avva: (Default)
[personal profile] avva
"Квадрат размером 103x103 клетки можно полностью покрыть непересекающимися квадратами размерами 2x2 и 3x3 клетки."

Доказать или опровергнуть.

Update: Исправлено первоначально неверное условие задачи, пр. пр.

Update (3 часа после записи): в комментах появилось правильное решение! Те, кто хотят думать сами - не заглядывайте.

Re:

Date: 2002-12-04 06:20 pm (UTC)
From: [identity profile] avva.livejournal.com
Чёрт его знает. Я не очень хорошо знаком с такими задачами. Эта конкретная ведь типично "олимпиадная" по своей сути, но есть и действительно серьёзные задачи в этой области. Не думаю, что раскраска часто в них помогает.

Если не ошибаюсь, например, довольно долго оставался открытым такой вопрос: можно ли заполнить квадрат меньшими квадратами с неповторяющимися размерами? (можно)

Another One

Date: 2002-12-04 06:55 pm (UTC)
From: (Anonymous)
А Вам знакома задача из схожей "Олимпиадной" тематики про 12 мешков?
Имеется 12 мешков. Один из них отличается весом, остальные 11 - одинаковые. За три (3) взвешивания на рычажных весах нужно не только найти отличающийся мешок, но и определить, легче он или тяжелее, чем остальные.
P.S. Я до сих пор над ней бьюсь, хотя лично знаю трех людей, ее решивших. В том числе девушку, решившую ее за недолгую поездку в маршрутке. Но пока не сдаюсь ;-)

Re: Another One

Date: 2002-12-04 06:57 pm (UTC)
From: [identity profile] avva.livejournal.com
Очень старая задачка. Я её знаю, да.

Re: Another One

Date: 2002-12-05 12:52 am (UTC)
From: [identity profile] peretz.livejournal.com
кстати, по поводу этой задачки про 12 мешков - мне известно ее решение с буквами. а есть какое-нибудь объяснение, формализованное с точки зрения логики? потому что к решению с буквами за время поездки в маршрутке не придешь...

Re: Another One

Date: 2002-12-05 03:18 am (UTC)
From: [identity profile] haraz-bey.livejournal.com
Есть. Даже два. Могу намылить.

Re: Another One

Date: 2002-12-05 03:27 am (UTC)
From: [identity profile] peretz.livejournal.com
Если не сложно...

Условие?

Date: 2002-12-04 06:59 pm (UTC)
From: (Anonymous)
А можно уточнить условие, особенно - про "непотворяющиеся размеры" квадратов?

Re: Условие?

Date: 2002-12-04 07:05 pm (UTC)
From: [identity profile] avva.livejournal.com
Найти такое n, и такое разбиение квадрата размером nxn клеток на конечное количество меньших квадратов, что никакие два из этих меньших квадратов не имеют одинаковый размер.

Date: 2002-12-05 12:58 am (UTC)
From: [identity profile] kukukas.livejournal.com
Вот еще пример задачки "на раскраску":

Из шахматной доски вырезали поля А1 и Н8.
Доказать возможность или невозможность заполнения доски доминошками (31 штука, каждая занимает 2 клетки).

Date: 2002-12-05 11:35 am (UTC)
From: (Anonymous)
А1 и Н8 - черные клетки (в общем случае - клетки одного цвета). Если их вырезать (из шахматной раскраски), то останется 30 черных клеток и 32 белых. Каждая доминошка покрывает одну черную и одну белую клетку. После покрытия 30-ю доминошками останется две белых клетки, которые не могут быть накрыты одной доминошкой ;-)

December 2025

S M T W T F S
  123 4 56
78 9 10 11 1213
1415 1617181920
21 22 23 24 2526 27
28293031   

Most Popular Tags

Page Summary

Style Credit

Expand Cut Tags

No cut tags
Page generated Dec. 28th, 2025 09:22 pm
Powered by Dreamwidth Studios