2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Комбинаторика информации
Сообщение29.05.2014, 13:23 
Несложная задача, но не могу решить ее комбинаторно.

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

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

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

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

 
 
 
 Re: Комбинаторика информации
Сообщение29.05.2014, 13:37 
Аватара пользователя
constant в сообщении #869166 писал(а):
Есть четыре поезда, каждый из них либо едет, либо не едет в Москву, а потому это Размещение из 2 по 4, то есть 16 бит.
Только один едет в Москву, поэтому каждому из них либо ехать, либе нет не разрешается.

 
 
 
 Re: Комбинаторика информации
Сообщение29.05.2014, 14:54 
Аватара пользователя
Из того, что поездов $4$, лишь со скрипом следует (т.е., собственно говоря, не следует), что платформ тоже $4$. А указывать надо платформу.

 
 
 
 Re: Комбинаторика информации
Сообщение29.05.2014, 16:08 
Понял, почему мое решение неверно, а каким тогда будет верное и притом комбинаторное решение?

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

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

 
 
 
 Re: Комбинаторика информации
Сообщение29.05.2014, 17:02 
svv

(Оффтоп)

Жуть какая. :shock:

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

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

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


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

 
 
 
 Re: Комбинаторика информации
Сообщение29.05.2014, 17:20 
Аватара пользователя
svv в сообщении #869227 писал(а):
логарифм монотонно возрастающая функция
Читать как «логарифм по основанию $2$ монотонно возрастающая функция.»

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

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group