Комбинаторика информации

[constant]

Несложная задача, но не могу решить ее комбинаторно.

Есть 4 поезда, только один из них едет в Москву. Сколько битов понадобиться для того, чтобы записать информацию о номере платформы, где стоит поезд на Москву?

Есть переборное решение: нужно все 4 различать, тогда нужно 4 символа: 00, 01, 10, 11, а это 2 бита.

Есть четыре поезда, каждый из них либо едет, либо не едет в Москву, а потому это Размещение из 2 по 4, то есть 16 бит.

Первый ответ правильный(проверил по формуле Хартли (которая с двоичным логарифмом)), но я никак не пойму как можно получить размещение из 2 по 2. Помогите, пожалуйста!

[TOTAL]

constant в сообщении #869166 писал(а):

Есть четыре поезда, каждый из них либо едет, либо не едет в Москву, а потому это Размещение из 2 по 4, то есть 16 бит.

Только один едет в Москву, поэтому каждому из них либо ехать, либе нет не разрешается.

[svv]

Из того, что поездов $4$, лишь со скрипом следует (т.е., собственно говоря, не следует), что платформ тоже $4$. А указывать надо платформу.

[constant]

Понял, почему мое решение неверно, а каким тогда будет верное и притом комбинаторное решение?

[svv]

Вот такое. Пусть у нас есть $k$ бит, каждый из них может принимать значение $0$ или $1$. Сколько различных комбинаций значений существует? (Видите слово «комбинация»? Значит, решение комбинаторное!) Очевидно, $2^k$. Сопоставим каждой из $n$ платформ некоторую из $2^k$ комбинаций, так, чтобы разным платформам соответствовали разные комбинации. Это можно сделать, в соответствии с принципом Дирихле, при условии $2^k\geqslant n$, или, так как логарифм монотонно возрастающая функция, $k\geqslant \log_2 n=\log_2 4=2$

Предыдущий абзац был наукообразной шуткой, но Вы, по-моему, примерно такого решения и хотели.

[Otta]

svv

(Оффтоп)

Жуть какая.

[constant]

svv в сообщении #869227 писал(а):

Вот такое. Пусть у нас есть $k$ бит, каждый из них может принимать значение $0$ или $1$. Сколько различных комбинаций значений существует? (Видите слово «комбинация»? Значит, решение комбинаторное!) Очевидно, $2^k$. Сопоставим каждой из $n$ платформ некоторую из $2^k$ комбинаций, так, чтобы разным платформам соответствовали разные комбинации. Это можно сделать, в соответствии с принципом Дирихле, при условии $2^k\geqslant n$, или, так как логарифм монотонно возрастающая функция, $k\geqslant \log_2 n=\log_2 4=2$

Предыдущий абзац был наукообразной шуткой, но Вы, по-моему, примерно такого решения и хотели.

Да, то что надо - спасибо!


Otta
А как бы Вы решали, чтобы явно получилось размещение?

[svv]

svv в сообщении #869227 писал(а):

логарифм монотонно возрастающая функция

Читать как «логарифм по основанию $2$ монотонно возрастающая функция.»

Otta

Скорее всего, под размещением понимается «перестановка, сочетание, размещение или другая подобная комбинаторная штуковина».