Математические головоломки и развлечения - [112]
3. Независимо от того, сколько листков бумаги берут играющие в гугол, вероятность выбрать листок с наибольшим числом никогда не опускается ниже 0,367879 (предполагается, что играющий придерживается оптимальной стратегии). Эта величина обратна числу е и служит пределом вероятности выигрыша, когда число листков стремится к бесконечности.
Если для игры взято десять листков (это число особенно удобно), то вероятность выбрать листок с наибольшим числом равна 0,398. Оптимальная стратегия состоит в том, чтобы, перевернув три листка, выбрать наибольшее из значащихся на них чисел, а затем продолжать переворачивать листки до тех пор, пока не встретится еще большее число. При достаточно продолжительной игре такая тактика гарантирует выигрыш в двух случаях из пяти возможных.
Анализ игры в гугол сводится к следующему. Пусть π — число листков бумаги, взятых для игры, р — число листков, перевернутых до того, как было выбрано число, превосходящее любое из чисел, проставленных на этих листках. Перенумеруем листки по порядку от 1 до π. Пусть (k + 1) — номер листка с наибольшим числом. Для того чтобы мы могли выбрать наибольшее число, k должно быть не меньше р (в противном случае, при k < р, наибольшее число будет для нас безвозвратно «утеряно», так как окажется на одном из р первых листков), при этом наибольшее из чисел на листках от 1 до А; должно одновременно быть наибольшим из чисел от 1 до р (в противном случае мы бы не смогли дойти до наибольшего из всех чисел, так как остановили бы свой выбор на наибольшем из чисел, значащихся на листках с номерами от 1 до р). Вероятность найти наибольшее число, если оно выписано на (k + 1) — м листке, равна p/k, а вероятность того, что наибольшее число действительно стоит на (k+1) — м листке, равна 1/n. Поскольку наибольшее число может стоять только на одном листке, мы получаем для вероятности «накрытия» этого числа следующую формулу:
При заданном значении п (числа листков) формула позволяет находить оптимальное значение р (числа листков, которые нужно перевернуть) — то значение р, при котором выписанное выражение достигает максимума. При π, стремящемся к бесконечности, p/n стремится к 1/e, поэтому хорошим приближением для р можно считать ближайшее к n/e целое положительное число. Итак, при игре с п листками стратегия заключается в том, чтобы переворачивать листки до тех пор, пока их число не превысит n/e, а затем выбрать первое же число, большее максимального, из чисел, записанных на перевернутых n/e листках.
Разумеется, приведенное выше рассуждение исходит из предположения о том, что играющему не известны наибольшее и наименьшее из чисел, выписанных на листках, и поэтому, увидев очередное число, он не может судить о том, насколько близко оно к верхней или нижней границе того отрезка числовой оси, которой принадлежит выбранное число. Если играющий располагает такими сведениями, то все рассуждение становится неприменимым. Например, если вместо листков бумаги при игре в гугол взять десять долларовых купюр с их банковскими номерами, то, вытащив доллар, номер которого начинается с девятки, вам лучше всего объявить этот номер наибольшим. По аналогичным причинам игра в гугол, если говорить строго, неприменима и к задаче о девушке, жаждущей выйти замуж, ибо, как отметили многие читатели, девушка, по-видимому, великолепно осведомлена о достоинствах своих поклонников и подходит к ним с определенными мерками. Если первый же, кто делает ей предложение, очень близок к ее идеалу, то, как написал нам один из читателей, «она будет просто дурой, если не примет предложения».
Задача о максимизации значения выбранного объекта (а не вероятности выбора объекта с наибольшим значением), насколько известно, была впервые поставлена знаменитым математиком Артуром Кэли в 1875 году.
4. Примем за единицу длины ширину (или равную ей глубину) строя курсантов, а за единицу времени — то время, которое требуется им, чтобы пройти единицу длины. В принятых единицах скорость передвижения строя также будет единичной. Пусть х — полное расстояние, пройденное терьером (его скорость будет выражаться той же величиной х). Когда пес бежит к первой шеренге, его скорость относительно курсантов равна х — 1. При возвращении в последнюю шеренгу скорость терьера составляет х + 1. Каждый раз он пробегает (относительно строя) расстояние 1 и на путешествия в оба конца затрачивает единицу времени. Это позволяет нам составить уравнение
которое можно переписать в виде квадратного уравнения
Положительный корень этого уравнения равен
Умножив его на 15, получаем окончательный ответ: 36,15… м. Иначе говоря, терьер пробегает расстояние, равное длине стороны квадрата, в форме которого выстроены курсанты, плюс расстояние, равное длине диагонали того же квадрата.
Аналогичным образом получается приближенный ответ и для лойдовского варианта задачи, когда собачка бегает вокруг марширующего строя.
Пусть, как и прежде, ширина строя равна единице и единице равно время, за которое курсанты проходят 15 м. Тогда и скорость их также равна 1. Пусть
