Нецелый прямоугольник

venco · Сб янв 08, 2005 11:13 am

Можно ли составить из произвольного количества произвольных прямоугольников, у каждого из которых одна сторона - целая, а вторая сторона - любая, большой прямоугольник с обеими нецелыми сторонами (без перекрытий и просветов).

Dimchik · Сб янв 08, 2005 2:42 pm

Нельзя.

Увы, я знаю аналогичную задачу, поэтому решением вполне не насладился:(

olg2002 · Пн янв 10, 2005 6:20 pm

Если мы заменим в задаче "целое-нецелое" на "четное-нечетное", то у нее появляется очень простое решение, которое, однако, не обобщается тривиально на случай "целое-нецелое". С другой стороны результат задачи остается в силе при замене условия на, скажем, "рациональное-нерациональное". Dimchik, какую аналогичную задачу имели ввиду Вы? Обобщается ли ее решение на произвольное аддитивное условие?

P.S. Радует завидная активность в разделе в новом году.

PavelM · Пн янв 10, 2005 7:50 pm

olg2002 писал(а):Если мы заменим в задаче "целое-нецелое" на "четное-нечетное", то у нее появляется очень простое решение, которое, однако, не обобщается тривиально на случай "целое-нецелое". С другой стороны результат задачи остается в силе при замене условия на, скажем, "рациональное-нерациональное".

Не совсем в точку, но действуете в правильном направлении :wink:

. Известное мне решение использует некую функцию имеющую разные значения при целых и нецелых аргументах, а далее как Вы заметили все просто ...

olg2002 · Пн янв 10, 2005 8:06 pm

Да нет, я знаю элементарное (не в смысле простое) решение для самого общего случая (к сожалению не свое). Интересно, что задача предлагалась на сайте IBM "Ponder This" в мае 1999. Оба предлагаемых решения не сильно тянут на элементарные и не обобщаются на более широкие классы чисел (рациональные, a+b*sqrt(2), etc.).

PavelM · Пн янв 10, 2005 8:40 pm

olg2002 писал(а):Да нет, я знаю элементарное (не в смысле простое) решение для самого общего случая (к сожалению не свое).

Интересно

Интересно, что задача предлагалась на сайте IBM "Ponder This" в мае 1999. Оба предлагаемых решения не сильно тянут на элементарные и не обобщаются на более широкие классы чисел (рациональные, a+b*sqrt(2), etc.).

Именно о первом из них я и говорил. В принципе там вместо экспоненты некоторые другие периодические функции тоже подойдут, синус например.

vc · Сообщение vc » Пн янв 10, 2005 9:52 pm

olg2002 писал(а):Да нет, я знаю элементарное (не в смысле простое) решение для самого общего случая (к сожалению не свое). Интересно, что задача предлагалась на сайте IBM "Ponder This" в мае 1999. Оба предлагаемых решения не сильно тянут на элементарные и не обобщаются на более широкие классы чисел (рациональные, a+b*sqrt(2), etc.).

The rational case is an obvious corollary of integer sides. The theorem can be restated for algebraic sides too, not so obviously, but I do not remember the proof.

VC

venco · Пн янв 10, 2005 10:20 pm

olg2002 писал(а):Да нет, я знаю элементарное (не в смысле простое) решение для самого общего случая (к сожалению не свое). Интересно, что задача предлагалась на сайте IBM "Ponder This" в мае 1999. Оба предлагаемых решения не сильно тянут на элементарные и не обобщаются на более широкие классы чисел (рациональные, a+b*sqrt(2), etc.).

Да, что-то они там перемудрили. Можно синусами обойтись.

vc · Сообщение vc » Пн янв 10, 2005 10:48 pm

venco писал(а):
olg2002 писал(а):Да нет, я знаю элементарное (не в смысле простое) решение для самого общего случая (к сожалению не свое). Интересно, что задача предлагалась на сайте IBM "Ponder This" в мае 1999. Оба предлагаемых решения не сильно тянут на элементарные и не обобщаются на более широкие классы чисел (рациональные, a+b*sqrt(2), etc.).

Да, что-то они там перемудрили. Можно синусами обойтись.

How ?

venco · Пн янв 10, 2005 10:55 pm

vc писал(а):
venco писал(а):Да, что-то они там перемудрили. Можно синусами обойтись.

How ?

F(x,y) = sin(2*Pi*x)*sin(2*Pi*y)

Хотя нет, отставить. С экспонентой всё же проще.
Тут надо добавить ещё косинусы, да ещё разные хитрые случаи рассмотреть...

olg2002 · Пн янв 10, 2005 11:19 pm

Статья "Fourteen proofs of a result about tiling a rectangle" by Stan Wagon опубликована в книге "The Lighter Side of Mathematics" by R.KGuy and R.E.Woodrow, eds. (pp.113-127). Книга доступна на amazon.com в "search inside" формате. Элементарное доказательство (из теории графов) можно увидеть в "Simple Proofs of a Rectangle Tiling Theorem".

venco · Ср янв 12, 2005 5:19 pm

venco писал(а):
vc писал(а):
venco писал(а):Да, что-то они там перемудрили. Можно синусами обойтись.

How ?

F(x,y) = sin(2*Pi*x)*sin(2*Pi*y)

Хотя нет, отставить. С экспонентой всё же проще.
Тут надо добавить ещё косинусы, да ещё разные хитрые случаи рассмотреть...

Чего это я... Испугали вы меня, vc.

Очень даже синусов достаточно. Та самая функция выше.

vc · Сообщение vc » Ср янв 12, 2005 7:00 pm

venco писал(а):
venco писал(а):
vc писал(а):
venco писал(а):Да, что-то они там перемудрили. Можно синусами обойтись.

How ?

F(x,y) = sin(2*Pi*x)*sin(2*Pi*y)

Хотя нет, отставить. С экспонентой всё же проще.
Тут надо добавить ещё косинусы, да ещё разные хитрые случаи рассмотреть...

Чего это я... Испугали вы меня, vc.
Очень даже синусов достаточно. Та самая функция выше.

I am sorry

This was not my intent. I should have asked "how i[s it simpler] ?" instead.

The (x,y) --> (exp(2*pi*i*x), exp(2*pi*i*y) mapping is just more obvious (to my eye) than the 'sin(2*x)' or 'cos(2*x)' one. In the latter case you need to remember the trigonometric identities which is of course no big deal.

VC

venco · Ср янв 12, 2005 7:09 pm

vc писал(а):
venco писал(а):F(x,y) = sin(2*Pi*x)*sin(2*Pi*y)

The (x,y) --> (exp(2*pi*i*x), exp(2*pi*i*y) mapping is just more obvious (to my eye) than the 'sin(2*x)' or 'cos(2*x)' one. In the latter case you need to remember the trigonometric identities which is of course no big deal.

Да не надо здесь этого знать.
Единственное что нужно - это что интеграл синуса - косинус.
А множитель 2*pi - это чтобы интеграл на целом интервале нулю был равен.

vc · Сообщение vc » Ср янв 12, 2005 7:51 pm

venco писал(а):
vc писал(а):
venco писал(а):F(x,y) = sin(2*Pi*x)*sin(2*Pi*y)

The (x,y) --> (exp(2*pi*i*x), exp(2*pi*i*y) mapping is just more obvious (to my eye) than the 'sin(2*x)' or 'cos(2*x)' one. In the latter case you need to remember the trigonometric identities which is of course no big deal.

Да не надо здесь этого знать.
Единственное что нужно - это что интеграл синуса - косинус.
А множитель 2*pi - это чтобы интеграл на целом интервале нулю был равен.

I think you (or maybe me

are a bit confused:

Int_x1_x2 Int_y1_y2 cos(2*pi*x)*cos(2*pi*y) *dx*dy ==>

1/(4*pi^2)*(sin(2*pi*x2) - sin(2*pi*x2))*(sin(2*pi*y2) - sin(2*pi*y1)) =>

.. then, _knowing_ the identity sin(u)-sin(v) = 2*cos((u+v)/2)*sin((u-v)/2), you can conclude that the integer values of (x2-x1) or (y2-y1) will make the measure equal zero.

In the case of 'exp', zeroes, or rather ones, are 'obvious' immediately.

VC