Тема НадЭн (Надежда энергетики)

Логика, комбинаторика и комбигео на Энергетике

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

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

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

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

Подтемы раздела надэн (надежда энергетики)

Решаем задачи

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

Задача 1#121577

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

Источники: Надежда Энергетики - 2025, 11.4(см. www.energy-hope.ru)

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

Подсказка 1

Давайте посчитаем количество способов попасть на конкретную клетку с номером k. Назовем это число Nₖ. Как его как можно проще выразить или посчитать?

Подсказка 2

Nₖ = Nₖ₋₁ + Nₖ₋₂. Теперь мы можем предположить, что изначально мы стояли на клетке с номером k, и явно записать через N количество вариантов для нашего пути.

Подсказка 3

Если всё будет посчитано правильно, то необходимо будет найти максимум у выражения Nₖ*N₂₀₂₅₋ₖ₊₁. Но сравнивать между собой такие числа сразу при всех k неудобно, значит, надо с чем-то одним. Можно выдвинуть гипотезу об ответе, какую?

Подсказка 4

Можно сравнить указанное выше число с N₂₀₂₅. Выдвигаем гипотезу о конце полосы!

Подсказка 5

Доказать неравенство можно как комбинаторно, так и по индукции, используя равенство, которое мы получили для Nₖ.

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

Пусть $N k$ — количество способов попасть на $k−$ ю по счету клетку. Туда топотун может попасть двумя способами: с клетки $k− 1$ либо $k− 2.$ Поэтому

Nk = Nk−1+ Nk−2

Если задать клетке, на которой стоит топотун, номер 1, то $N =1, 2$ $N =2. 3$

Таким образом, количество ходов задается хорошо известной последовательностью чисел Фибоначчи (начиная со второго).

Если топотун начинает с клетки с номером $k,$ то количество способов дойти до клетки с номером $L= 2025$ равно $N . L−k+1$ Количество способов дойти от клетки с номером $L= 2025$ до первой клетки (пройти всю полосу) составляет $NL,$ а количество способов вернуться с клетки номер один на клетку с номером $k$ равно $Nk.$ Общее количество вариантов есть $NL−k+1⋅NL ⋅Nk.$ Если же движение начинается из конца полосы, то общее количество вариантов есть $NL ⋅NL.$

Таким образом, необходимо найти максимум по параметру $k$ выражения

Nk⋅NL−k+1

(для $L = 2025$ ) и сравнить его с $N . L$

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

Nk⋅NL−k+1 < NL

1 вариант. Рассмотрим выражения $N ⋅N k L−k+1$ и $N L$ как количество способов передвинуться по полосе. Первое из них соответствует количеству способов переместиться на $L −$ ю клетку вправо, но с обязательным посещением

клетки с номером $k.$ Второе $(N ) L$ есть общее количество способов переместиться на такое же количество клеток, которое включает в себя как варианты с посещением клетки с номером $k,$ так и варианты с перепрыгиванием этой клетки.

Следовательно, $NL > Nk ⋅NL −k+1.$

2 вариант. Перепишем доказываемую формулу в виде

Nk ⋅Nm <Nk+m −1

и докажем ее индукцией по $k$ при фиксированном $m.$

Базу проверим для $k =2.$ $N2 ⋅Nm =1⋅Nm < N2+m− 1.$

Теперь рассмотрим значение параметра $k+ 1$ в предположении, что для всех предыдущих значений $k$ неравенство верно.

N(k+1)+m−1 = Nk+m−1 +Nk+m −2 > Nk⋅Nm + Nk−1⋅Nm =(Nk +Nk−1)Nm = Nk+1⋅Nm

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

Ответ:

При начале движения из любого конца полосы

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 2#87528

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

Источники: Надежда энергетики - 2024, 11.1 (см. www.energy-hope.ru)

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

Подсказка 1

А что если не было бы условия на два дня голодовки? Сколько способов было бы?

Подсказка 2

Нам нужно выбрать всего 4 дня из 10, а остальные будут обжорными. А как посчитать количество способов, которые не подходят под условие?

Подсказка 3

Нам нужно вычесть способы, в которых есть хотя бы 3 дня подряд голодовки. Много ли таких случаев?

Подсказка 4

Разберите случаи: когда у нас есть 3 дня подряд голодовки и 1, не стоящий рядом с ними. И второй случай: все 4 дня голодовки стоят рядом

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

Посчитаем сначала общее количество способов распределить дни без учёта условия. Заметим, что нам нужно выбрать 4 голодных дня, остальные сразу станут обжорными. Значит, их количество

4 10⋅9⋅8⋅7 C10 =---4!---= 210

Теперь посчитаем способы, которые нам не подходят под условия, чтобы вычесть их. Понятно, чтобы не выполнялось условие задачи нужно иметь хотя бы 3 голодных дня подряд, но, т.к. голодных дней всего 4 возможно два варианта:

1) У нас 3 голодных дня подряд и 1 голодный, не стоящий с ними рядом. Будем воспринимать эти 3 дня как 1, назовём его большой голодный день, т.е. теперь у нас будет 8 дней и мы распределяем большой голодный день и голодный день так, чтобы они не стояли рядом. Если большой голодный стоит первым или последним, то у обычного есть 6 вариантов, в иных случаях у него их 5. В итоге

2⋅6+ 6⋅5= 42

2) У нас 4 голодных дня подряд. Количество таких способов равно количеству способов выбрать место для первого голодного дня, оно равно 7.

В итоге количество способов распределения, подходящих под условия равно

210 − 42− 7= 161

Ответ: 161

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

Задача 3#71014

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

Источники: Надежда энергетики-2023, 11.1 (см. www.energy-hope.ru)

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

