Шаг за шагом

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

1) Рядом с 2 стоит 3. Тогда рядом с 3 может стоять только 1. Ее сосед — это только 4 и рядом с 4 может встать только 6.

2) Рядом с 2 стоит 4. Тогда рядом с 4 может стоять или .

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

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

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

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

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

База для : Квадрат без угловой клетки является уголком из трёх клеток, поэтому база очевидна.

Переход:

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

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

Например, подходит . При этом , , , то есть это действительно три точных квадрата.

Попробуем привести пример, в котором стороны квадратов целые. Тогда сначала нам надо отыскать точный квадрат, который можно представить в виде суммы двух точных квадратов. Это мы сделали в предыдущей задаче: . Теперь достаточно разрезать квадрат на одинаковых маленьких квадратиков, а из них сложить два квадрата: и .

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

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

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

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

В качестве ответа на первый вопрос подходит число . Число, равное сумме своих четырех различных делителей также существует, например, .

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

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

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

Можно сделать хитрее, и воспользоваться тем же равенство . Проблема в том, что слева ни одно число нельзя заменить на сумму двух квадратов. Исправим это, домножив обе части на , получим . Теперь уже можно записать так: , поэтому этот квадрат можно заменить на сумму двух квадратов и подставить в равенство: .

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

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

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

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

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

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

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

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

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

Комментарий. Таким образом можно получить пример на любое количество чисел.

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

Теперь заметим, что у нас осталась еще одна цистерна с литрами бензина. Сольем бензин в ней с бензином в цистерне с литрами бензина, получим ровно литров бензина — как раз столько, сколько требуется.

Вот эти представления:

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

Пронумеруем людей числами от до . Заметим, что при могут созвониться сначала и , потом и , потом и , и в конце и . Тогда все будут знать все новости. Пусть мы умеем организовывать созвон для человека. Научимся организовывать для . Сначала пусть созвонятся и . Теперь знает две новости. Далее организуем созвон для человека. А потом могут созвониться опять и . Легко видеть, что все будут знать все новости, а количество звонков стало равно .