/ it Задачи / Шахматная доска и кости домино

Шахматная доска и кости домино

Шахматная доска и кости домино

1 794 · 15 декабря 2016 в 15:37 ·
На первый взгляд простая задача, в которой вам надо выяснить можно ли расставить кости домино на шахматной доске размером 8x8. На самом деле не все так просто! :)
У вас есть самая обыкновенная шахматная доска, размер которой 8х8. При этом, в шахматной доске нету двух противоположных по диагонали квадратиков. Также у вас есть 31 кость домино. Ваша задача состоит в том, чтобы ответить на простой вопрос: можно ли расположить все кости на шахматной доске? Одна кость занимает два квадратика. Обычно, если на собеседовании задают подобный вопрос, то еще просят обосновать свой ответ, поэтому сделайте это тоже.

Решение

Давайте начнем с самого начала. У вас есть доска размером 8х8, соответсвенно на доске есть 64 квадратика. Если учесть тот момент, что двух не хватает, то получаем цифру 62. Теперь если каждое домино занимает по два квадратика, а у нас 31 кость домино, то хочется сразу ответить положительно, но это будет неправильный ответ.

На этом этапе важно заметить, что мы удалили именно два противоположных по диагонале квадратика. Это означает, что на нашей доске осталось на два, к примеру, черных квадратика меньше, нежели белых квадратиков. Таким образом, у нас на доске сейчас 32 белых и 30 черных квадратов.

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

Таким образом, как бы вы не старались заполнить вашу шахматную доску, вы все равно это не сможете сделать, так как отсутствующие два одинаковых квадратика всегда будут мешать вам доложить еще одну кость в ряд.

Итак, ответ для данной задачи - нет!

Больше интересных новостей