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

Кружок 6 класса

Занятие 3 (08.10.2011). Города и дороги

1.

В некоторой стране а) 6; б) 20 городов, любые два из которых соединены дорогой. Сколько всего дорог в этой стране? в) Докажите, что если число городов равно n, то дорог ^{n(n − 1)}/₂.

Ответ Решение

Ответ. а) 15; б) 190.

Решение. Докажем «в)». Посчитаем пары городов. На первое место можно выбрать n городов, на второе уже n − 1 (так как город не может быть соединен сам с собой). Следовательно, всего пар n(n − 1). Заметим, что число дорог в два раза меньше числа пар, так как пару город А — город Б мы посчитали 2 раза (А-Б и Б-А). Значит, надо поделить на 2. Пункты А и Б получаются подсановкой в формулы.

2.

В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник заметил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр-названий делится на три. Можно ли добраться из города 1 в город 9?

Ответ Решение

Ответ. Нет, нельзя.

Решение. По признаку делимости на 3 число делится на 3 только в том случае, когда сумма его цифр делится на 3. 1 не делится на 3. Следовательно, этот город может быть соединен только с городом, который на 3 тоже не делится. (Иначе получится, что сумма цифр не делится на 3, так как сумма кратного трем и не кратного не делится на 3). 9 делится на 3. Поэтому добраться из города в город нельзя.

3.

В государстве 100 городов, и из каждого выходит по 4 дороги. Сколько всего дорог в государстве?

Ответ Решение

Ответ. 200.

Решение. В государстве 100 городов, из каждого выходит по 4 дороги. Значит, если мы умножим 100 на 4, то получим число дорог, умноженное на 2, так как каждую дорогу мы посчитали 2 раза, ведь дорога соединяет 2 города. Следовательно, число дорог равно ^{100· 4}/₂ = 200.

4.

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

Решение

Решение. План города может быть, например, таким.

5.

Любознательный турист хочет прогуляться по улицам Старого города от вокзала (точка A на плане) до своего отеля (точка B). Он хочет, чтобы его маршрут был как можно длиннее, но дважды оказываться на одном и том же перекрёстке ему неинтересно, и он так не делает. Нарисуйте на плане самый длинный возможный маршрут и докажите, что более длинного нет.

Решение

Решение. Один из возможных маршрутов туриста изображён на рисунке.

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

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

6.

В стране 96 городов, из которых 24 — «областные». Некоторые пары городов соединены между собой дорогами (но не более чем одной), причём любой путь по дорогам между двумя обычными городами, если он есть, проходит хотя бы через один «областной» город. Какое наибольшее количество дорог могло быть в этой стране?

Ответ Решение

Ответ. 2004.

Решение. Очевидно, что обычные города не соединены дорогами, иначе бы существовал путь не проходящий через областной город. Значит, максимальное число дорог в том случае, когда каждый обычный город соединен с каждым областным, и все областные соединены между собой. Нетрудно убедиться, что ответ в таком случае будет равен ^{24· 23}/₂ + (96 − 24)· 24 = 276 + 1728 = 2004.

7.

В чемпионате России по футболу участвуют 16 команд. Любые две команды играют друг с другом два раза: по разу на поле каждого из соперников.

а)

Какое максимальное и какое минимальное количество очков может набрать команда, участвующая в чемпионате России?

б)

Какое минимальное и какое максимальное количество очков могут набрать в сумме все команды? (В футболе за победу в матче даётся 3 очка, за ничью — 1 очко, за поражение — 0 очков.)

Ответ Решение

Ответ. а) 90 и 0 очков; б) 480 и 720 очков.

Решение. а) Ясно, что наибольшее число очков команда может набрать, когда все матчи выиграет, а минимальное, когда все матчи проиграет.

б) Если в матче одна из команд ожержит победу, то в сумме за матч будет разыграно 3 очка; если же ни одна из команд не выиграет, то в сумме будет разыграно два очка. Ясно, что можно добиться того, чтобы в каждом матче было разыграно 2 очка — каждый матч закончиться ничьей. Тогда будет разыграно всего 16·15·2 = 480 очков. Максимальное число будет разыграно, когда в каждом матче одна из команд выиграет. В этом случае будет разыграно 16·15·3 = 720 очков.

8.

В шахматном турнире приняло участие несколько человек. Каждый сыграл с каждым ровно одну партию. Оказалось, что все, кроме Гоши, набрали одинаковое количество очков. Докажите, что Гоша либо у всех выиграл, либо всем проиграл. (В шахматах за победу даётся 1 очко, за ничью — 1/2 очка, за поражению — 0 очков.)

Решение

Решение. Поменяем немного правила начисления очков: за победу будем давать 2 очка, а за ничью 1 очко. Ясно, что после такой замены все условия задачи сохранятся и каждый из участников наберет целое число. Будем считать, что в этом турнире всего участников было n. Тогда все участники в сумме набрали n(n − 1) очков. Пусть у тех участников, которые набрали равное число очков, по k очков, а у Гоши G очков. Тогда

n(n − 1) = k(n − 1) + G.

Заметим, что G кратно n − 1. Но всего максимум очков могло быть 2(n − 1) (n − 1 тур, в каждом максимум два очка). Значит, G = 0, n − 1 или 2(n − 1). В первом и третьем случае получим то, что нужно доказать, во втором получим n = k + 1, или k = n − 1, но тогда все, в том числе и Гоша, набрали n − 1 очко, но это противоречит условию задачи.