Режем шахматную доску. (ЗаЗа)
От: Pushkin Россия www.linkbit.com
Дата: 30.12.02 11:59
Оценка:
Из квадратной шахматной доски со стороной 2^N вырезали в произвольном месте 1 клетку.
Всегда ли можно замостить остаток 3-клеточными уголками?

28.01.03 20:57: Ветка выделена из темы Занимательные задачки
Автор: fAX
Дата: 07.08.02
— ХД
Re[2]: Режем шахматную доску.
От: KonstantinA Россия  
Дата: 30.12.02 12:47
Оценка: 8 (1)
Здравствуйте, Pushkin, Вы писали:

P>Из квадратной шахматной доски со стороной 2^N вырезали в произвольном месте 1 клетку.

P>Всегда ли можно замостить остаток 3-клеточными уголками?

Да. Доказательство по индукции.

N=1 очевидно
Пусть умеем для N<=k. Докажем для N=k+1.

Режем на 4 части. Выбираем ту, где вырезана клетка. Его заполняем. Осталось.

**|**
**|**
-----
**|
**|

Ставим уголок так.

**|**
*У|У*
-----
*У|
**|

Остальные заполняем по предположению индукции.
Re[3]: Режем шахматную доску.
От: Pushkin Россия www.linkbit.com
Дата: 30.12.02 12:54
Оценка:
Здравствуйте, KonstantinA, Вы писали:

KA>Здравствуйте, Pushkin, Вы писали:


P>>Из квадратной шахматной доски со стороной 2^N вырезали в произвольном месте 1 клетку.

P>>Всегда ли можно замостить остаток 3-клеточными уголками?

KA>Да. Доказательство по индукции.


OK
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.