Пусть в основании пирамиды лежит 2024-угольник , точка — вершина пирамиды. Пусть для всех , сфера касается ребер в точке , а ребер в точке ().

Рассмотрим треугольник . Сечением сферы в его плоскости является вписанная в него окружность, которая касается его сторон в точках , , . Пусть

Из теоремы косинусов имеем

Как известно,

По условию достаточно показать, что произведения квадратов половинных синих и половинных красных углов равны. Но из равенства выше каждое из таких произведений равно произведению отношений для всех , что доказывает исходное равенство.

Переформулируем условие задачи на язык графов. Каждому племени поставим в соответствие вершину, между любыми двумя соседними проведем ребро. Для каждой вершины определен ее идол, если идол соседней вершины сильнее, то в этот день вершина меняет своего идола на более сильного.

Будем решать задачу индукцией по количеству вершин. База индукции для графа, состоящего из одной вершины, очевидна.

Докажем, что если условие задачи верно для некоторого натурального то оно же верно для Выберем висячую вершину исходного дерева, родителем которой является вершина

Будем говорить, что вершина влияет на вершину если данные вершины являются соседями и идол сильнее идола при этом не имеет соседа с более сильным идолом, отличным от

Если не существует дня, в котором вершина влияло на вершину В графе, полученном из данного удалением вершины по предположению индукции все вершины через несколько дней будут иметь одного и того же идола, в частности его же будет иметь вершина а значит и вершина

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

Из отрезков можно сложить четырехугольник тогда и только тогда, когда . Рассмотрим четверку , заметим, что , следовательно, , иначе проверяемое неравенство не выполнено. Аналогично, можно показать, что .

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

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

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

Первое решение.

Из вписанности четырехугольника следует, . Треугольник является равнобедренным, а значит , следовательно, .

Из равнобедренности треугольника следует, что .

Наконец, в силу вписанности четырехугольника

Второе решение.

Достаточно показать, что хорды и стягивают равные дуги в окружности , то есть доказать равенство . По теореме о внешнем угле верно,

Поскольку треугольник является равнобедренным , а из вписанности четырехугольника следует, что . Таким образом,

Аналогично,

Наконец, исходное равенство углов можно переписать в виде

что верно, так как суммой углов в каждой части равна углу между диагоналями четырехугольника.

Заметим, что если для исходного числа существует такой момент, то и для числа , полученного вычеркиванием всех девяток из исходного, он так же существует, поскольку каждое вычеркивание не меняет остаток при делении суммы цифр на 9.

Рассмотрим число . В силу неравенства , отношение количества восьмерок к оставшимся числам, больше 9. Отметим подряд идущие блоки по 9 чисел. Докажем, что существует блок, элементами которого являются лишь восьмерки. Пусть это не так, тогда в каждом блоке есть цифра отличная от восьмерки, следовательно, количество цифр, не являющихся восьмерками, хотя бы от общего количество, что противоречит полученному неравенству.

Рассмотрим блок, состоящий только из восьмерок. Пусть число, полученное из вычеркиванием всех цифр до найденного блока, имеет остаток при делении на 9. Каждое вычеркивание 8 увеличивает остаток при делении на 9 на 1, следовательно, вычеркнув элементов в блоке, мы получим искомое число.

Оценка. Приведём пример ситуации, в которой 4 дней не хватит. Пусть у каждого из 45 людей будет своя, не совпадающая с другими людьми, пара дней, в которые он не может участвовать во встрече. Так как количество способов выбрать пару дней из 10 предложенных равно , то для любой пары дней найдётся человек, который не может присутствовать ровно в эту пару дней. Предположим, что мы смогли выбрать какие-то 4 дня так, чтобы каждый узнал все новости. Но тогда существует человек , который не может присутствовать в первые два дня из этих четырёх, а также человек , который не может присутствовать в последние два из этих четырёх дней. Заметим, что тогда не сможет узнать новостей . Противоречие.

