Peg Game: лучшее место для размещения мяча так, чтобы он приземлился в целевой ячейке

Источник: Facebook Hacker Cup Квалификационный раунд 2011

В аркаде вы можете сыграть в простую игру, в которой мяч падает в верхнюю часть игры, из положение по вашему выбору. Есть несколько колышков, от которых мяч будет отскакивать во время падения в игре. Каждый раз, когда мяч ударяется о колышек, он отскакивает влево с вероятностью 0,5 и вправо с вероятностью 0,5. Единственное исключение из этого - когда он ударяется о колышек слева или справа, в этом случае он всегда отскакивает к середине.

Когда игра была впервые сделана, колышки были расположены в правильной сетке. Однако это старая игра, и теперь некоторые колышки отсутствуют. Ваша цель в игре - заставить мяч выпасть из нижней части игры в определенном месте. Учитывая организацию игры, как мы можем определить оптимальное место, чтобы бросить мяч, чтобы вероятность попадания в это конкретное место была максимальной?

На изображении ниже показан пример игры с пятью рядами по пять столбцы. Обратите внимание, что в верхнем ряду пять колышков, в следующем - четыре, в следующих пять и так далее. С пятью столбцами есть четыре варианта, в которые можно бросить мяч (индексируется от 0). Обратите внимание, что в этом примере отсутствуют три колышка. Верхняя строка - это строка 0, а крайний левый стержень - это столбец 0, поэтому координаты недостающих колышков равны (1,1), (2,1) и (3,2). В этом примере лучше всего бросать мяч в крайнем левом углу, в столбце 0, что дает 50% -ную вероятность того, что мяч попадет в цель.

x.x.x.x.x
 x...x.x
x...x.x.x
 x.x...x
x.x.x.x.x
 G

x указывает на колышек, . указывает на пустое пространство.