GitLab

Вариант 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))

Решение:

Задача 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}

Задача 5 Каждый зритель, купивший билет в первый ряд кинотеатра, занял одно из мест в первом ряду. Оказалось, что все места в первом ряду заняты, но каждый зритель сидит не на своём месте. Билетёр может менять местами соседей, если оба сидят не на своих местах. Всегда ли он может рассадить всех на свои места?

Решение:

Докажем по индукции. База для двух человек очевидна.

Индукционное предположение -- мы можем рассадить всех, если никто из них сидит на своих местах их меньше или n.

Индукционный переход: Пусть у нас есть n+1 человек, а кресла пронумерованы слева направо. Тогда рассмотрим первого человека слева, который сидит за одно место до своего места. Будем менять его с соседями слева пока он не сядет на 1ое место. Поскольку он был первым человеком, который так сидит, в процессе обменов его с соседями никто не сядет на своё место. Аналогично поступим по очереди со всеми людьми, которые сидят за одно место до своего - сдвинем их к предыдущим таким людям, которые уже сидят в начале.

Получится, что у нас людей сидящих до своего места не осталось -- а именно они могли бы сесть на своё место, когда мы будем протаскивать влево человека с первого кресла. Значит мы сможем посадить первого человека на место, при этом так же на своё место смогут сесть только те люди, которые сидели до этого на одно место правее -- т.е. как раз те, кого мы перетаскивали влево, но только если их номера идут по порядку по возрастанию сразу за 1. Одним словом, мы получили ситуацию, когда первые сколько-то (1 или больше) человек сидят на своих местах, а оставшиеся все не на своих. Но по индукционному предположению решать такую ситуацию мы уже умеем, ведь умеем рассаживать любое количество людей меньше n+1 сидящих не на своих местах, но один сидящий (первый) у нас точно есть, а если есть другие они идут "вплотную" за первым и их всех тоже можно отбросить.