Задать вопрос
@Andrew1000000

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



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

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

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

Удачного решения.
P.S. Всем спасибо.
  • Вопрос задан
  • 3148 просмотров
Комментировать
Подписаться 9 Оценить Комментировать
Пригласить эксперта
Ответы на вопрос 7
@Andrew1000000 Автор вопроса
Думаю, примерно так и надо доказывать.
После 4 ходов мы будем точно знать, что шарика нет в стаканах с номерами 1..4 и такими:
k1+4; k2+3; k3+2; k4+1,
где k1, k2, k3, k4 — номера стаканов, проверяемых на соответствующем ходе.
Остаётся два стакана, чтобы их проверить, нужно ещё два хода.
Так что можно вас объявить победителем :)
Ответ написан
1 комментарий
1 комментарий
tbicr
@tbicr
Сперва думал что нашел решение с 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
Ответ написан
Комментировать
Комментировать
UniBomb
@UniBomb
За шесть. Первые пять ходов — это первые пять стаканов. Шестой — последний стакан. Если его нет в младшей (в первой) пятёрке, то он гарантированно окажется в последнем стакане.
Ответ написан
4 комментария
4 комментария
nickme
@nickme
можно просто пять раз поднять пятый стакан, если он все-таки пуст, то ответ — десятка… тоже шесть ходов
Ответ написан
1 комментарий
1 комментарий
@Andrew1000000 Автор вопроса
А можно ли доказать, что 6 ходов — это минимум?
Ответ написан
1 комментарий
1 комментарий
ratkke
@ratkke
5 ходов у меня получилось. Смотрите — сначала открываем 5 стакан, затем 4, затем 3. Если за все это время шарика не оказалось — значит он уже либо в 9 либо в 10. Открываем их соответсвенно сначала 9, потом 10.
Ответ написан
1 комментарий
1 комментарий
@Mercury13
Программист на «си с крестами» и не только
Меньше, чем за шесть нельзя, и вот почему.
Задача эквивалентна такой. Поднимаем колпачок. Есть шарик — отлично; если нет — снимаем правый, и если шарик под ним, тот перекатывается под оставшийся правый. Очевидно, после четырёх проверок четыре колпачка исчезнут, а значит, как минимум два непроверенных останутся.
Ответ написан
Комментировать
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Вакансии с Хабр Карьеры
JavaScript разработчик
summer • Ярославль
от 100 000 до 140 000 ₽
Функциональный архитектор 1С:ERP
SmartyHR • Москва
До 500 000 ₽
Ведущий консультант 1С:ERP
SmartyHR • Москва
До 350 000 ₽
Ещё вакансии
Заказы с Хабр Фриланса
Фронтенд и скрипты мобильного приложения на Flutter или ReactNative
18 апр. 2024, в 13:47
50000 руб./за проект
Обучение команды разработчиков по направлению Kafka Срок - 1 месяц
18 апр. 2024, в 13:46
3000 руб./в час
Техническая оценка специалиста по разработке на React Native
18 апр. 2024, в 13:40
1500 руб./в час
Ещё заказы