МАЛЫЙ МЕХМАТ МГУ

Кружок 9-11 классов

Доказательство от противного

1.

Имеется 101 пуговица, каждая пуговица — одного из 11 цветов. Докажите, что среди этих пуговиц найдутся либо 11 пуговиц одного цвета, либо 11 пуговиц разных цветов.

2.

С числами можно выполнять следующие операции: умножать на два или произвольным образом переставлять цифры (нельзя только ставить нуль на первое место). Можно ли из 1 получить 74?

Примечание

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

3.

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

4.

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

5.

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

6.

Одиннадцать мальчиков и одиннадцать девочек сидят за круглым столом. Докажите, что у кого-то из них оба соседа — мальчики.

7.

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

8.

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

9.

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

10.

Можно ли во всех точках плоскости с целыми координатами записать некоторые натуральные числа (можно использовать не все числа) так, чтобы три точки с целыми координатами лежали на одной прямой тогда и только тогда, когда записанные в них числа имели общий делитель, больший единицы?