Тема . ЮМШ (олимпиада Юношеской Математической Школы)

Комбинаторика на ЮМШ

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела юмш (олимпиада юношеской математической школы)

Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#69411

Общий сюжет. Пусть $f(a,b)$ — это количество способов пронумеровать клетки доски $a ×b$ номерами от 1 до $ab$ так, что каждая следующая находится в одной строке или столбце хотя бы с одной из предыдущих.

1. Найдите $f(3,2)$ .

2. Покажите, что

( ) f(a,a)≤ 100-a2! 2a

3. Докажите, что

( 2) f(a,a)≥ --a-!a 100⋅8

4. Найдите $f(a,2)$ .

Замечание. “Найти” означает выписать ответ в замкнутом виде.

Источники: ЮМШ-2023, 11 класс, 2 сюжет (см. yumsh.ru)

Подсказки к задаче

Пункт 1), подсказка 1

Чтобы начать расставлять числа, нужно как-то зафиксировать хоть что-то. Попробуйте зафиксировать 1 и понять, почему так можно делать. Как расставлять дальше?

Пункт 1), подсказка 2

Для 2 у нас есть 3 варианта. У каждого из них свои ограничения на следующие клетки, которые несложно разобрать по отдельности.

Пункт 2), подсказка 1

Попробуем расставлять числа по возрастанию, тогда будет проще рассуждать. Если мы поставим 1 в нижний левый угол, то какова доля клеток, куда мы можем поставить 2? А 3? Как выглядит общий случай?

Пункт 2), подсказка 2

Доля мест, куда мы можем поставить 2, не больше чем 2/а(почему?). Подумаем о том, как будет меняться такая доля с каждый новым числом.

Пункт 2), подсказка 3

С каждым новым числом общее коколичество свободных мест уменьшается на 1, а количество подходящих увеличивается максимум на (а-1). С помощью неравенства можно понять, до какого числа мы можем считать долю как (i+1)/a. Теперь у нас есть количество вариантов для каждого числа, каким тогда будет общее мест?

Пункт 2), подсказка 4

Произведение количества вариантов для каждого числа! Осталось лишь доказать, что такое число не больше 100 * (a^2)!/(2^a).

Пункт 3), подсказка 1

Отлично, количество вариантов уже посчитано в предыдущем пункте. Теперь нужно доказать, что это число больше того, что нас просят в этот раз. Попробуем доказать по индукции по а!

Пункт 3), подсказка 2

Базу проверить несложно. Теперь попробуем доказать, что (a+1)^(a-1) <= a^(a-2)*8a. Для этого попробуем преобразовать неравенство, тогда у нас получится найти связь с числом e!

Показать ответ и решение

1. Заметим, что при перестановке столбцов и строк в расстановке чисел она всё ещё будет удовлетворять условию. Значит, можно посчитать число способов с $1$ в нижнем левом угле и затем умножить его на $6$ . Разберём возможные позиции для двойки:

2

1

$=⇒ 4!$ (остальные числа можем поставить как угодно)



1	2

$=⇒ 3⋅3!$ (нам нельзя ставить $3$ в верхний правый угол. выбираем для неё одно из трёх других мест и расставляем остальные как угодно)



1		2

$=⇒ 3⋅3!$ (симметричен предыдущему случаю)

Тогда $f(3,2)= 6(4!+ 2⋅3⋅3!)= 360.$

2. Будем расставлять числа по возрастанию. Переставим столбцы и строки так, чтобы $1$ находилась в левом нижнем углу. Рассмотрим долю мест, на которые мы можем поставить $2$ . Эта доля $= 2(aa−2−1)1 ≤ 2a$ . Для $3$ эта доля будет $(a−1)+(aa−21−)2+(a−2)≤ 3a$ . И в общем случае: с каждым новым числом общее количество свободных мест уменьшается на 1, а количество подходящих увеличивается максимум на $(a− 1)$ . Сравним:

(i+-1)(a+-1)≤ i+1- a2− i a

что при $i≤ a$ верно.

Тогда общее количество мест

2 (a−-1)! (a)!aa−2

Докажем, что

2 (a−-1)! (a2)! (a )!aa−2 ≤ 100 2a

что равносильно

a a−2 2 ⋅(a− 1)!≤ 100a

По неравенству о средних:

a2 x(a− x)≤ 4

Тогда

2a⋅(a− 1)!≤ 8⋅1⋅(a − 1)⋅aa− 1 ≤ 100aa−2

что и требовалось.

3. Докажем, что

( 2) (a2)!(a−a−12)!-≥--a-!a a 100⋅8

что равносильно

a a−2 (a − 1)!⋅100⋅8 ≥ a

Базу $a= 2$ легко проверить

100⋅64≥ 1

По предположению индукции

----aa−2----≤ 1, (a− 1)!⋅100⋅8a

а для перехода надо доказать

-(a+-1)a−1-- (a)!⋅100⋅8a+1 ≤ 1

Тогда докажем

a−1 a−2 -(a+-1)-a+1 ≤----a------a, (a)!⋅100⋅8 (a− 1)!⋅100⋅8

что равносильно

(a+ 1)a−1 ≤ aa−2⋅8a ⇐⇒ (a-+1)a−1 ≤ 8 a

1a−1 (1+ a) ≤ 8

а это уже известное неравенство (можно оценить даже не числом 8, а числом Эйлера - числом $e$ ), которое тоже легко проверить по индукции для любого натурального $a.$

4. Будем расставлять числа по возрастанию. Пусть мы начали с какой-то из двух строк. Нам интересен первый момент, когда мы “перескочим” на другую, так как после этого остальные числа можно расставить как угодно.

			…	k	…

1	2	3	…		…

Пусть мы “перескочили” на числе $k +1$ . Посчитаем количество таких расстановок: мы выбираем одну из двух строк начальной, затем расставляем числа от $1$ до $k$ в этой строке, затем выбираем, куда поставить $k+ 1$ — для этого есть только $k$ способов, так как мы должны поставить его в один столбец с любым из $k$ чисел. Все остальные числа можем расставить как угодно:

2⋅a⋅(a− 1)⋅...⋅(a− k+ 1)⋅k ⋅(2a− (k +1))!

Таким образом,

∑a f(a,2)= 2⋅a⋅(a− 1)⋅...⋅(a− k+ 1)⋅k ⋅(2a− (k+ 1))!= k=1

∑a --a!-- =k=12⋅(a− k)! ⋅k⋅(2a− (k+ 1))!

Что делать с такой суммой не очень понятно, хочется выразить её через $Cnm$ — с ними мы умеем работать, то есть мы хотим получить выражение вида $(nn+!mm!)!$ :

f(a,2)= ∑a 2⋅--a!--⋅k⋅(2a− (k+ 1))!= k=1 (a− k)!

a a =2⋅a!(a− 1)!∑ -k(2a−-k−-1)! =2 ⋅a!(a − 1)!∑ kCa−1 k=1(a− 1)!(a− k)! k=1 2a−k−1

Осталось посчитать эту сумму. Распишем её:

a ∑ kCa−1 = Ca−1 +2Ca−1 + 3Ca−1 + ...+ aCa−1 k=1 2a−k−1 2a−2 2a−3 2a−4 a− 1

Пусть у нас есть $2a− 1$ игроков, которые упорядочены по убыванию своей силы. мы выбираем среди них команду из $a$ игроков и капитана, который должен быть сильнее всех игроков. С одной стороны, мы можем просто набрать команду из $a+ 1$ игроков и назначить капитаном самого сильного из них. Это же число способов можно посчитать по-другому: выберем самого сильного после капитана участника команды. Пусть он имеет номер $k+ 1$ (то есть сильнее него ровно $k$ человек). Тогда у нас есть $k$ способов выбрать капитана, и потом нам нужно набрать команду из $a− 1$ человека из $2a− k− 2$ . Получается, что

a ∑ kCa2−a1−k−1 = Ca2+a1 k=1

Ответ:

1. $360$

2. что и требовалось доказать

3. что и требовалось доказать

4. $a+1 C2a$

Нужна консультация? Задайте нам вопрос в чате.

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

Комбинаторика на ЮМШ

Специальные программы

Программалояльности v2.0

Крути рулеткуи выигрывай призы!

Бесплатное онлайн-обучение

Налоговые вычеты

Специальное предложениедля учителей

Вернём деньги за курсза твою сотку на ЕГЭ

Программалояльности v2.0

Крути рулеткуи выигрывай призы!

Бесплатное онлайн-обучение

Налоговые вычеты

Специальное предложениедля учителей

Вернём деньги за курсза твою сотку на ЕГЭ

Программа
лояльности v2.0

Крути рулетку
и выигрывай призы!

Специальное предложение
для учителей

Вернём деньги за курс
за твою сотку на ЕГЭ

Программа
лояльности v2.0

Крути рулетку
и выигрывай призы!

Специальное предложение
для учителей

Вернём деньги за курс
за твою сотку на ЕГЭ