Свёртыш (kladun) wrote,
Свёртыш
kladun

Про битьё стеклянных шаров

Привожу ответ на задачку.

В случае с двумя шарами 100-этажное здание можно гарантированно промерить за 14 бросков.
Делается это так: первый шар сбрасывается с 14-ого этажа, далее, если не разбивается, с этажа номер 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100.
Определенный таким образом промежуток, в котором разбивается шар, последовательно промеряется вторым шаром.

Иначе говоря, вначале мы зондируем здание первым шаром с шагом, уменьшающимся на единицу, начиная с 14. То есть номер этажа для сбрасывания определяется последовательным суммированием 14 + 13 + 12 + 11 + ... Каждый бросок первым шаром отнимает у нас один ход, потому следует уменьшать на один и количество этажей для промера вторым шаром. В итоге сумма бросков первым и вторым шаром не превысит 14 и мы точно определим искомый этаж.

За N бросков таким способом можно гарантированно промерить N + (N-1) + ... + 3 + 2 + 1 = N*(N+1)/2 этажей. При N=13 это 91 этаж, а при N=14 уже 105.

В случае с 3-мя шарами искомый этаж определяется в 9 бросков. Принцип такой же - зондируем здание первым шаром через промежуток, который можно смерить оставшимся числом ходов с помощью двух шаров (см. формулу выше). Это значит, что сбрасываем первый шар с этажей 37, 66, 88, 100 и определенный промежуток промеряем двумя шарами описанным выше способом. За 8 ходов так можно промерить 92 этажа, за 9 - 129 этажей.

P.S. Коменты в посте с задачей раскрыл.
Subscribe

  • памятная дата

    Сегодня исполняется ровно 10 лет с восстания на Манежке. Кто не читал или не прочь освежить в памяти, моя ода тем событиям тут.

  • 53

    Сегодня бы исполнилось. Всего-навсего 53. Но не случилось даже столько. Я помню.

  • Разъяснение про коммунизм

    Как известно, не существует каноничного описания коммунизма. Тот же Маркс писал, что коммунизм обязательно наступит в силу законов исторического…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 4 comments