ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при поддержке
ЦПМ
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 48]      



Задача 97804

Темы:   [ Отношение порядка ]
[ Обход графов ]
[ Упорядочивание по возрастанию (убыванию) ]
[ Перестановки и подстановки (прочее) ]
Сложность: 4
Классы: 8,9,10

Автор: Коганов И.

В Швамбрании N городов, каждые два соединены дорогой. При этом дороги сходятся лишь в городах (нет перекрёстков, одна дорога поднята эстакадой над другой). Злой волшебник устанавливает на всех дорогах одностороннее движение таким образом, что если из города можно выехать, то в него нельзя вернуться. Доказать, что
  а) волшебник может это сделать;
  б) найдётся город, из которого можно добраться до всех, и найдётся город, из которого нельзя выехать;
  в) существует единственный путь, обходящий все города;
  г) волшебник может осуществить своё намерение N! способами.

Решение

  а) Занумеруем города в произвольном порядке и для каждой пары городов оставим направление движения от меньшего номера к большему.

  б) Повесим на город A номер, равный количеству городов, из которых ведёт путь в A. Очевидно, все номера разные, поэтому они пробегают все значения от 0 до  N – 1.

  в) Единственный способ – обходить города от большего к меньшему в соответствии с установленной нумерацией.

  г) Число способов нумерации равно числу перестановок из N элементов.

Прислать комментарий

Задача 34844

Темы:   [ Отношение порядка ]
[ Геометрическая прогрессия ]
Сложность: 5
Классы: 9,10

Натуральные числа от 1 до n расставляются в ряд в произвольном порядке. Расстановка называется плохой, если в ней можно отметить 10 чисел (не обязательно стоящих подряд), идущих в порядке убывания. Остальные расстановки называются хорошими. Докажите, что количество хороших расстановок не превосходит 81n.

Подсказка

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

Решение

1) Докажем, что если расстановка хорошая, то числа в ряду можно раскрасить в девять цветов так, чтобы числа каждого цвета шли в порядке возрастания. Действительно, будем красить числа слева направо, используя каждый раз такой цвет с наименьшим номером, что последнее покрашенное в этот цвет число меньше текущего. Предположим, что девяти цветов не хватило. Мы не можем покрасить очередное число в девятый цвет, так как в девятый цвет уже было покрашено большее число. Оно не было покрашено в восьмой цвет, поскольку до него встретилось большее число, покрашенное в восьмой цвет. И так далее. Получается 10 чисел, которые идут в порядке убывания. 2) Расстановка чисел от 1 до n вместе с такой раскраской в девять цветов, что последовательность чисел каждого цвета возрастает, полностью определяется цветом каждого числа от 1 до n и цветом каждого места в ряду. Числа от 1 до n можно раскрасить в 9 цветов 9n способами. И столькими же способами можно раскрасить в 9 цветов n мест, на которые эти числа будут расставлены. Таким образом, число хороших расстановок не превосходит 81n.
Прислать комментарий


Задача 67268

Тема:   [ Отношение порядка ]
Сложность: 5
Классы: 8,9,10,11

Натуральные числа от 1 до 100 раскрашены в три цвета: 50 чисел – в красный, 25 чисел – в жёлтый и 25 – в зелёный. Известно, что все красные и жёлтые числа можно разбить на 25 троек так, чтобы в каждой тройке было два красных числа и одно жёлтое, которое больше одного красного и меньше другого. Аналогичное утверждение верно для красных и зелёных чисел. Обязательно ли все 100 чисел можно разбить на 25 четвёрок, в каждой из которых два красных числа, одно жёлтое и одно зелёное, при этом жёлтое и зелёное числа лежат между красными?

Решение

Упорядочим числа каждого цвета по возрастанию. А красные числа ещё и разобьём на две части: первые 25 назовём малыми, а следующие 25 – большими. Докажем, что можно взять в качестве k-й четверки k-е жёлтое и k-е зелёное числа и из красных k-е малое и k-е большое.

Действительно, k-е жёлтое число больше одного красного числа из своей тройки и из всех троек с меньшими жёлтыми числами, то есть больше хотя бы k красных чисел. Значит, оно больше k-го малого красного числа. С другой стороны, k-е жёлтое число меньше одного красного числа из своей тройки и из всех троек с большими жёлтыми числами, то есть меньше хотя бы 25 – (k – 1) красных чисел. Значит, оно меньше k-го большого красного числа. Те же рассуждения справедливы для k-го зелёного числа.

Ответ

обязательно.
Прислать комментарий


Задача 109564

Темы:   [ Отношение порядка ]
[ Задачи с неравенствами. Разбор случаев ]
[ Примеры и контрпримеры. Конструкции ]
[ Оценка + пример ]
Сложность: 5
Классы: 10

В классе 30 учеников, и у каждого из них одинаковое число друзей среди одноклассников. Каково наибольшее возможное число учеников, которые учатся лучше большинства своих друзей? (Про любых двух учеников в классе можно сказать, кто из них учится лучше; если A учится лучше B, а тот – лучше C, то A учится лучше C.)

Решение

  Учеников, которые учатся лучше большинства своих друзей, назовём хорошими. Пусть n – число хороших учеников, k – число друзей у каждого ученика. Докажем, что  n ≤ 25.  Для этого разберём два случая.
  1)  k ≥ 8.  Тогда пять худших учеников класса не являются хорошими.
  2)  k ≤ 7.  Лучший ученик класса является лучшим в k парах друзей, а любой другой хороший ученик – не менее, чем в  k+1/2  парах. Поэтому хорошие ученики являются лучшими не менее, чем в  k + (n – 1)·k+1/2  парах. Это число не может превышать числа всех пар друзей в классе, равного 15k. Отсюда   2k + (n – 1)(k + 1) ≤ 30k,   то есть   n – 1 ≤ 28·k/k+1 = 28 – 28/k+1 ≤ 28 – 28/8 = 24,5.  Значит, и в этом случае  n ≤ 25.
  Покажем, что n может равняться 25. Занумеруем учеников числами от 1 до 30 в порядке ухудшения успеваемости и расположим номера в таблице 6×5 так, как показано на рисунке.


  Пусть пара учеников является парой друзей, если их номера расположены одним из трёх способов:  а) в соседних строках и в разных столбцах;  б) в одном столбце и один из номеров при этом находится в нижней строке;  в) в верхней строке. При этом, как нетрудно проверить, все требуемые условия выполнены.

Ответ

25 учеников.

Прислать комментарий

Задача 98661

Темы:   [ Математическая логика (прочее) ]
[ Отношение порядка ]
Сложность: 2
Классы: 5,6

В пяти корзинах А, Б, В, Г и Д лежат яблоки пяти разных сортов. В каждой из корзин А и Б находятся яблоки 3 и 4 сорта, в корзине В — 2 и 3, в корзине Г — 4 и 5, в корзине Д — 1 и 5. Занумеруйте корзины так, чтобы в первой корзине имелись яблоки 1-го сорта (как минимум одно), во второй корзине — яблоки 2-го сорта и т.д.

Подсказка

Заметьте, яблоки 1-го сорта есть только в корзине Д.

Решение

Поскольку, яблоки 1-го сорта есть только в корзине Д, ее следует поставит первой. Яблоки 2-го сорта есть только в корзине В — ее поставим второй. Аналогично, корзина Г может быть только пятой, а третье и четвертое места займут корзины А и Б, причем, в любом порядке. Итак, задача имеет два решения: либо ДВАБГ, либо ДВБАГ.
Прислать комментарий


Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 48]      



© 2004-... МЦНМО (о копирайте)
Пишите нам