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

Предположим противное. Тогда сумма всех чисел в тетрадке равна

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Первое решение на самом деле дает оценку на человека, второе — даже на человек.

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

Если Маша одна, то она танцевала два раза с Витей и два раза с единственным Пашей. Но тогда Паша танцевал с Полинами раза, а Полины с ним — хотя бы раза. Противоречие.

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

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

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