Playing poohsticks in the Styx

Имеется 4 больших мешка с разноцветными стеклянными шариками. На мешках написано "красные", "зелёные", "синие", "смесь". Известно, что шарики в мешках действительно только красные, зелёные или синие, и смесь только в одном из мешков, но ни на одном мешке надпись не соответствует действительности.

Разрешается вслепую взять по одному шарику из каких-нибудь двух мешков; при этом можно выбирать, откуда взять второй шарик, в зависимости от цвета шарика, взятого из первого мешка.

Как гарантированно выбрать два мешка, в которых не смесь?

(Взято с fivethirtyeight.com)

Как только я вчера перед сном понял, что в словах "ЛЕГИОН" (в кириллическом счёте означавшем, в частности, 10⁵) и "ТЬМА" (как широко известно, это 10⁴) в общей сложности 10 различных букв, я лёг спать с намерением написать небольшую программу. Проснувшись поутру, я исполнил намеренное, и в результате оказалось, что

LEGION / ТЬМА = TEN - 3 решения (какая досада)

ЛЕГИОН / ТЬМА = МИГ - 2 решения

LEGION / ТЬМА = LOL - 4 решения


и т. п.

А, скажем, с частным вида EGG, OIL или TOT решение получается единственное.

Всего же комбинациий, чтобы число из каких-то 6 различных цифр, деленное на число из оставшихся 4 цифр (разумеется, ни в одном из двух чисел ноль не должен быть старшей цифрой), давало в результате целое число, оказывается 1382, от 107352 / 8946 = 12 до 973854 / 1062 = 917.

Лай собак какой породы, судя по её названию, должен быть наиболее благозвучным (вариант для нелюбителей собак: наименее неблагозвучным)?

Ответы не скринятся; кто первый, тот и молодец.

У какого популярного советского персонажа, скоропостижно покинувшего нас более 40 лет назад, был орохороним?

Если бы я знал ответ на более или менее ретрокомпьютерный вопрос, который хочу задать, из него могла бы получиться неплохая задачка для олимпиад по лингвистике. А пока это только вопрос в воздух.

( дальше интересно не всем )

Надо записать, а то пойду спать и забуду. 

Имеется черный ящик, в котором внутри реализована некоторая фиксированная перестановка из N элементов. У ящика можно попросить сгенерировать случайную строку из N бит, с независимыми равновероятными 0 и 1 в каждой  позиции, произвести над ней эту свою перестановку, и показать исходную строку и результат.

Сколько в среднем запросов нужно сделать, чтобы однозначно определить, какая внутри ящика перестановка?

Например, при N=2, c вероятностью 50% случайная строка нам ничего не скажет (если она оказалась 00 или 11, то она такая и останется), а с вероятностью 50% мы узнаем, какая из двух возможных перестановок была реализована. Итого, ожидаемое количество проб S = 0.5*(1+S) +  0.5*1, т. е. S = 2. Для N=3 уже нужна бумажка. А дальше я и не знаю.

Представьте себе плавательный бассейн, для конкретности стандартный олимпийский (50x25x2 м) в котором много часов никто не плавал. Вода в нём совершенно спокойная. Внезапно в бассейн прыгнули пловцы и принялись плавать туда-сюда в течение довольно долгого времени, скажем, порядка десятков минут, так что степень взболтанности воды в бассейне достигла равновесного значения, после чего вылезли из бассейна.

Как оценить механическую энергию, которую они придали воде своим плаванием, хотя бы по порядку величины?

Все (интересующиеся подобными вещами) помнят хрестоматийный ответ на вопрос, сколько людей должно быть в группе, чтобы с вероятностью больше 50% среди них нашлось два человека с совпадающим днём (числом и месяцем) рождения: этот ответ - 23, что на первый взгляд довольно парадоксально, учитывая более чем на порядок большее количество дней в году.

А теперь вопрос наоборот: сколько людей должно быть в группе, чтобы с вероятностью больше 50% среди них нашёлся человек, чей день рождения - 31 августа (в предположении, что все дни рождения равновероятны, разумеется)?

