Бесячая задача

Постановка

Демагогия

Чем бесит эта задача? А тем, что решение, чуть лучше плохого (там, где решающий догадывается о ЦПТ - об этом дальше), является верным. Выглядит оно ужасно, буквально хочется кричать, но: постановка задачи такова, что ничего лучше не придумаешь (нам, что называется, «выкрутили руки»). В итоге: тупить на этой задаче одинаково будет и новичок, и опытный - но по разным причинам. Хорошо бы спрашивать у решивших быстро «середнячков» аспекты их решения.

Впервые я услышал эту задачу из уст человека, не очень ассоциирующегося с понятием «программирование». Исходя из озвученного решения, я был уверен, что он сам её придумал. Ну, оказалось, что даже её придумал не он, зато – эта задачка регулярно всплывает на собеседованиях.

Решение

Вызываем генератор два раза и интерпретируем выходы следующим образом:


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

Чуть более продвинутый уровень - интерпретировать серию исходов как биты (для конкретики, в нотации little endian), тогда:

В чем ловушка задачи?

Базовая ловушка задачи - навязать решающему не взвешенное суммирование. Нельзя просто взять и сложить два результата. Действительно:

• 00 - 0
  
• 01 - 1
  
• 10 - 1
  
• 11 - 2

Видим, что такой подход приводит к желаемому расширению диапазона до трёх состояний, но середину распределения - в соответствии с Центральной Предельной Теоремой - можно получить бОльшим количеством способов, чем «хвосты». Результат «1» будет доминировать над «0» и «2», что нарушает требования к результату. Мы уже разбирали этот эффект, когда каскадировали броски игральных кубиков здесь

Мне, как обычно, очень нравится когда творческая аналитика («рассмотрим группы выходов отдельно») соответствует формальным трансформациям (взвешивание суммы, очевидное при «битовой» интерпретации решения, приводит к неравномерному вкладу слагаемых, что нарушает условия ЦПТ).

Страдания

В перезапуске кроется вся мерзость решения. Мы можем повторять процедуру сколько угодно раз, а значит:

• время работы алгоритма нестабильно;
  
• время работы может быть сколь угодно большим.
  

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

Можем ли мы использовать какие-то алгоритмы каскадирования, чтобы получив X результатов от исходного генератора, преобразовать их в Y результатов требуемого диапазона (то есть: гарантировать генерацию за известное количество "тактов")?

Ранее мы оговорили, что для ухода от ЦПТ, масштабировать выход мы можем только взвешенной суммой исходов.

Далее примем следующие обозначения:

• **

  - возведение в степень (как в Питоне);
  

• <<

  - битовый сдвиг влево (как в Си);
  

• continue

  - переход к следующей итерации в цикле (как в Си и Питоне).
  

Можем ли мы создать такую серию исходов, что образованный ею набор чисел можно будет интерпретировать как набор чисел в троичной системе? Вернее: не просто «интерпретировать», а чтобы каждому состоянию серии соответствовал уникальный набор чисел. Возвращаясь к игральным костям: один бросок D4 можно интерпретировать как 2D2, так как размеры диапазонов связаны как 4 ** p = 2 ** q.

Таким образом, вопрос сводится к отысканию корней уравнения:


Решений у него нет, так как слева стоит произведение четных чисел (2 * 2 * …), а справа - нечётных (3 * 3 * …). Слева, при любом целом p - чётное, справа, при любом целом q - нечётное.
Можем ли мы создать такую серию исходов, что образованное ею число будет делиться нацело на 3?

В «кубиках» это: бросок шестигранника можно свести к 1D3, путем деления результата на 2 с округлением, так как


Таким образом, вопрос сводится к уравнению:


У меня только одна идея как можно доказать отсутствие корней у этого уравнения.

Слева стоит произведение числа 3 ( в двоичном представлении) и неизвестного m (), справа - степень двойки ( в двоичном представлении: число с одной единичкой). Необходимо найти такое число m, чтобы выполнялось тождество, которое «в столбик» записывается как:



Иначе говоря: сумма разрядов числа и этого же числа, сдвинутого на один разряд влево, должна быть такой, чтобы только один разряд результата был с единичкой. (К рассуждениям о сдвиге можно прийти и из соображений: 3 * m = 2 * m + m = (m << 1) + m.)

Рассмотрим суммирование, допустим, для числа 010:


Получили два сложения единички и нуля - два поднятых разряда в ответе.

Попробуем число, более обильное на истинные биты: 0011:


Сложение двух единичек «избавляет» соответствующий разряд результата от цифры «один», но провоцирует перенос - единичка «всплывает» далее.

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

Как всегда – приглашаю всех желающих.