Давненько у меня не было задач, которые, кажется, невозможно решить. Но время пришло, так что сразу к делу.
На столе аккуратными рядами разложены 100 игральных карт. 10 из них лежат лицом вверх, а остальные 90 — рубашкой вверх. Как именно они разложены вы не знаете, на глазах у вас плотная маска, через которую ничего не видно, почувствовать на ощупь, где у карты лицо, а где рубашка, невозможно. При этом вам каким-то образом нужно сделать так, чтобы на столе получилось две группы карт, в каждой из которой будет одинаковое количество карт, лежащих лицом вверх. Как это сделать?
Говорят, что эту задачу давали на собеседовании в Apple. Впрочем, интересным задачам всегда придумывают подобную легенду, так что особо верить в это не будем. Лучше давайте разберём её решение.
Решение
На первый взгляд, решить задачу невозможно. Мы не занем, какие карты лежат лицом вверх, а потому вероятность того, что, взяв наугад пять случайных карт и отложив их отдельно в надежде на то, что именно они лежали лицом вверх, и теперь в обоих группах по 5 карт, лежащих лицом вверх, ничтожно мала. Можно даже посчитать её, она равна чуть больше трёх десятимиллионных — 0,0000003. Маловато. Так что метод научного тыка здесь не прокатит.
Тут нужна стратегия.
А стратегия должна быть такой: берём 10 любых карт наугад, откладываем их и переворачиваем все 10. Всё! Теперь в обеих группах одинаковое количество карт, лежащих лицом вверх. Не факт, что в каждой группе их по пять, но нас никто и не просил, чтобы их было по пять. Это многие из нас сами додумали, потому что десять делить на два — это пять.
Нас просили, чтобы карт, лежащих лицом вверх было одинаковое количество в обеих группах. При этом их может вообще не быть, быть по одной, по две, три, четыре, пять, шесть, семь, восемь, девять или даже по десять в каждой группе. Почему так получается?
Покажу в общем случае. Пусть всего у нас Р+Л карт (Р — это количество карт, лежащих рубашкой вверх, а Л — количество карт, лежащих лицом вверх). Разделим их на две группы по Р и Л карт в каждой соответственно.
Так как мы не знаем, какие карты, в какую группу попали, придётся ввести ещё одну переменную Х — количество карт, лежащих лицом вверх в первой группе (напоминаю, что всего в этой группе Р карт). Значит, количество карт, лежащих в этой группе рубашкой вверх будет равно Р-Х.
Тогда во второй группе будет Л-Х карт, лежащих лицом вверх, и Л-(Л-Х) карт, лежащих рубашкой вверх. Но если мы раскроем скобки в последнем выражении: Л-(Л-Х) = Л-Л+Х = Х, то получим, что во второй группе (в которой всего Л карт) Х карт лежат рубашкой вверх.
Если же мы теперь перевернём все карты из второй группы, получится, что Х — это теперь количество карт, лежащих лицом вверх, а Л-Х — количество карт, лежащих рубашкой вверх. А это ровно то же самое, что а нас получилось в первой группе карт.
Схематично решение можно изобразить так.
Вот такая магия. Если было интересно, ставьте лайк и подписывайтесь на мой Телеграм, чтобы у вас было время подумать самостоятельно и обсудить решение в комментариях. Ниже же я подобрал для вас ещё несколько интересных задач: