Вопрос школьника
Меню состоит из 101 блюда. Докажите, что количество способов выбора обеда из нечетного количества блюд равно, количества способов выбора обеда с парной количества блюд при условии, что заказать все блюда из меню нельзя
Ответ от учителя
Для доказательства данного утверждения воспользуемся принципом биекции.
Предположим, что количество блюд в меню нечетное. Тогда при выборе обеда мы можем выбрать любое нечетное количество блюд от 1 до 101. Обозначим это количество за n. Таким образом, нам нужно посчитать количество способов выбрать n блюд из 101.
Теперь рассмотрим случай, когда количество блюд в меню четное. В этом случае мы не можем выбрать все блюда из меню, так как это четное количество. Поэтому мы можем выбрать любое нечетное количество блюд от 1 до 99. Обозначим это количество за m. Таким образом, нам нужно посчитать количество способов выбрать m блюд из 100.
Заметим, что количество способов выбрать n блюд из 101 равно количеству способов выбрать 101 — n блюд из 101. Это следует из того, что если мы выбрали n блюд, то оставшиеся 101 — n блюд мы автоматически не выбрали. Таким образом, мы можем установить биекцию между выбором n блюд и выбором 101 — n блюд.
Аналогично, количество способов выбрать m блюд из 100 равно количеству способов выбрать 100 — m блюд из 100. Мы также можем установить биекцию между выбором m блюд и выбором 100 — m блюд.
Таким образом, мы доказали, что количество способов выбора обеда из нечетного количества блюд равно количеству способов выбора обеда с парной количества блюд при условии, что заказать все блюда из меню нельзя.
