Описание слайда:
Не всё так просто. Не всё так просто. 19. Имеется 10 различных книг. Сколькими различными способами можно выбрать из них одну или несколько книг для подарка? Решение. Занумеруем книги числами от 1 до 10. Тогда каждому подарку можно сопоставить двоичный код длины 10, где на k-ом месте стоит 1, если книга с номером k входит в подарок, и 0, если не входит (например, подарку из книг 2, 5, 7 и 8 соответствует код 100101100). Значит, способов сделать подарок будет 210. Критика. На самом деле подарков меньше, чем кодов, ибо коду 0000000000 никакой подарок не соответствует: пустых подарков не бывает! Поскольку всем остальным кодам подарки все же соответствуют, верный ответ – 210–1. 20. Сколькими различными способами победитель "Поля чудес" может выбрать два приза из трех имеющихся? Решение. Пусть призы – заводы, а выбор – размещение заказов. Тогда наша задача кодируется задачей о размещении заказов, и способов получается = 321 = 6 Критика. Легко убедиться, что ответ снова неверен: если обозначить призы цифрами 1, 2 и 3, то выборов получится только три: {1,2}, {1,3} и {2,3}. Причина в том, что в базовой задаче 7 заказы были различными, а тут неважно, какой приз взят первым, а какой – вторым. Это привело к тому, что мы в нашем "решении" каждый выбор сосчитали дважды. Например, выбор {1,2} получил коды 12 и 21: первый код соответствует случаю, когда первым был взят приз №1, а второй – случаю, когда первым был взят приз №2. Мораль. Сводя одну задачу к другой, надо брать только такие кодировки, при которых каждому кодируемому предмету соответствует ровно один код, а каждому коду – ровно один предмет (такое соответствие между предметами и кодами называется взаимно-однозначным.) Лишь в этом случае мы можем гарантировать, что кодируемых предметов столько же, сколько кодов. 21. Почему задача 17 не кодируется задачей о троичных кодах?
