Разобьем доску двумя на квадраты 2x2 и на прямоугольники 1x3 (3x1) + 1 клетка), как показано на рисунке. Пусть в каждом квадрате 2x2 ровно n фигур, а в каждом прямоугольнике 1x3 (3x1) ровно m фигур. Тогда при первом разбиении получается (8 * 8) / (2 * 2) * n = 16n фигур, а на втором (8 * 8 - 1) / 3 * m = 21m либо 21m + 1 фигур (+1 за счет одной клетки, не попавшей ни в один из прямоугольников из 3 клеток). Переберем все возможные значения m (0, 1, 2 и 3) и подберем для них все возможные значения n.
m = 0: 16n = 0 либо 16n = 1. Получаем n=0, а значит ни одной фигуры не выставлено.
m=1: 16n=21 либо 16n=22. Такого быть не могло (ни 21, ни 22 не делятся на 16)
m=2: 16n=42 либо 16n=43. Такого быть также не могло (ни 42, ни 43 не делятся на 16)
m=3: 16n=63 либо 16n=64, откуда n=4 и вся доска заставлена фигурами (их 64). Больше вариантов нет.
И 0, и 64, очевидно, подходят (во всех клетках одинаковое количество фигур, а значит в любых объединениях клеток, содержащих одинаковое число клеток, содержится одинаковое количество фигур).
Число 1 можно поменять с любым другим (все числа от 2 до 2017 делятся на 1). Будем поступать следующим образом:
1) Если число 1 не стоит на месте i (i не равно 1), то меняем местами число 1 и число, стоящее на месте i. 2) Меняем местами число i и число 1.
Повторяем эти действия для всех i от 2 до 2017.
Покажем, что таким образом числа окажутся в порядке возрастания. На месте t>1 после t-1 повторения оказывается число t. После этого мы это число не трогаем (далее мы меняем 1 только с числами, большими t). Значит после 2016-го применения данного алгоритма на позициях 2..2017 окажутся числа 2..2017 в порядке возрастания. Значит для числа 1 осталось только позиция 1. Отсюда все числа расположены в порядке возрастания. Всего произведено 2*2016=4032 операций.
0,0(0 оценок)
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota
Оформи подписку