Пример. Теперь поймём, что 5 дней всегда точно хватит. Выберем 5 дней произвольным образом. Докажем, что любые два человека будут вместе присутствовать на какой-то встрече. Действительно, среди этих 5 дней есть не более 2 дней, в которые не может присутствовать первый, а также не более 2 дней, в которые не может присутствовать второй. Значит, найдётся день, в который могут присутствовать оба человека. Таким образом, каждая пара людей сможет обменяться новостями, то есть каждый узнает новость каждого.

Докажем, что из любой уравновешенной доски можно получить доску, раскрашенную в шахматную раскраску, причём на каждом шаге доска будет оставаться уравновешенной. Из этого будет следовать, что из любой уравновешенной доски можно получить любую другую, так как операция обратима.

Будем получать шахматную раскраску следующим образом. Разобьём столбцы на пары подряд идущих. Выберем самую левую пару столбцов и в этой паре столбцов по очереди будем приводить строки (состоящие из двух клеток) к шахматной раскраске. После того как закончим с первой парой столбцов, перейдём ко второй и так далее.

Объясним, как делать следующий шаг внутри одной пары столбцов и Пусть в следующей строке сейчас находятся чёрная и белая клетка, но в неправильном порядке. Например, слева стоит чёрная клетка, а справа белая, а должно быть наоборот. Заметим, что во всех строках выше в первом столбце суммарно чёрных клеток не меньше, чем во втором, так как они уже покрашены шахматным образом. Значит, в какой-то строке ниже должна быть ситуация, когда в левом столбце чёрных клеток меньше, чем в правом, т.е. должна быть строка белая-чёрная (это следует из того, что суммарно в первом столбце столько же чёрных клеток, сколько и во втором). Произведём операцию со строками и и текущими столбцами.

