|
ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 48]
В Швамбрании N городов, каждые два соединены дорогой. При этом дороги
сходятся лишь в городах (нет перекрёстков, одна дорога поднята эстакадой над
другой). Злой волшебник устанавливает на всех дорогах одностороннее движение
таким образом, что если из города можно выехать, то в него нельзя вернуться.
Доказать, что
Решениеа) Занумеруем города в произвольном порядке и для каждой пары городов оставим направление движения от меньшего номера к большему. б) Повесим на город A номер, равный количеству городов, из которых ведёт путь в A. Очевидно, все номера разные, поэтому они пробегают все значения от 0 до N – 1. в) Единственный способ – обходить города от большего к меньшему в соответствии с установленной нумерацией. г) Число способов нумерации равно числу перестановок из N элементов.
ПодсказкаЕсли расстановка хорошая, то числа в ряду можно раскрасить в девять цветов так, чтобы числа каждого цвета шли в порядке возрастания.Решение1) Докажем, что если расстановка хорошая, то числа в ряду можно раскрасить в девять цветов так, чтобы числа каждого цвета шли в порядке возрастания. Действительно, будем красить числа слева направо, используя каждый раз такой цвет с наименьшим номером, что последнее покрашенное в этот цвет число меньше текущего. Предположим, что девяти цветов не хватило. Мы не можем покрасить очередное число в девятый цвет, так как в девятый цвет уже было покрашено большее число. Оно не было покрашено в восьмой цвет, поскольку до него встретилось большее число, покрашенное в восьмой цвет. И так далее. Получается 10 чисел, которые идут в порядке убывания. 2) Расстановка чисел от 1 до n вместе с такой раскраской в девять цветов, что последовательность чисел каждого цвета возрастает, полностью определяется цветом каждого числа от 1 до n и цветом каждого места в ряду. Числа от 1 до n можно раскрасить в 9 цветов 9n способами. И столькими же способами можно раскрасить в 9 цветов n мест, на которые эти числа будут расставлены. Таким образом, число хороших расстановок не превосходит 81n.
РешениеУпорядочим числа каждого цвета по возрастанию. А красные числа ещё и разобьём на две части: первые 25 назовём малыми, а следующие 25 – большими. Докажем, что можно взять в качестве k-й четверки k-е жёлтое и k-е зелёное числа и из красных k-е малое и k-е большое.Действительно, k-е жёлтое число больше одного красного числа из своей тройки и из всех троек с меньшими жёлтыми числами, то есть больше хотя бы k красных чисел. Значит, оно больше k-го малого красного числа. С другой стороны, k-е жёлтое число меньше одного красного числа из своей тройки и из всех троек с большими жёлтыми числами, то есть меньше хотя бы 25 – (k – 1) красных чисел. Значит, оно меньше k-го большого красного числа. Те же рассуждения справедливы для k-го зелёного числа. Ответобязательно.
В классе 30 учеников, и у каждого из них одинаковое число друзей среди одноклассников. Каково наибольшее возможное число учеников, которые учатся лучше большинства своих друзей? (Про любых двух учеников в классе можно сказать, кто из них учится лучше; если A учится лучше B, а тот – лучше C, то A учится лучше C.) Решение Учеников, которые учатся лучше большинства своих друзей, назовём хорошими. Пусть n – число хороших учеников, k – число друзей у каждого ученика. Докажем, что n ≤ 25. Для этого разберём два случая. Пусть пара учеников является парой друзей, если их номера расположены одним из трёх способов: а) в соседних строках и в разных столбцах; б) в одном столбце и один из номеров при этом находится в нижней строке; в) в верхней строке. При этом, как нетрудно проверить, все требуемые условия выполнены. Ответ25 учеников.
ПодсказкаЗаметьте, яблоки 1-го сорта есть только в корзине Д.РешениеПоскольку, яблоки 1-го сорта есть только в корзине Д, ее следует поставит первой. Яблоки 2-го сорта есть только в корзине В — ее поставим второй. Аналогично, корзина Г может быть только пятой, а третье и четвертое места займут корзины А и Б, причем, в любом порядке. Итак, задача имеет два решения: либо ДВАБГ, либо ДВБАГ.
Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 48] |
|
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|
|