Рассуждения от противного

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

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

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

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

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

Способ 1. Предположим, что никакие двое не родились в один месяц. Тогда все человек родились в разные месяцы, значит, всего должно существовать хотя бы месяцев. Но месяцев всего , противоречие. Значит, какие-то двое первокурсников родились в один месяц.

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

Пронумеруем места, на которых лежат шарики, номерами от до . Предположим, что любые два соседних шарика разного цвета. Тогда цвета чередуются, и расстановка такая: …-К-С-К-С-…Таким образом, все шарики на нечетных местах одного цвета, а на четных другого. Но шарики с номерами и тогда одного цвета, и они лежат рядом, противоречие. Таким образом, какие-то два одноцветных шарика все-таки лежат рядом.

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

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

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

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

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

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

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

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

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

Предположим, что какому-то инопланетянину достались сразу три банана. Тогда он получил по банану и от Лосяша, и от Бараша, и от Пина.

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

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

и кто-то выбрал , , , а кто-то , , .

Рассмотрим два случая. Первый случай, когда тройку , , выбрал Лосяш. Тогда инопланетянин ниже, чем . В этом случае тройку , , выбрал Бараш, и тогда ниже, чем .

Второй случай, когда тройку , , выбрал Бараш. Тогда инопланетянин выше, чем , а инопланетянин выше, чем , так как тройку , , выбрал Лосяш, и в этой тройке самый высокий.

Заметим, что в обоих случаях мы получили, что кто-то из инопланетян и выше, чем , а кто-то ниже.

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

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

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

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

Чтобы у всех трех Маш были одноцветные тезки, они должны быть все одного цвета, аналогично все три Ани тоже должны быть одного цвета. Тогда Даши будут разного цвета.