Пусть теперь у нас в строке стоят две одинаковые клетки, например чёрные. Тогда в какой-то строке должны оказаться две белые клетки (иначе суммарно чёрных клеток в этих двух столбцах будет слишком много). Понятно, что эта строка расположена ниже текущей, т.к. выше неё все строки разноцветные. Теперь заметим, что если посмотреть на эту пару строк во всей таблице, то должен быть столбец правее и в котором в первой строке белая клетка, а во второй — чёрная. Тут мы пользуемся тем, что левее наших столбцов в этих строках поровну чёрных и белых клеток. Теперь осталось лишь выбрать один из столбцов или (в котором неправильный цвет в строке и столбец а также строки и и произвести операцию с ними.

Легко видеть, что на каждом шаге уравновешенность доски сохраняется. А так как мы всегда можем сделать шаг в нашем алгоритме, то в конце получится шахматная раскраска.

Докажем, что точки лежат на одной окружности т.е. что четырёхугольник является вписанным. Действительно, как накрест лежащие при параллельных прямых и и секущей а как опирающиеся на одну дугу в значит, Следовательно, по признаку четырёхугольник является вписанным.

Из этого получаем, что Из окружности получаем, что Значит, а, следовательно, по признаку четырёхугольник является вписанным, т.е. точки лежат на одной окружности.

Воспользуемся алгоритмом Евклида для получим

Заметим, что, так как НОД двух натуральных чисел не превосходит каждое из них,

Аналогично получаем, что

А также

Складывая эти три неравенства, получаем

В качестве примера на можно предъявить, например, В этом случае

В данных выражениях умножим числители и знаменатели на соответственно (согласно условию, эти разности ненулевые). Получим те же числа в другом виде:

Без ограничения общности будем считать, что первое и третье числа равны. Тогда

Это симметричное равенство, поэтому теперь можно просто поменять местами две переменные (например, и и проделать те же переходы в обратном порядке, получив равенство третьего и второго чисел:

Деления при этом корректны, так как выражения-делители уже фигурировали ранее в знаменателях, и мы знаем, что они не равны нулю.

Пойдём от противного, предположим, что такое возможно. Без ограничения общности можно считать, что число 1 покрашено в красный. Выберем произвольное число покрашенное в синий. Заметим, что тогда должно быть зелёного цвета, — синего, — зелёного и т.д. Таким образом, все числа, большие покрашены в синий или зелёный цвет. С другой стороны, так как покрашен в синий цвет, a — в зелёный, то число должно быть покрашено в красный цвет, противоречие. Значит, такое невозможно.

Докажем оценку

______________________________________________________________________________________________________________________________________________________

Пусть существует стратегия, позволяющая ошибаться не более чем в битах т.е. Тогда заметим, что Наблюдатель, знающий стратегию Фокусника, сообщенное Ассистентом слово, и набор бит, в которых ошибся Фокусник, может восстановить написанное Зрителем слово. В самом деле, Наблюдатель берет слово, которое должен был написать Фокусник, и меняет его в тех местах, где Фокусник ошибся. Значит, количество различных пар вида "слово сообщенное Ассистентом и набор мест, в которых фокусник ошибся"не меньше, чем различных слов, которые мог написать зритель. То есть

Перепишем в виде

Заметим, что при неравенство неверно:

_________________________________________________________________________________________________________________________________________________________________________________

Теперь попробуем показать, из каких соображений строится пример. Для начала напомним конструкцию, известную как математикам так и программистам: двоичный код длины 15, позволяющий передать 11 бит полезной информации и исправить ошибку не более чем в одном бите (также известен как 15-битный код Хэмминга). Построим его.

Для начала заметим, что есть ровно 11 слов длины 4 из нулей и единиц, содержащих хотя бы две единицы (всего слов минус одно из одних нулей, минус четыре с одной единицей). Припишем такие слова номерам от 1 до 11 как угодно, например как в таблице:

Теперь построим код таким образом: в первые 11 бит запишем те биты, которые хотим передать (первые 11 позиций будем называть информационными). В последние 4 бита запишем следующие контрольные суммы. В 12-й запишем сумму по модулю два тех из первых 11 бит, приписанное 4-значное число которых имеет 1 в первом разряде, то есть биты № 3,5,6,8,9,10,11. В 13-й — сумму тех из первых 11 бит, приписанное 4-значное число которых имеет 1 во втором разряде, в 14-й сумму бит, имеющих 1 в третьем разряде приписанного слова, в 15-й — в четвертом. Покажем, почему этот код позволяет исправить одну ошибку при передаче.

_________________________________________________________________________________________________________________________________________________________________________________

Пусть Получатель получил кодовое слово, возможно искаженное в одном бите. Получатель точно так же по первым 11 битам посчитает 4 контрольные суммы, и сравнит их с четырьмя полученными. Если совпали все четыре — то слово дошло без искажений. В самом деле, если бы исказился контрольный бит — в нем было бы расхождение, а если информационный — то расхождения были бы во всех контрольных, в которые он входит. Аналогично, если расхождение есть ровно в одном контрольном бите, то исказился именно он. В самом деле, если исказился другой контрольный — то все информационные дошли правильно, тогда в этом контрольном расхождения бы не было; а если исказился информационный, то все контрольные дошли правильно, и тогда расхождения были бы во всех контрольных, в которые входит искаженный информационный, а таких контрольных хотя бы два (именно за этим мы приписывали комбинации нулей и единиц, содержащие хотя бы две единицы). По аналогичным соображениям если получатель видит не менее двух расхождений с контрольными битами, то искажен точно информационный. Тогда достаточно из 11 информационных позиций выбрать ту, в приписанном 4-битном слове которой единицы стоят ровно на тех местах, на которых есть расхождения с контрольными суммами — это и есть искаженная позиция.

_________________________________________________________________________________________________________________________________________________________________________________

Теперь подумаем в других терминах, что же мы построили. У нас есть код из кодовых слов. Каждое из этих слов можно исказить 16 способами (ничего не менять, или изменить один из 15 бит). Все полученных в результате слов будут разными. В самом деле, если бы какое-то слово получалось двумя разными способами: искажением кодового слова и искажением кодового слова (в обоих случаях — не более чем в одном бите), то код бы не исправлял одну ошибку — Получатель может получить слово но в этом случае не может понять, посылали ему или Итак, все слов разные, но это означает что вообще любое из слов длины 15 получается искажением какого-то из кодовых слов не более чем в одном бите.

На этом и построим стратегию Фокусника и Ассистента. Ассистент видит написанное зрителем 60-битное слово, режет его на четыре 15-битных слова Как доказано выше, для них найдутся кодовые слова такие что отличается от не более чем в одном символе. Тогда Ассистент выбрасывает из каждого кодового слова контрольные символы, получает четыре слова длины 11, то есть одно слово длины 44. Его он и передает Фокуснику. Фокусник восстанавливает контрольные суммы, получает слово отличающееся от исходного максимум в четырех битах — победа.

Нам будет полезен аналог целой части выражающий для двух чисел с разностью расстояние по окружности между образами этих чисел, если намотать числовую прямую на единичную окружность: будем говорить, что при и при (здесь обозначает обычную целую часть числа ). Тогда, например, если длина дуги между точками и равна то длина дуги между и равна

Для краткости точку будем обозначать просто Заметим, что точки не повторяются: если бы оказалось, что при то выполнялось бы и т.д., тогда число хорд было бы конечным. Итак, каждая новая точка попадает строго между ранее поставленными.

Определим по индукции понятие активной дуги -го шага. Для натурального будем ей считать ту из двух дуг на которую попадает . Заметим, что тогда все точки лежат на активной дуге первого шага. В самом деле, пусть все точки от 2 -й до -й лежат на активной дуге 1 -го шага, а -я там не лежит. Тогда хорды и пересекаются.

Теперь предположим, что мы уже индукцией по доказали, что все точки попадают на активную дугу -го шага при Определим активную дугу -го шага. лежит на -й активной дуге, значит делит ее на две части. На одну из этих частей попадает точка — эту часть и будем называть активной дугой -го шага. Тогда чтобы индукция работала нам осталось доказать, что все точки лежат на этой дуге при Понятно, что концы дуги — это какие-то из предыдущих точек значит есть фрагмент ломанной, соединяющий их. Значит если еще лежит на дуге, а — уже нет, и не совпадает ни с одной из предыдущих точек (что упоминалось ранее) — значит, пересекается с указанным фрагментом ломанной.

Как легко видеть, каждая следующая активная дуга является подмножеством предыдущей. Более того, обозначим через длину активной дуги, а через — длину дуги (той из двух, которая лежит внутри активной). Тогда или

(1)

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

Если предел равен нулю, то нулю же равен и предел последовательности поскольку Но заметим, что То есть если то Кроме того, всегда не равно нулю (иначе две точки совпали). Значит для в последовательности встречаются члены большие со сколь угодно большими номерами — ноль не является пределом.

Пусть предел равен положительному числу Тогда по последовательность разбилась на две подпоследовательности, предел одной равен нулю, предел другой — , причем по доказанному выше вторая содержит бесконечное число членов. Заметим, что — неподвижная точка преобразования Тогда аналогично если

Выберем будем говорить о числах 0 и как о двух пределах. Начиная с какого-то номера все должны попадать в -окрестность одного из двух пределов. Но тогда при переходе от к расстояние до предела будет расти в 2022 раза - рано или поздно выскочит из -окрестности текущего предела и еще не дотянется до -окрестности другого предела.

Сразу заметим, что при равенство из условия невозможно, так что далее мы везде считаем, что даже когда не напоминаем об этом явно.

Предположим, что такие многочлены и нашлись. Тогда можно считать, что они взаимнопросты (иначе поделим оба на общий множитель — новая пара тоже удовлетворяет условию), и у старший коэффициент равен 1 (домножим и на константу , чтобы старший коэффициент стал равен 1). Введем обозначение для разложения на линейные множители (естественно, воспользовавшись существованием такого разложения в комплексных числах):

Для комплексного числа множество чисел вида где , будем называть цепью числа

______________________________________________________________________________________________________________________________________________________

Ключевое утверждение:

Если — корень то числа 0 и 1 принадлежат цепи

______________________________________________________________________________________________________________________________________________________

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

Пусть — корень тогда обозначим через и такие минимальное и максимальное значения при которых является корнем Заметим, что и определены корректно: множество значений не пусто (поскольку 0 подходит) и конечно, поскольку у конечное число корней (первое место, в котором важно, что ). Тогда пусть не оба числа 0 и 1 лежат в цепи Тогда одно из двух чисел и не является ни 0 ни 1 (второе место: нам важно, что и — два разных числа). Рассмотрим эти два случая.

Пусть — не равно ни 0 ни 1. Посмотрим на равенство из условия

и разложим левую часть на простейшие дроби:

где степень меньше при причем

Поскольку — корень в разложение входит член со знаменателем и ненулевым числителем. Но — не корень иначе было бы корнем что противоречило бы максимальности . Тогда член со знаменателем не входит в разложение значит члену с таким знаменателем слева не с чем сократиться — но он не входит в правую часть — противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Итак, мы доказали, что если у многочлена есть комплексные корни, то в цепь этого корня входят числа 0 и 1, то есть выполняется равенство для какого-то целого . Если же у нет комплексных корней, то он - ненулевая константа, то есть и — многочлены, тогда их разность не может равняться

Осталось показать, что все значения вида где подходят. Для достаточно взять функцию

и привести сумму к общему знаменателю, числитель взять в качестве а знаменатель — Для то же самое сделать с суммой

Введём обозначения для длин сторон:

Сделаем инверсию с центром и радиусом с симметрией относительно биссектрисы угла

Середины сторон прямоугольного треугольника и вершина его прямого угла образуют прямоугольник, значит, все четыре на одной окружности. Значит, при инверсии образ окружности — прямая. Легко посчитать, что эта прямая отсекает от лучей и отрезки длины и соответственно, то есть симметрична относительно биссектрисы угла Поэтому гипотенуза и окружность Эйлера треугольника переходят друг в друга.

Касательная из к вписанной окружности равна её радиусу а касательная из к вневписанной окружности равна полупериметру Таким образом, их произведение — площади треугольника Итак, Поэтому вписанная и вневписанная окружности треугольника переходят друг в друга.

Следовательно, переходит в а переходит в Угол переходит в угол значит, они равны.

Заполним табличку: в клетке запишем, на какое максимальное число Вася может гарантированно к концу игры умножить имеющуюся у него сейчас сумму, если сейчас в ящике осталось черных и красных шаров. Легко понять, что стоит с краю: если уже не осталось черных шаров, то Вася может смело ставить все деньги на красный шар, соответственно увеличивая капитал в раз за каждый из оставшихся красных шаров. Аналогично если не осталось красных. Это и отмечено в таблице ниже.

Теперь поймем, что должно стоять в клетке если мы уже знаем, что в клетках и стоят числа и соответственно. Пусть для определенности

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

Теперь поймём, сколько же Вася должен ставить. Ставить он должен на тот цвет, выпадание которого приводит в клетку с числом напомним, в противном случае если этот цвет выпадет, Вася не сможет увеличить свой капитал более чем в раз, а мы строим стратегию лучше. Для определенности обозначим количество Васиных денег через и пусть он поставит денег на цвет, выпадение которого приводит в клетку с числом Тогда если выпал этот цвет Вася оказался в этой клетке имея денег, соответственно закончит игру, имея не менее денег (и не может гарантированно иметь больше). Если же выпал цвет, приводящий в клетку с числом Вася попал туда, имея денег, значит закончит игру, имея не меньше денег (и не может гарантированно иметь больше). Итак, гарантированный минимум при этой стратегии есть Поскольку первая из функций под минимумом возрастающая по , а вторая — убывающая, максимум минимума достигается при значении для которого функции принимают одно значение. Имеем

То есть

Иными словами, в интересующей нас клетке должно стоять число

Пользуясь этой формулой и значениями в клетках на краях, заполним всю табличку:

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

Задумаемся, а существует ли такое Условие равносильно квадратному уравнению в остатках(в этом абзаце все сравнимости по модулю 7):

Или можно было просто перебором остатков, благо их всего 7, убедиться, что любой из 3 и 5 подходят.

Что же нам дает равенство Просится от обоих частей взять функцию а затем воспользоваться условием задачи. Имеем:

Чтобы подчеркнуть полученное, обозначим и выбросим среднюю часть:

Отсюда следует (далее все сравнимости будут по модулю 11)

Отметим что это именно следствие, а не равносильность. Выясним, имеет ли сравнимость решения, действуя стандартно А извлекается ли квадратный корень из -3 по модулю 11? Заметим что и Мы перебрали все остатки, среди квадратов не нашлось -3, значит корень не извлекается, значит уравнение не имеет решений.

Итак, требуемой функции не существует.

Во-первых, докажем что Для этого полезно доказать более сильное утверждение: для произвольной фигуры из клеток количество квадратов в семействе, таком что все квадраты лежат в фигуре и для любого квадрата найдется клетка, покрытая только им, не превосходит Рассмотрим два случая: для семейства найдется клетка покрытая четырьмя квадратами, и случай, когда такой клетки не найдется.

Если такая клетка нашлась, то рассмотрим четыре покрывающих ее квадрата. Они образуют квадрат с клеткой в центре. И поскольку в каждом из четырех квадратов должна быть клетка, покрытая только им — это четыре угловые клетки квадрата поскольку все остальные покрыты хотя бы дважды. Но тогда никакой другой квадрат из семейства не покрывает клетки квадрат иначе он покрывает и угловую клетку, а она должна быть покрыта только один раз. Итак, все остальные квадраты лежат в множестве площади В этот момент доказательства еще не поздно решить, что на самом-то деле мы ведем индукцию по :), благо база тривиальна. Итак, всего квадратов в семействе оказывается не больше

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

Теперь построим пример, доказывающий, что следовательно неравенство при неверно при всех достаточно больших

Возьмем бесконечную клетчатую плоскость и покрасим ее в два цвета следующим образом: выберем одно из двух направлений диагонали, покрасим все клетки каждой диагонали в один цвет: две диагонали в белый, следующие две в черный и так далее с периодом Теперь выберем квадрат в который черных клеток попало не меньше чем белых, то есть хотя бы Теперь на каждую черную клетку внутри квадрата положим квадрат так, чтобы кроме этой черной клетки квадрат содержал только белые (это можно сделать единственным образом). Удалим все квадраты частично вылезшие за границы квадрата их не больше Требуемое семейство построено.

Для начала докажем, что на делятся те и только те числа Фибоначчи, номер которых делится на Докажем это по индукции. База: Первое число Фибоначчи, кратное — это которое является числом Фибоначчи.

Переход: Пусть этот факт был верен для всех чисел Фибоначчи с номерами от до Докажем, что он верен для чисел от до Пусть число с номером имело остаток от деления на Тогда числа с номерами будут иметь следующие остатки:

Теперь докажем, что на делятся те и только те числа Фибоначчи, номер которых делится на Доказательство аналогично.

Следовательно, если число Фибоначчи делится на то его номер делится на Значит его номер делится на а значит, само число обязано делиться на Значит оно не может быть равно натуральной степени числа