Навчання / Бібліотека / Головоломки
Доміно на обрізаній дошці
Дошка на одиничних клітинок має вирізані кутові клітинки. Доміно накриває рівно клітинки зі спільним ребром. Яка найбільша кількість доміно, що можна розмістити на решті клітинок без перекриттів?
Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.
Підказка
Розфарбуйте клітинки як шахівницю й порахуйте кожен колір. Кожне доміно накриває по одній клітинці кожного кольору.
Розв’язок
- Розфарбуйте клітинки як шахівницю, щоб кути мали перший колір. Цей колір має клітинок, а інший — , і всі вирізані кути мають перший колір, тож лишається і .
- Кожне доміно накриває по одній клітинці кожного кольору, тож поміститься щонайбільше доміно.
- Розміщення з існує: по горизонтальні доміно в кожному з рядків від до над стовпцями від до (), по у кожному з рядків і над стовпцями від до () і вертикальні в стовпці над рядками від до .
- Найбільша кількість дорівнює .
Відповідь: