Давно не решали занимательные задачки на Хабре?

Question

[Andrew1000000]

Решил возобновить традицию решения занимательных задач на Хабре :)
Предлагаю математическую задачку под названием «Волшебный шарик».

На столе стоит 10 непрозрачных стаканов. Под одним из них лежит шарик. За каждый ход можно поднять один из стаканов и проверить, есть ли там шарик. Если шарик найден — выигрыш. Если под стаканом шарика не оказалось, он перемещается в соседний справа стакан. При этом он может переместиться и в тот стакан, который только что проверили. Если шарик в крайнем справа стакане — он никуда не перемещается. Будем считать, что если вы точно знаете, где шарик (например проверили 9 стаканов), вам всё равно нужно поднять последний стакан и увидеть под ним шарик (это нужно для точного подсчёта ходов).

Задача заключается в том, чтобы определить, за какое минимальное количество ходов можно гарантированно найти шарик.

Удачного решения.
P.S. Всем спасибо.

Answer 1

[Andrew1000000]

Думаю, примерно так и надо доказывать.
После 4 ходов мы будем точно знать, что шарика нет в стаканах с номерами 1..4 и такими:
k1+4; k2+3; k3+2; k4+1,
где k1, k2, k3, k4 — номера стаканов, проверяемых на соответствующем ходе.
Остаётся два стакана, чтобы их проверить, нужно ещё два хода.
Так что можно вас объявить победителем :)

Comments

[Andrew1000000]

nickme

Answer 2

[Павел Тысляцкий]

Сперва думал что нашел решение с 5ю попытками, потом решил проверить кодом: для 5и и меньше попыток решения не нашел, для 6и 1056 разных решений, причем последний ход не всегда заканчивается поднятием последнего стакана.
Или же мой код неверен.

Решение в лоб для 5и попыток:

wins = 0
# i1, i2, i3 и тд - выбор стакана на 1ом, 2ом, 3ем и тд шагах соответственно
for i1 in xrange(1, 11):
    for i2 in xrange(1, 11):
        for i3 in xrange(1, 11):
            for i4 in xrange(1, 11):
                for i5 in xrange(1, 11):
                    win = 0
                    # j - начальное положение шарика
                    # pos1, pos2, pos3 и тд
                    # - положение шарика в начале 1ого, 2ого, 3его и тд хода
                    for j in xrange(1, 11):
                        pos1 = min(j + 0, 10)
                        pos2 = min(j + 1, 10)
                        pos3 = min(j + 2, 10)
                        pos4 = min(j + 3, 10)
                        pos5 = min(j + 4, 10)
                        if i1 == pos1 or i2 == pos2 or i3 == pos3\
                        or i4 == pos4 or i5 == pos5:
                            win += 1
                    if win == 10:
                        print i1, i2, i3, i4, i5
                        wins += 1
print wins

Решение в лоб для 6и попыток:

wins = 0
# i1, i2, i3 и тд - выбор стакана на 1ом, 2ом, 3ем и тд шагах соответственно
for i1 in xrange(1, 11):
    for i2 in xrange(1, 11):
        for i3 in xrange(1, 11):
            for i4 in xrange(1, 11):
                for i5 in xrange(1, 11):
                    for i6 in xrange(1, 11):
                        win = 0
                        # j - начальное положение шарика
                        # pos1, pos2, pos3 и тд
                        # - положение шарика в начале 1ого, 2ого, 3его и тд хода
                        for j in xrange(1, 11):
                            pos1 = min(j + 0, 10)
                            pos2 = min(j + 1, 10)
                            pos3 = min(j + 2, 10)
                            pos4 = min(j + 3, 10)
                            pos5 = min(j + 4, 10)
                            pos6 = min(j + 5, 10)
                            if i1 == pos1 or i2 == pos2 or i3 == pos3\
                            or i4 == pos4 or i5 == pos5 or i6 == pos6:
                                win += 1
                        if win == 10:
                            print i1, i2, i3, i4, i5, i6
                            wins += 1
print wins

Answer 3

[UniBomb]

За шесть. Первые пять ходов — это первые пять стаканов. Шестой — последний стакан. Если его нет в младшей (в первой) пятёрке, то он гарантированно окажется в последнем стакане.

Comments

[UniBomb]

даже за пять. Открываем четыре раза пятый стакан. За четыре открывания он бы нам попался бы, если бы был в первом стакане. Если не попадётся, то в худшем случе за четыре раза он переместился бы в последний стакан и оказался бы в десятом, который мы бы в пятый раз и открыли бы.

[nickme]

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

[nickme]

«первые пять ходов — это первые пять стаканов», т.е. 1, 2, 3, 4, 5 — не проходит, т.к. если шарик изначально лежал под вторым стаканом, то после пятого хода он окажется лежащим под седьмым (а не под десятым)…

[Colobock]

За эти пять ходов он бы уже показался под пятым. Если же не показался — он лежал в последних пяти и за пять ходов добрался бы до последнего.

Answer 4

[nickme]

можно просто пять раз поднять пятый стакан, если он все-таки пуст, то ответ — десятка… тоже шесть ходов

Comments

[nickme]

либо поднимать 1, 3, 5, 7, 9, 10 — тоже шесть ходов :)

Answer 5

[Andrew1000000]

А можно ли доказать, что 6 ходов — это минимум?

Comments

[nickme]

а шесть — это минимум? :) схема доказательства может быть примерно такой: после каждого хода максимум два стакана гарантированно оказываются пустыми — тот, что справа от открываемого и самый левый из неоткрытых, значит делаем четыре хода и у нас остается два стакана — их надо проверить оба, итого 6 ходов…

Answer 6

[ratkke]

5 ходов у меня получилось. Смотрите — сначала открываем 5 стакан, затем 4, затем 3. Если за все это время шарика не оказалось — значит он уже либо в 9 либо в 10. Открываем их соответсвенно сначала 9, потом 10.

Comments

[ratkke]

эх, если шарик изначально был в 4 стакане — не прокатит.

Answer 7

[Mercury13]

Меньше, чем за шесть нельзя, и вот почему.
Задача эквивалентна такой. Поднимаем колпачок. Есть шарик — отлично; если нет — снимаем правый, и если шарик под ним, тот перекатывается под оставшийся правый. Очевидно, после четырёх проверок четыре колпачка исчезнут, а значит, как минимум два непроверенных останутся.