В стране Пятнашка пятнадцать городов, каждый из
которых соединён дорогами не менее, чем с 7 другими.
Докажите, что из любого города можно добраться до любого
(возможно, проезжая через другие города).
Указание
Указание.Выберем два города, и проведём из них по
7 дорог. Докажите, что так как у нас всего 15
городов, то обязательно найдётся город,
в который ведут дороги из двух выбранных городов.
Если это так, то мы нашли дорогу, соединяющую
выбранные города, поэтому любые 2 города можно будет
соединить дорогами.
2.
В этой же Пятнашке решили построить железную дорогу
так, чтобы каждый город был соединён ровно с тремя другими.
Удастся ли пятнашцам осуществить этот проект?
УказаниеРешение
Указание.Посчитайте, сколько дорог нужно построить
пятнашцам.
Решение.Из каждого города выходит 3 дороги, всего 15 городов.
Каждая дорога соединяет ровно 2 города.
Значит, потребуется (3×5)/2 дорог, а столько
построить невозможно.
3.
Пятнашцам был предложен ещё один план
железнодорожной сети. Предлагалось построить железные дороги так, чтобы из
каждого города выходило по 1, 5, 7 или 11 дорог.
Осуществим ли такой план?
ОтветУказаниеРешение
Ответ.Такой план не существует.
Решение.Задача очень похожа на предыдущую.
Нам нужно построить
(1 + ... + 1 + 5 + ... + 5 + 7 + ... + 7 + 11 + ... + 11)/2
дорог. Сумма, состоящая из нечётного (15) числа
нечётных (1, 5, 7 и 11) слагаемых не может быть чётна.
Следовательно, числитель не делится на 2 и столько дорог построить
нельзя.
Указание.Задача очень похожа на предыдущую.
4.
Докажите, что число людей, когда либо живших и
живущих сейчас на Земле и сделавших нечётное число рукопожатий,
чётно.
Решение
Решение.Задача решается точно так-же,
как и предыдущая.
Будем считать, что люди это города из
предыдущей задачи. Если люди сделали рукопожатие,
то мы города, соответстующие этим людям
соединим дорогой (при этом два города может соединять
несколько дорог, если люди сделали несколько рукопожатий).
Посчитаем, сколько дорог нужно построить на этот раз.
Число дорог = (сумма дорог, которые выходят из каждого города)/2,
числитель этой дроби чётный только в том случае,
если число городов, из которых выходит нечётное число дорог,
чётно.
5.
В стране Сто было ровно сто городов. Какое
минимальное количество дорог нужно построить, чтобы из
каждого города можно было бы добраться до любого другого?
Ответ
Ответ.99
6.
Через сто лет в стране Сто из каждого города стало
выходить ровно 100 дорог (а городов стало больше). Из
каждого города можно добраться до любого другого. Одну
дорогу закрыли на ремонт. Докажите, что и теперь из любого
города можно добраться до любого другого.
Решение
Решение.Предположим, что теперь есть два города А и Б
такие, что из А никак нельзя добраться
до города Б.
Теперь у нас есть 2 группы городов: те, в кооторые
можно добраться из города А, и те, в которые можно
добраться из города Б. (Эти группы не содержат общих городов,
так как из города А в город Б доехать нельзя.)
Рассмотрим одну из этих групп
и посчитаем, сколько дорог в ней проходит.
Из одного города
выходят 99 дорог, а из всех остальных --- 100.
Тогда всего в этой группе (99 + 100 + 100 + ... + 100)/2 дорог.
Этого быть не может, так как (99 + 100 + 100 + ... + 100) нечётное
число.
7.
Сможет ли конь обойти доску 4×4, если из нее
вырезать угловые клетки?
8.
a) Докажите, что среди шести человек всегда есть
либо трое знакомых, либо трое незнакомых друг с
другом. b) На конференцию, которая проводилась на
русском, английском и французском языках,
приехали 17 ученых. Каждый разговаривал с каждым на
одном из этих языков. Докажите, что есть тройка
ученых, которые разговаривают друг с другом на
одном языке.
9.
Докажите, что для любого натурального числа
n число 4n - 1 делится на 3.
