Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет kouzdra ([info]kouzdra)
@ 2011-08-25 18:31:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Тригонометрическая задачка:
Прямоугольник разбит на прямоугольники у каждого из которых как минимум одна из сторон - целая. Доказать, что хотя бы одна из сторон "большого" прямоугольника тоже целая.

У нее есть охуенное тригонометрическое решение.

(Добавить комментарий)


[info]ded_mitya
2011-08-25 18:36 (ссылка)
Я тебя за такие посты отфренжу, ей-богу. ЕВПОЧЯ.
Вот как читать теперь ЖЖ в рабочий день...

(Ответить) (Ветвь дискуссии)


[info]kouzdra
2011-08-25 18:40 (ссылка)
Лет 10 назад эта задачка выбила из колеи нашу фирму на пару дней. Я ее решил часа за три - но увы "тупой техникой" и довольно долго не знал, "правильного" ее решения.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ded_mitya
2011-08-25 18:42 (ссылка)
Я кажется, нащупал решение индукцией. Но надо расписать,
а времени нет.

(Ответить) (Уровень выше)


[info]loknar
2011-08-28 11:11 (ссылка)
никак не могу придумать тригонометрическое решение

моё решение:
берём левый верхний прямогольник и обрезаем "большой" прямогольник по линии, содержащей сторону левого верхнего, которая "не обязательно целая". таким образом отрезается полоса с целой шириной.
очевидно, целость сторон большого прямоугольника и его оставшихся частей не меняются
продолжем, пока не останется один прямогольник.
одна из его сторон, очевидно, целая. поскольку целость не менялась, то у исходного "большого прямоугольника" целая та же сторона

(Ответить)


[info]akater
2011-08-28 17:43 (ссылка)
М-м-м...

Пусть стороны прямоугольника равны a и b. При этом известно, что

a = a1 + ... + an
b = b1 + ... + bm

Если обе эти суммы одновременно нецелые, то одновременно существуют нецелые ai и bj. То есть, (i, j)-ый прямоугольник имеет обе нецелые стороны.

Что-то не так?

(Ответить) (Ветвь дискуссии)


[info]loknar
2011-08-28 18:04 (ссылка)
всё не так
перечитай условие

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]akater
2011-08-28 18:19 (ссылка)
А, разбиение необязательно «сеткой»? Но его можно легко превратить в сеточное и провести такое же рассуждение.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]loknar
2011-08-28 23:12 (ссылка)
мне не приходит в голову простого метода привести к сеточному с сохранением целости
может он и есть
выше я написал своё доказательство, достаточно простое

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]akater
2011-08-29 02:22 (ссылка)
Да, действительно, не очень прозрачно. К суммам для a и b нужно присовокупить список допустимых прямоугольников. Если обе суммы нецелые, в них обоих есть нецелые подсуммы. Эти нецелые можно обозначить за a', b' и повторить процедуру. Если перебрать все возможные случаи, согласуясь на каждом шаге со списком допустимых прямоугольников, то алгоритм (очевидно, конечный) должен в результате привести ко всем прямоугольникам с нецелыми сторонами.

Но я согласен, что это, если и правильно, то не очень красиво. Вообще, многие конструктивные доказательства некрасивы.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2011-08-29 16:27 (ссылка)
У меня решение - доказательство для сторон, являющихся рациональными числами с простым знаменателем: там простая делимость - приводим все к общему знаменателю - .../q - соответственно площажи многоугольников имеют в числителе множитель q -> соответственно сумма площадей тоже делится на q -> одна из сторон целая.

Далее - предельный переход.

Тригонометрическое схожее - подбирается несложная тригфункция, интеграл которой по прямоугольнику с целой стороной равен нулю тогда и только когда. Далее - тоже все ясно.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]loknar
2011-08-31 03:19 (ссылка)
не понял доказательство, можно поподробней

> подбирается несложная тригфункция, интеграл которой по прямоугольнику
двойной интеграл, правильно?
тогда можно подобрать ф-ю, для достижения нуля интеграла которой на прямоугольнике достаточно целости одной из сторон
но как доказать необходимость, например?

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]kouzdra
2011-09-01 21:15 (ссылка)
Реально это cos 2 pi x * cos 2 pi y.

Двойной интеграл тут произведение одинарных интегралов cos 2 pi x. Каковые одинарные интегралы равны нулю тогда и только тогда, когда диапазон интегрирования целый.

А произведение двух чисел равно нулю тогда и только тогда, когда хотя бы один из сомножителей равен нулю. Собственно все.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]loknar
2011-09-01 21:37 (ссылка)
согласен, видно, если интегрировать
первое док-во я тоже не понял(которое через общий знаменатель) :(
btw мое док-во ок?

(Ответить) (Уровень выше)


[info]kouzdra
2011-08-29 16:22 (ссылка)
Так свойство целости при этом теряется.

(Ответить) (Уровень выше)