Решения-контрольной-по-комбинаторике-1-вариант.md

+***Вариант 1***
+---------------------------------
+**Задача 1**
+*В образцовом детском саду известно всего 7 плохих слов, причем из 380 детей каждый знает хотя
+бы одно, но никто не знает всех. Докажите, что найдутся 4 человека, знающие один и тот же набор плохих
+слов.*
+
+Решение:
+Посчитаем количество возможных комбинаций плохих слов, которые может знать ребёнок в этом детском саду. Каждое слово из 7 ребёнок может знать, а может и не знать. 
+Значит всего их $`2^7`$. Но 2 варианта -- когда ребёнок знает все слова и ни одного нам не подходят -- их надо вычесть. Итого $`2^7-2 = 126`$ вариантов. Но детей у нас 380. 
+Значит по принципу Дирихле (если мы будем раздавать каждому ребёнку одинаковое минимальное количество наборов плохих слов) мы раздадим один и тот же набор больше чем трём детям: 
+$`380 > 126*3 = 178`$
+
+**Задача 2**
+*Рассмотрим все бесконечные последовательности натуральных чисел, которые начиная с некоторого
+места становятся постоянными (т. е. такие последовательности $`(an)`$, что $`∃N ∈ \N ∀n > N (an = aN ))`$.
+Является ли множество таких последовательностей счетным?*
+
+Решение:
+Зафиксируем какое-нибудь $`n ∈ \N`$. И рассмотрим $`A_N`$ -- множество всех последовательностей, которые становятся постоянными начиная с члена с номером $`n`$. (Т.е. $`n`$ - номер цифры, за которой все цифры такие же как она сама). Множество таких последовательностей конечно. Потому что каждую такую последовательность можно записать как, $`n`$ упорядоченных чисел от 0 до 9. Множество таких последовательностей чисел является подмножеством декартова произведения целых чисел на самих себя $`n`$ раз, значит оно счётно. 
+
+При этом каждому множеству $`A_n`$ последовательностей можно однозначно сопоставить номер $`n`$, с которого последовательности этого множества постоянны. Таким образом, раз для множеств $`A_n`$ существует биекция в $`N`$ их счётно. Но и каждое такое множество счётно, то и множество всех последовательностей, из которых состоят наши $`A_n`$ счётно, т.к. объединение не более чем счётного множества не более чем чётных множеств не более чем счётно.
+ 
+*Решение с идеей про предел от Максима Лагус:*
+Заметим, что все такие бесконечные последовательности сходятся к $`a_n`$ по определению предела последовательности. По теореме из курса мат анализа мы знаем, что все члены последовательности лежат в любой $`\epsilon`$ окрестности предела кроме, может быть, конечного числа членов. Значит, что в любой последовательности из задачи лишь конечное число элементов не равно $`a_N`$.
+
+Пойдём дальше. Зафиксируем какое-нибудь $`N ∈ \N`$. Пусть $`{a_1, a_2, ... , a_{N-1}}`$ -- упорядоченное множество элементов последовательности не равных $`a_N`$. Как мы доказали выше -- это множество конечно. Зададим оставшиеся члены последовательности как один последний элемент: $`{a_1, a_2, ... , a_{N-1}, a_N}`$. Множество таких множеств -- подмножество декартова произведения множества целых чисел самого на себя $`N`$ раз. А значит множество последовательностей -- счётно. 
+
+При этом каждому множеству последовательностей  длинны $`N`$ можно однозначно сопоставить номер $`N`$, с которого последовательности этого множества постоянны. Таким образом, раз для этих множеств существует биекция в $`N`$ их счётно. Но и каждое такое множество счётно, то и множество всех последовательностей, из которых состоят наши счётно, т.к. объединение не более чем счётного множества не более чем чётных множеств не более чем счётно.
+
+**Задача 3**
+*Не пользуясь таблицами истинности приведите к СКНФ и СДНФ следующую формулу: $`(((¬P ⊃ ¬Q) ⊃ R) ⊃ ((Q ⊃ ¬R) ⊃ P))`$*
+
+Решение:
+
+<img src="/uploads/e3639f840c5b2ff30e4b4b668953307f/photo_2021-11-01_15-47-40.jpg"  width="50%" height="50%">
+
+**Задача 4**
+*Вычислите сумму $`C^2_{2n} + 2C^4_{2n} + 3C^6_{2n} + ... + nC^{2n}_{2n}`$. (В записи ответа допустимы только четыре арифметические операции, возведение в степень, взятие факториала и стандартных комбинаторных величин, там не должно содержаться многоточий и число использованных операций не должно зависеть от n.)*
+
+Решения:
+
+**1)** $`kC^{2k}_{2n} = \frac{1}{2}(2kC^{2k}_{2n}) =  \frac{1}{2}(2nC^{2k-1}_{2n-1}) = nC^{2k-1}_{2n-1}`$
+Значит $`C^2_{2n} + 2C^4_{2n} + 3C^6_{2n} + ... + nC^{2n}_{2n} = \sum\limits^n_{k=1} kC^{2k}_{2n} = \sum\limits^n_{k=1} nC^{2k-1}_{2n-1} = n 2^{(2n-1)-1} = n 4^{n-1}`$
+
+**2)**
+Построим квадрат как на картинке. Видно, что заданное в задаче выражение равно сумме коэффициентов в жёлтом треугольнике. При этом сумма коэффициентов в каждом столбце и диагонали равна $`2^n`$. Значит нам интересна сумма коэффициентов в половине квадрата минус половина диагонали: $`\frac{2^{2n-1}(n+1) - 2^{2n-1}}{2} = n 4^{n-1}`$
+
+<img src="/uploads/0866a3fc2f6d164648a6a70bb83cca3e/photo_2021-11-01_16-26-07.jpg"  width="40%" height="40%">
+
+**Задача 5**
+*Каждый зритель, купивший билет в первый ряд кинотеатра, занял одно из мест в первом ряду.
+Оказалось, что все места в первом ряду заняты, но каждый зритель сидит не на своём месте. Билетёр
+может менять местами соседей, если оба сидят не на своих местах. Всегда ли он может рассадить всех на
+свои места?*
+
+Решение:
+
+Докажем по индукции. 
+*База* для двух человек очевидна.
+
+*Индукционное предположение* -- мы можем рассадить всех, если никто из них сидит на своих местах их меньше или n. 
+
+*Индукционный переход:* Пусть у нас есть $`n+1`$ человек, а кресла пронумерованы слева направо. Тогда рассмотрим первого человека слева, который сидит за одно место до своего места. Будем менять его с соседями слева пока он не сядет на 1ое место. Поскольку он был первым человеком, который так сидит, в процессе обменов его с соседями никто не сядет на своё место. Аналогично поступим по очереди со всеми людьми, которые сидят за одно место до своего - сдвинем их к предыдущим таким людям, которые уже сидят в начале.
+
+Получится, что у нас людей сидящих до своего места не осталось -- а именно они могли бы сесть на своё место, когда мы будем протаскивать влево человека с первого кресла. Значит мы сможем посадить первого человека на место, при этом так же на своё место смогут сесть только те люди, которые сидели до этого на одно место правее -- т.е. как раз те, кого мы перетаскивали влево, но только если их номера идут по порядку по возрастанию сразу за 1. Одним словом, мы получили ситуацию, когда первые сколько-то (1 или больше) человек сидят на своих местах, а оставшиеся все не на своих. Но по индукционному предположению решать такую ситуацию мы уже умеем, ведь умеем рассаживать любое количество людей меньше $`n+1`$ сидящих не на своих местах, но один сидящий (первый) у нас точно есть, а если есть другие они идут "вплотную" за первым и их всех тоже можно отбросить. 
\ No newline at end of file