Каталог по источникам

Задачи

Страница: << 16 17 18 19 20 21 22 >> [Всего задач: 110]

Задача 60442 (#02.108)

Темы:	[	Формула включения-исключения	]
	[	Раскладки и разбиения	]
	[	Правило произведения	]
	[	Сочетания и размещения	]

Сложность: 3+
Классы: 8,9,10

Сколькими способами можно расселить 15 гостей в четырёх комнатах, если требуется, чтобы ни одна из комнат не осталась пустой?

Решение

Без указанного ограничения есть 4¹⁵ способов. В 3¹⁵ из них первая (вторая, третья, четвертая) комната будет пуста. В 2¹⁵ способов будет пуста фиксированная пара комнат, и по одному способу, когда три фиксированные комнаты будут пусты. По формуле включения-исключения (см. задачу 60435) имеется 4¹⁵ – 4·3¹⁵ + 6·2¹⁵ – 4 способа, когда все комнаты непусты.

Ответ

4¹⁵ – 4·3¹⁵ + 6·2¹⁵ – 4 способа.

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

Задача 58107 (#02.109-110)

Темы:	[	Принцип Дирихле (площадь и объем)	]
	[	Формула включения-исключения	]
	[	Сочетания и размещения	]
	[	Перегруппировка площадей	]
	[	Доказательство от противного	]

Сложность: 3
Классы: 9,10

а) В квадрате площади 6 расположены три многоугольника площади 3. Докажите, что среди них найдутся два многоугольника,
площадь общей части которых не меньше 1.
б) В квадрате площади 5 расположено девять многоугольников площади 1. Докажите, что среди них найдутся два многоугольника,
площадь общей части которых не меньше ¹/₉.

Решение

а) Согласно задаче 58106 а) 6 = 9 – (S₁₂ + S₂₃ + S₁₃) + S₁₂₃, то есть S₁₂ + S₂₃ + S₁₃ = 3 + S₁₂₃ ≥ 3.
Поэтому одно из чисел S₁₂, S₂₃, S₁₃ не меньше 1.

б) Согласно задаче 58106 б) 5 ≥ 9 – M₂, т. е. M₂ ≥ 4. Так как из девяти многоугольников можно образовать пар, площадь общей части одной из этих пар не меньше M₂ : 36 ≥ ¹/₉.

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

Задача 60445 (#02.111)

Темы:	[	Формула включения-исключения	]
	[	Принцип Дирихле (площадь и объем)	]
	[	Сочетания и размещения	]

Сложность: 4
Классы: 10,11

В прямоугольнике площади 1 расположено пять фигур площади ½ каждая. Докажите, что найдутся
а) две фигуры, площадь общей части которых не меньше ³/₂₀;
б) две фигуры, площадь общей части которых не меньше ⅕;
в) три фигуры, площадь общей части которых не меньше ¹/₂₀.

Решение

Мы будем пользоваться обозначениями задачи 58106.

а) Согласно задаче 58106 б) 1 ≥ 5·0,5 – M₂, то есть M₂ ≥ 1,5. M₂ – сумма 10 площадей попарных пересечений пяти фигур, значит, площадь наибольшего из этих пересечений на меньше 0,15.
Замечание. Можно получить эту же оценку, рассуждая аналогично решению 2 задачи 58107 б).

б) Согласно задаче 58106 а) S = M₁ – M₂ + M₃ – M₄ + M₅. (*)
Применив ту же формулу включения-исключения к первой фигуре, получим S₁ = ∑ S_1i – ∑ S_1ij + ∑ S_1ijk – S₁₂₃₄₅.
Сложив пять подобных равенств для пяти фигур, получим M₁ = 2M₂ – 3M₃ + 4M₄ – 5M₅. (**)
Прибавив утроенное равенство (*), получим 3S = 2M₁ – M₂ + M₄ – 2M₅ ≥ 2M₁ – M₂ (M₄ ≥ 5M₅ ≥ 2M₅, поскольку S_ijkl ≥ S₁₂₃₄₅ = M₅ для каждой из пяти площадей вида S_ijkl).
Отсюда M₂ ≥ 2M₁ – 3M = 5 – 3 = 2. Значит, площадь наибольшего из 10 попарных пересечений пяти фигур не меньше 2 : 10 = 0,2.

в) Заменив формулу включения-исключения на неравенство из задачи 50106 б) (для m = 2), мы вместо (**) получим неравенство M₁ ≥ 2M₂ – 3M₃, откуда
3M₃ ≥ 2M₂ – M₁ ≥ 2·2 – 2,5 = 1,5. Значит, площадь наибольшего из 10 "тройных" пересечений пяти фигур не меньше 0,5 : 10 = 0,05.

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

Задача 60446 (#02.112)

Темы:	[	Покрытия	]
Темы:	[	Примеры и контрпримеры. Конструкции	]

Сложность: 4-
Классы: 9,10,11

Докажите, что в условии задач 60445 б) и в) числа ¹/₅ и ¹/₂₀ нельзя заменить большими величинами. >

Решение

На рисунке приведена схема покрытия прямоугольника фигурами, где цифры на отдельных частях показывают какими из фигур покрыты соответствующие участки. Эта схема показывает, что оценки ¹/₅ и ¹/₂₀ точны.

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

Задача 60447 (#02.113)

Темы:	[	Числа Каталана	]
Темы:	[	Мощность множества. Взаимно-однозначные отображения	]

Сложность: 4
Классы: 8,9,10,11

Сколько последовательностей {a₁, a₂, ..., a_2n}, состоящих из единиц и минус единиц, обладают тем свойством, что a₁ + a₂ + ... + a_2n = 0, а все частичные суммы a₁, a₁ + a₂, ..., a₁ + a₂ + ... + a_2n неотрицательны?

Решение

Установим взаимно однозначное соответствие между такими последовательностями и расстановками скобок в произведении x₀x₁...x_n (включая внешние скобки, например, (x₀((x₁x₂)x₃))). Именно, каждой открывающей скобке поставим в соответствие единицу, а каждому знаку умножения – минус единицу. Например указанной выше расстановке скобок в произведении x₀x₁x₂x₃ соответствует последовательность {1, –1, 1, 1, –1, –1}. Условие на неотрицательность частичных сумм выполнено, поскольку каждому знаку умножения соответствует своя пара скобок, "включающая" выражения, которые он перемножает.
Наоборот, по каждой последовательности можно построить расстановку скобок. Сначала, как указано выше, расставляем в пустой строке открывающие скобки и знаки умножения, затем восстанавливаем закрывающие скобки следующим образом. Пусть открывающей скобке в последовательности соответствует a_k = 1. Ищем наиболее "короткую" частичную сумму a_k + ... + a_m = 0 (такая, очевидно, найдется). При этом
a_k = –1, и мы ставим закрывающую скобку после знака произведения, соответствующего a_m. Затем уже легко вставить в полученную строку знаки неизвестных x₀, ..., x_n.

Ответ

C_n.

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

Страница: << 16 17 18 19 20 21 22 >> [Всего задач: 110]