2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Размещение девяти прямоугольников на доске 6*6
Сообщение03.02.2011, 15:28 
Недавно я участвовала в заочной олимпиаде, одна из задач которой формулировалась следующим образом:

Разместите на шахматной доске 6*6 девять прямоугольников, 1*4 клетки каждый, без перекрытий, или докажите, что это сделать невозможно.

Я отправила следующее решение:

Разобьём доску 6*6 на 9 квадратиков 2*2 и отметим левую верхнюю клетку в каждом квадратике. Каждый прямоугольник 1*4 будет покрывать либо ровно 0, либо ровно 2 отмеченные клетки, то бишь, чётное число. Но тогда число всех отмеченных клеток, занятых прямоугольниками, должно быть чётным. Следовательно, одна клетка останется свободной, а значит, не более 35 клеток будут заняты прямоугольниками, из чего следует, что прямоугольников не более 8.

Решение мне не засчитали (почему?), а правильным объявили следующее:

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

А чем моё хуже (или это их ляп?)?

 
 
 
 Re: Размещение девяти прямоугольников на доске 6*6
Сообщение03.02.2011, 15:52 
Задачка простая, решена тобой верно. Возможные причины провала:
1. Не любят евреев
2. Недоразумение
3. Проверял полный тормоз
4. Не нарисовала свою доску
5. Не доказала, что только четное покроет каждый кирпичик
6. Нигде не указала, что допустила покрытие и вывела противное
7. Замутила с одной клеткой

В итоге, надо было короче и яснее писать(твое решение ничем не хуже, мягко говоря)! По-любому, олимпиада не стоит тебя, обижают хороших девушек! :lol:

 
 
 
 Re: Размещение девяти прямоугольников на доске 6*6
Сообщение03.02.2011, 16:06 
LeXa в сообщении #408597 писал(а):
Задачка простая, решена тобой верно. Возможные причины провала:
1. Не любят евреев
2. Недоразумение
3. Проверял полный тормоз
4. Не нарисовала свою доску
5. Не доказала, что только четное покроет каждый кирпичик
6. Нигде не указала, что допустила покрытие и вывела противное
7. Замутила с одной клеткой

В итоге, надо было короче и яснее писать(твое решение ничем не хуже, мягко говоря)! По-любому, олимпиада не стоит тебя, обижают хороших девушек! :lol:

Скорее всего, 4-ая причина. Действительно, забыла нарисовать.

(За комплименты - отдельное спасибо!)



Вот ещё один способ, тоже легкообобщающийся до доски (4n+2)*(4n+2):

Опять же, разобьём доску на квадратики 2*2 и раскрасим эти квадратики в шахматном порядке (у правого нижнего все 4 клетки - белые (шахматное правило "light on right"), у каждого из соседних с ним - чёрные и. т. д.).
В этом случае каждый прямоугольник 1*4 покрывает ровно 2 белые и ровно 2 чёрные клетки, значит, всего покрыто ровно 18 белых и ровно 18 чёрных. Но у нас кол-во белых и чёрных - не равное.

Иными словами, доска 6*6 - это та же доска 3*3, вид сбоку :oops:

 
 
 
 Re: Размещение девяти прямоугольников на доске 6*6
Сообщение03.02.2011, 16:26 
Аватара пользователя

(Оффтоп)

А что за олимпиада была?

 
 
 
 Re: Размещение девяти прямоугольников на доске 6*6
Сообщение03.02.2011, 16:54 
Andrey173 в сообщении #408609 писал(а):

(Оффтоп)

А что за олимпиада была?

(Оффтоп)

Заочная олимпиада Техниона

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group