Home » Работа и карьера » Тесты при приеме на работу в ABBYY Software – Ответы 5

Тесты при приеме на работу в ABBYY Software – Ответы 5

Хочу поблагодарить читателя Ravlyk, оставившего совершенно правильный ответ на пятую задачу в комментариях:

5. На клетчатом поле 8х8 вырезали по клетке в противопол-х углах диагонали.. Можно ли замостить получившееся поле паркетинами 2х1? Ответ доказать.

Ответ: Нет.

Доказательство:

Пусть поле будет шахматное, с черными и белыми клетками.  Вырезано было 2 клетки одинакового цвета (на одной диагонили все клетки одного цвета). Как результат клеток одного из цветов больше чем клеток другого цвета. Каждая паркетина 2х1 ложится на две соседние клетки, причем очевидно – это клетки разных цветов. Соответственно в самом лучшем раскладе останутся две клетки одного цвета, на которые невозможно будет уложить паркетину.

Спасибо!

  • 111

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

  • Alina Portna

    Прошу прощение, но при чем здесь цвета клеток?..
    Постановка задачи серьезнее- нужно доказать, что заполнение поля участками 2*1 геометрически невозможно.

    • В условии задачи не было ограничений на способ доказательства.

      • Alina Portna

        аааааааа но это и не доказательство))
        к задаче были дописаны условия и та, более простая задачка конечно же решена.
        но это не доказывает оригинальную задачу..
        для наглядности:
        в доказательстве написано “Соответственно в самом лучшем раскладе останутся две клетки одного цвета, на которые невозможно будет уложить паркетину.”
        да неправда. возможно будет). В условии задачи не сказано, что паркетина состоит из клеток разного цвета)