Подсказка 1

Нас просят найти количество попарных пересечений! Для начала давайте разберемся, а когда образуется одно попарное пересечение?

Подсказка 2

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

Подсказка 3

Первые два дома нужно выбрать из 6, а вторые два из 8. То есть, это просто число сочетаний из 6 по 2 и число сочетаний из 8 по 2!

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

Возьмем произвольную пару домов на одной стороне улицы и произвольную пару на другой. Они являются вершинами выпуклого четырехугольника (поскольку две стороны четырехугольника, идущие от каждой выбранной пары, лежат по одну сторону прямой, т.е. углы не превосходят $∘ 180$ ), следовательно, его диагонали пересекаются.

Каждое попарное пересечение теней (кабелей) является точкой пересечения диагоналей такого четырехугольника. Таким образом, осталось найти их количество, которое равно произведению способов выбрать пару домов на каждой стороне улицы.

C26 ⋅C28 = 420.

Ответ: 420

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

Задача 4#76464

Охотник Пулька для своей собаки Бульки заказал на АлиЭкспресс три куля собачьего корма. Наутро после доставки один куль оказался съеден. Под подозрение попали четверо, и Незнайке удалось установить следующее.

(1) Если алиби Пончика истинно, то Сиропчик также имеет алиби.

(2) Если Пончик ел корм, то либо Сиропчик, либо Авоська тоже ел корм (либо оба вместе).

(3) Из двух показаний: «Авоська ел корм», «Пончик не ел, но при этом ел Небоська» - хотя бы одно истинное.

(4) Если Небоська ел корм, то также ел либо Авоська, либо Сиропчик (либо оба вместе).

Кого из подозреваемых Незнайка может гарантированно обвинить в поедании за ночь целого куля собачьего корма?

Источники: Надежда энергетики-2022, 11.5 (см. www.energy-hope.ru)

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

Подсказка 1

Начнём с рассмотрения третьего пункта. Условие на авоську мы никак не можем связать с другими фактами, так что давайте предположим, что Небоська ел, а Пончик нет. Тогда надо найти следствия этих фактов из других пунктов и сопоставить их друг с другом. Что мы можем сказать теперь?

Подсказка 2

Да, из 4 мы знаем, что вместе с Небоськой также ели Авоська и Сиропчик, но из 1 нам известно, что если Пончик не ел, то и Сиропчик тоже. Тогда получается, что первое условие из 3 в любом случае выполняется

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

Начнем с (3). Пусть Авоська не ел корм. Тогда Пончик не ел, а Небоська ел. Из (4) получаем, что либо Авоська ел, либо Сиропчик. При сделанном предположении это означает, что ел Сиропчик. Но из (1) следует, что Сиропчик не ел корм, т.к. Пончик не ел. Получено противоречие. Следовательно, Авоська виновен (корм ел).

Рассмотреть все варианты для трех оставшихся подозреваемых,


	Авоська	Небоська	Пончик	Сиропчик

1	ел	ел	ел	ел

2	ел	ел	ел	нет

3	ел	ел	нет	ел	невозможно в силу (1)

4	ел	ел	нет	нет

5	ел	нет	ел	ел

6	ел	нет	ел	нет

7	ел	нет	нет	ел	невозможно в силу (1)

8	ел	нет	нет	нет

Видно, что каждый из подозреваемых мог как есть, так и не есть корм.

Ответ: Авоська

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

Задача 5#108271

При обработке числовых данных часто приходится вычислять среднее арифметическое

S(x,y)= (x +y)∕2

и решать уравнения, содержащие среднее арифметическое. Найдите все конечные (состоящие из конечного числа элементов) числовые множества $X$ такие, что для любых $a$ и $b$ из $X$ множество $X$ содержит корень $x$ уравнения

S(a,x)=b.

Источники: Надежда Энергетики - 2020, 11.4 (см. www.energy-hope.ru)

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

Подсказка 1

Давайте для начала попробуем разобраться на примере очень маленьких множеств.

Подсказка 2

Подходит ли одноэлементное множество?

Подсказка 3

А давайте предположим, что у нас есть хотя бы 2 различных элемента. Какому равенству будет удовлетворять x?

Подсказка 4

x = 2a - b. То есть мы только что построили новый элемент нашего множества. Давайте строить дальше, используя найденные новые элементы множества ;)

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

Имеем

S(a,x)= b⇔ x= 2b− a. (1)

Требуемым в условии задачи свойством обладает любое одноэлементное множество

X = {a}, a∈ (− ∞;∞ ), (2)

так как $S(a,a)= a.$

Допустим далее, что множество $X$ содержит по крайней мере два различных элемента $c,d,$ причем $c< d$ (без ограничения общности). Для уравнения $S(d,x)= c$ находим, согласно (1), $x =2c− d.$ Затем для уравнения $S(d,x)= 2c− d$ получаем $x= 4c− 3d,$ после чего рассматриваем уравнение $S(d,x)= 4c− 3d$ и получаем $x= 16c− 15d.$ Продолжая таким же образом, получаем последовательность решений

c,2c− d,4c− 3d,16c− 15d,... (3)

Покажем, что все её члены $xn =2nc− (2n − 1)d, n =0,1,2,...$ попарно различны. Если допустить, что $xn =xm$ при $n ⁄=m,$ то, преобразуя равенство, получим $(2m − 2n)c= (2m − 2n)d,$ откуда $c= d,$ это невозможно. Итак, множество $X$ содержит бесконечное подмножество — последовательность (3), следовательно, множество $X$ бесконечно.

Ответ:

в точности все одноэлементные множества $X ={a},a∈(−∞; ∞).$