Так, ну с правилами сложения и умножения мы немножко разобрались, я надеюсь.
Давайте попробуем чуть-чуть коснуться принципа Дирихле в таком простейшем
варианте, конечно, то есть не заморачиваясь пока что.
И начнем с чего-нибудь совсем простого.
Ну давайте так вот: есть монеты [ПИШЕТ НА ДОСКЕ]
стоимостью 1, 2, 5 и 10 рублей, соответственно.
Есть монеты стоимостью 1 рубль, 2 рубля,
5 рублей и 10 рублей.
Спрашивается: какое минимальное количество таких монет необходимо и достаточно взять,
какое минимальное количество таких монет необходимо и достаточно взять,
чтобы с гарантией среди вот этих взятых монет,
то есть как бы их ни взяли, нашлось 6 монет одного достоинства?
Вот давайте я напишу это словами.
Значит, каково минимальное
количество таких монет,
чтобы при абсолютно любом раскладе, всегда,
с гарантией нашлись 6 монет одного достоинства,
нашлись 6 монет
одного достоинства.
Ну то есть либо 6 рублей отдельных, либо 6 отдельных двушек,
либо пятачков, либо гривенников таких.
Так, 6 монет одного достоинства.
Ну тут даже
сильно говорить «принцип Дирихле», потому что задачка совсем простая.
Утверждается, что ответ 21, конечно.
Это ответ, и сейчас я это буду аккуратно обосновывать.
Значит, смотрите, во-первых, что нам нужно обосновать?
Ведь я недаром произнес слова «необходимо и достаточно».
То есть я утверждаю, что, с одной стороны, 21 достаточно для того,
чтобы гарантировать, что заведомо найдется 6 монет одного достоинства,
а, с другой стороны, я утверждаю, что это минимальное число.
То есть если взять 20 монет, то, вообще говоря,
шести одинаковых может и не случиться.
Понимаете, вот тут слово «минимум» очень принципиально.
Если взять 20 монет, то, вообще говоря, можно так разложить их по кучкам,
чтобы пяти монет одинакового достоинства не случилось.
Ну последнее утверждение, то есть вот что среди 20-ти вполне может случиться так,
что не найдется шести одинаковых, – оно кажется совсем очевидным,
потому что действительно мы можем просто взять 5 монет
достоинством 1,
5 монет достоинством 2,
5 монет достоинством 5 и 5 монет достоинством 10.
Видите, ни одной шестерки нет, все по 5 каждый раз,
но при этом в сумме получается в аккурат 5 х 4, то есть 20 монет.
И вот вам ситуация, когда всего монет – 20 штук,
и среди них нет шестерки одинаковых: есть пятерка одинаковых,
другая пятерка одинаковых, третья и четвертая — шестерки одинаковых нет.
То есть, если что-то и минимально, то точно не 20 и, тем более,
не меньше чем 20.
Ну осталось доказать,
что среди 21 монеты ну непременно найдется 6 одинакового достоинства.
Ну, действительно, давайте предположим,
что монет
достоинством 1 не больше пяти.
Так же точно предположим,
что монет достоинством 2 снова не больше пяти.
Так же точно предположим, что и монет достоинством 5 не больше пяти.
И даже предположим, о ужас,
что монет достоинством 10 по-прежнему не больше пяти.
Но смотрите, если у нас таких монет не больше пяти,
таких не больше пяти, таких не больше пяти и таких не больше пяти,
то суммарно их будет не больше 20 опять же.
Здесь 5 + 5 + 5 + 5 — это 20, то есть суммарно их будет не больше 20.
Но у нас-то их 21, мы же уже считаем, что у нас 21 монета.
Значит, какое-то из вот этих вот предположений все-таки неверно.
А что значит оно неверно?
Оно неверно — это значит, что либо монет достоинством 1 не
меньше шести, либо монет достоинством 2 не меньше шести,
ну и так далее, то есть какая-то шестерка уже точно найдется.
Ну я не знаю, вот такое вот простое применение, если хотите,
принципа Дирихле, ящики с кроликами.