«
»

О пользе наук

18.10.2011

Недавно на собеседовании мне предложили несколько задачек, среди которой была задача о шарах. Вы, возможно, знаете ее, формулировка у ней такая. В корзине лежит m белых и n черных шаров. Из нее наугад вынимают 2 шара. Если шары одного цвета, то в корзину возвращают белый шар, если разного, то черный. Считается, что есть достаточное количество белых шаров вне корзины для их возврата в случае постоянной выемки пар из двух черных шаров. Вопрос: можно ли, зная числа m и n, заранее сказать, какой шар в корзине останется последним?

К своему стыду за отведенное время я эту задачу не решил, хотя провозился с ней долго. Я вообще несколько туповат и тугодум, поэтому быстро решать подобные задачи не могу. На днях я вернулся к этой задачке, так как решить ее было делом чести.

Сначала я снова начал бродить вокруг тех же безрезультатных идей, которые у меня были на собеседовании. Но потом вдруг вспомнил о недавнем чтении ТФКП и придумал вот что. Пусть общее число шаров в корзине соответствует некому комплексному числу z = x + iy, причем действительная часть показывает количество белых шаров, а мнимая — черных. Если вынули два белых шара и затем один вернули, то в корзине останется x + iy-2 + 1 = (x-1) + iy. Если вынули два черных и вернули белый, то в корзине будет x + iy-2i + 1 = (x + 1) + i(y-2). И, наконец, если вынули белый и черный и вернули черный, в корзине останется x + iy-1-i + i = (x-1) + iy. Видно, что третий случай эквивалентен первому. Кроме того, общее число шаров (x + y) на каждом шаге уменьшается ровно на единицу, то есть в конечном итоге действительно останется только один шар. Таким образом, при очередной выемке к текущему числу шаров прибавляют либо число z_1 = -1, либо z_2 = 1-2i.

Пусть до того, как в корзине остался один шар, сделали k выемок по z_1 и l выемок по z_2 (k, l — неотрицательные целые). Тогда возможно два варианта: m + in + kz_1 + lz_2 = 1, если последний шар белый, и m + in + kz_1 + lz_2 = i, если последний шар черный.

Вообще, сами комплексные числа тут особо не нужны, нужно только их представление на комплексной плоскости, т. е. можно вполне обойтись обычными векторами. Пусть (m, n) — вектор, задающий начальное состояние корзины. Тогда конечное состояние можно представить в виде суммы начального вектора и линейной комбинации векторов (-1, 0) и (1, -2).

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

m + (-1)\cdot k + l = 1 \\n + 0\cdot k + (-2)\cdot l = 0, если последний шар белый, и

m + (-1)\cdot k + l = 0 \\n + 0\cdot k + (-2)\cdot l = 1, если последний шар черный.

Отсюда видно, что n = 2l для белого шара и n = 2l + 1 для черного. То есть если начальное число черных шаров четное, то последним останется белый шар, если нечетное — то черный. Это и есть ответ.

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

,



  1. Саша, скажи что за контора.

    # kronos, 18.10.2011 в 15:38.

  2. можно проще:

    черный+черный = белый
    черный+белый = черный
    белый+черный = черный
    белый+белый = белый

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

    т.е. белые изъять можно все в любом случае, пока шаров больше 1, а черные — только если их количество четно.

    # мимо проходил, 18.10.2011 в 18:23.

    • Конечно можно! Но это ж надо думать, а у меня думать получается плохо :)

      # Alexander Yurchenko, 18.10.2011 в 20:11.

  3. Мне тоже попадалась интересная задачка, про перестановку двух интеджеров не используя третьей переменной. Можно использовать операции вида x или y = f(x,y). Главное, не тратить время пытаясь доказать, что это невозможно.

    # Sergey Sokolov, 25.10.2011 в 09:58.

    • это реликтовый боянец.

      xor

      # мимо проходил, 27.10.2011 в 15:15.

      • 1. можно использовать не только xor а например операции +- да и не только их
        2. к этому баянцу есть подбаянец — вместо xor использовать комбинацию &|~

        # tm, 27.10.2011 в 21:08.

        • с +\- могут быть сложности если числа вещественные сильно разных порядков или при переполнении.

          # мимо проходил, 29.10.2011 в 17:54.

  4. Мне вот что непонятно. Если в 1 момент времени из корзины достаём черный+черный, то должны вернуть белый- это ломает все мои представления о «жизни».
    Объясните пожалуйста.

    # Error, 23.12.2011 в 09:13.

    • А в чем неувязка-то?

      # Alexander Yurchenko, 23.12.2011 в 09:57.

      • Условие — В корзине лежит m белых и n черных шаров. Из нее наугад вынимают 2 шара. Если шары одного цвета, то в корзину возвращают белый шар.
        Если в 1 момент времени вынимаю 2 ЧЁРНЫХ шара, то должен ВЕРНУТЬ в корзину БЕЛЫЙ шар, который не доставал — как это?

        # Error, 20.01.2012 в 08:56.

        • > Считается, что есть достаточное количество белых шаров вне корзины для их возврата в случае постоянной выемки пар из двух черных шаров.

          # Alexander Yurchenko, 20.01.2012 в 09:34.

          • В 1 раз когда читал условия задачи, опустил это предложения по непониманию. Простите мну такого :D

            # Error, 20.01.2012 в 12:40.