Вопрос, собственно, не в том, сможете ли вы вычислить ответ, или насколько парадоксальным он вам кажется, а слышали ли вы раньше об этом варианте парадокса? Что смешно, я о нём впервые узнал только вчера, поскольку число-ответ не вызвало у меня совершенно никаких воспоминаний.

Upd (thx to utnapishti): сколько человек должно быть в группе, чтобы с вероятностью больше 50% каждый день в году был чьим-нибудь днём рождения?

Бывший сослуживец-американец, ныне живущий в Неваде, на прошлой неделе посещал наши края, и на нашей с ним встрече-прогулке задал задачку:

Даны 10 различных целых чисел в диапазоне от 1 до 100. Докажите, что из них можно составить два различных набора с одинаковой суммой. (Возможно, в девичестве это какая-то старая русскоязычная детская задачка с гирьками и весами, но за что купил, за то продал.)

Комменты скринятся, дабы не портить удовольствие тем, кто её не знал. Также задайте детям, если они уже в том возрасте, в котором знают арифметические действия и понимают, что значит "докажите".

Комментарии больше не скрываются.

Трюк из предыдущего поста базируется на том, что программа zcat (gunzip), кроме своего собственного формата .gz, умеет разжимать еще и устаревшие форматы compress (.Z), который был основным и самым популярным до распространения gzip, а также предшествоваший ему формат pack (.z).

Этот формат pack был довольно прост. До 1977-78 годов, когда профессор אברהם למפל (родившийся в 1936 году, как и положено еврейскому математику, во Львове) и профессор יעקב זיו (родившийся в 1931 году, сабра), да будут они оба здоровы, изобрели семейство алгоритмов LZ, всё искусство сжатия текстов, отличных от длинных повторов одинаковых символов, недалеко ушло от кода Морзе: чего много - обозначаем более короткой последовательностью нулей и единиц вместо точек и тире, чего мало - обозначаем более длинной. В алгоритмические детали (префиксные коды, отличия кодировки Хаффмена от Шеннона-Фано) вдаваться не будем.

Благодаря тому, что создателю программы была поставлена задача сжимать только файлы (а не потоки байтов), сжиматель работает в два прохода - сначала собирает статистику по символам и строит таблицу, а потом читает файл ещё раз и выдаёт его сжатый вид. Из-за этого в начале сжатого файла есть таблица соответствия символов кодам, в которой можно устроить почти произвольную перетасовку символов, в частности ROT13.

А теперь по существу темы поста. Для простоты и скорости выполнения программы максимальная длина кода была ограничена 24 битами, чтобы при побайтной записи в сжатый файл или чтении из него в 32-битном слове гарантированно помещался как минимум один код независимо от положения кода по отношению к границам байтов (можно бы и 25, в принципе, ну да ладно). Эффективный алгоритм построения кодов с ограничением длины тогда еще не придумали, поэтому решили, что на практике такого соотношения частот символов, которое могло бы привести к кодам длиной более 24, не встретится. Действительно™, чтобы у символа был код длиной 1 бит, его частота должна быть порядка 50%, длиной 2 бита - порядка 25%, и т.п. Итого, чтобы длина кода была больше 24, частота символа должна быть меньше 1/2²⁴, а это может быть, только если символ встречается реже, чем 1 раз на 16 Мб.

Типичные длины файлов, которые могло бы захотеться сжимать этим алоритмом, в конце 70-х годов были от силы порядка сотен килобайт (потому что емкости дисков были порядка единиц мегабайт), вот и в программе написано

if (maxlev > 24) { /* can't occur unless insize.l.lng >= 2**24 */ printf (": Huffman tree has too many levels"); return(0); }

На самом же деле это наглое враньё, и рассуждение выше с "действительно" - заблуждение. В молодости у меня не потребовалось много времени, чтобы, познакомившись с программой pack, вызвать эту диагностику с помощью файла гораздо меньшей длины, чем 16 Мб. Попробуйте и вы.

Автор первоначальной программы - T.G. Szymanski (тот, который вторая S в LZSS). Вот же ж ведь позорник.