Математическая головоломка

Рейтинг: 4.6 из 5
Автор
Вадим Соколов
Рейтинг автора
4.6

Эта крутая головоломка (и решение) принадлежит моему другу Майку.

Алиса тайно выбирает два разных действительных числа неизвестным способом и помещает их в два (абстрактных) конверта. Боб случайным образом выбирает один из двух конвертов (при правильном подбрасывании монеты) и показывает вам номер в этом конверте. Теперь вы должны угадать, больше или меньше число в другом закрытом конверте, чем то, которое вы видели.

Есть ли стратегия, которая дает вам более чем 50% шанс правильно угадать, независимо от того, какую процедуру использовала Алиса для выбора чисел?

Сначала я подумал, что нет, или что проблема была парадоксально определена, но оказалось, что это совершенно верно, и ответ - «Да». См. Мой первый комментарий для примера одной такой выигрышной стратегии.

Эта головоломка похожа на парадокс двух конвертов , но не то же самое . Чтобы прочитать больше, отнимите время, см. Список парадоксов Википедии .

Поделись этим:

Нравится:

Связанный

411 ответов на «Math Puzzle»

Наберите номер, на котором вы увидели «х». Используйте логистическую функцию, чтобы вычислить p (x) = 1 / (1 + e ^ -x). Выберите случайное действительное число от 0 до 1. Если оно меньше p (x), угадайте «меньше». В противном случае угадывай «выше».

Другими словами, угадать «ниже» с вероятностью p (x) и «выше» с вероятностью 1-p (x).

Это работает, потому что p (x) - это функция, которая равна 0 на отрицательной бесконечности, 1 на положительной бесконечности и монотонно увеличивается между ними. Таким образом, для любой пары чисел, если вы назовете меньшее A и большее B, у вас (немного) больше шансов угадать «меньшее», если вы видели B, чем если вы видели A. Ваши общие шансы правильно угадать - учитывая, что существует 50% вероятность, что вы видите A, и вероятность 50%, что вы видите B, - это:

N = 0,5 * (1-p (A)) + 0,5 * p (B)

(помня, что p (x) равно 1 / (1 + e ^ -x))

Поскольку p (A) всегда меньше p (B), N всегда больше 50%. Если Алиса выбрала 1,0 и число пи, ваши шансы правильно угадать 61,37%. Если Алиса выбрала 10 и 11, ваши шансы угадать правильно составляют 50,00053%. Независимо от того, какие два числа выбрала Алиса, шанс угадать правильно всегда выше 50%. Иногда лучше всего на крошечную, крошечную сумму, но всегда лучше.

Здесь важно помнить, что несуществует такой вещи, как случайная выборка всех чисел. Невозможно выбрать одно целое число случайным образом, при этом каждое целое число имеет равные шансы быть выбранным. (Подробнее об этом см. В этой статье.) Точно так же не существует такой вещи, как случайно выбранная функция из всех возможных. Вы не можете попытаться смоделировать процесс Алисы, вычислив шансы, что ее процедура (или числа) попадет в ту или иную категорию, потому что вы не знаете, какую процедуру она использует.

Для другой версии этой головоломки см. Вопрос B здесь и решение здесь. Если что-то из этого кажется вам неправильным, попробуйте написать программу для моделирования игры, как вы ее понимаете, и самостоятельно измерить вероятности. Вы обнаружите, что не существует метода, который Алиса могла бы использовать для выбора чисел, который удерживал бы вас от хотя бы немного большего, чем даже шанс на победу (хотя, если она выберет два особенно больших положительных или отрицательных числа, разница, вероятно, будет слишком мала, чтобы мера).

Вы правы в выборе случайного действительного числа, но вы никогда не заявляли, что это число было выбрано случайным образом. Вы только что сказали, что она выбрала два числа, оговорив только, что они не равны. Если она может выбрать произвольное действительное число (почти все из которых нельзя описать логикой, которая является счетной), то почему она не может выбирать произвольно большое число так же часто, как любое другое?

Другими словами, если она может придумать бесконечную последовательность цифр от 1 до 9 (десятичное расширение), почему она не может выбрать место из бесконечного множества с равной вероятностью, чтобы поставить десятичную точку, если она хочет?

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

Это похоже на парадокс теории игр: выберите действительное число x>0, и ваш выигрыш будет равен 1 / x. Какая ваша лучшая стратегия / равновесие по Нэшу? Конечно, нет, потому что x можно выбрать так, чтобы ваша выплата в размере 1 / x произвольно велика.

xkcd писал (а):

>>закрытый конверт больше или меньше того, что вы видели.

Когда вы говорите больше, вы имеете в виду более высокое абсолютное значение (дальше от нуля) или более положительное (близкое к + inf)?

Первое, что мне пришло в голову, было: если число отрицательное, я предполагаю, что другое число больше, а если оно положительное, я предполагаю, что другое число меньше. Кто-нибудь знает, где я ошибаюсь?

Я был с тобой до тех пор, пока не набрал номер «х».

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

Использование логистической функции здесь не требуется: вы можете просто выбрать любое действительное число y, которое вам нравится, и если x больше, тогда y скажет «больше», а если x

Конечно, использование чего-то вроде логистической функции с последующим равномерным выбором числа из [0,1] позволяет вам выполнять вероятные вычисления в комментарии выше, а не просто доказывать, что вы выигрываете более чем в половине случаев.

Поскольку это решение не содержит обозначений ABS, я думаю, было бы безопасно предположить, что он использует общее понимание «большего».

«Привет, Алиса, это число в другом конверте больше или меньше». Вероятность правильного угадывания зависит от того, доверяете ли вы Алисе. Не говоря уже о Бобе.

Всегда выбирайте больше, и у вас будет 100% шанс на победу.

Существует конечное количество чисел меньше, чем первое выбранное, и бесконечное количество больше, чем.

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

Мой вопрос: имеет ли значение конкретная используемая функция, если у нее одинаковые граничные условия и постоянно возрастающее поведение? Например, будет ли p (x) = 1 / (1 + 2 ^ -x) или p (x) = atan (x) / pi + 1/2 также работать в долгосрочной перспективе?

Кстати, я не оспариваю ваше решение, что типично для странностей в Анализе. Я просто хочу заявить, что существует разница между произвольным действительным числом, которое математики принимают все время (пусть x будет действительным числом ...), и равномерно распределенным случайным действительным числом, что, как вы утверждаете, невозможно (распределение везде должно быть 0, но иметь интеграл от -oo до oo, равный 1).

Если вы мне не верите, вот мое доказательство того, что 0 не является действительным числом: пусть x будет действительным числом. Затем, поскольку вероятность того, что x = 0 равна 0 (см. Ссылку в исходном сообщении), тогда x! = 0. Поскольку x было произвольным, никакое действительное число = 0. Следовательно, 0 не является действительным числом.

Новый вопрос: могли бы вы все еще сделать это, если бы A и B могли быть равны друг другу (в этом случае вышеприведенная стратегия не работает)?

Из любопытства, зачем нужна часть «выбрать случайное число от 0 до 1»? Почему бы просто не сказать: «Если p (x)

Я полагаю, что 0 должно быть выбрано произвольно, чтобы быть на той или иной стороне, но если вы вытащите 0, ваши шансы в любом случае составляют 50%, верно? Или мне что-то здесь не хватает?

«Теперь вы должны угадать, больше или меньше число в другом закрытом конверте, чем то, которое вы видели».

Нет варианта C) для равных?

Так что, если Алиса выберет одно и то же число дважды, вы каждый раз будете проигрывать.

Вы никогда не заявляли, что x было случайно выбранным действительным числом. Следовательно, обсуждение вероятности невозможно, поскольку такое обсуждение потребует знания распределения.

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

Когда математики говорят «пусть x будет действительным числом», они обсуждают свойства, относящиеся ко всем действительным числам, а не к конкретному числу. В этом нет ничего странного.

Вернемся к предлагаемому решению: это решение основано на том факте, что ни один процесс, процедура, человек или компьютер не могут генерировать действительно случайное число. Любое равномерно выбранное случайное число будет бесконечно длинным слева И справа от десятичной точки. Я предполагаю, что это решение основано на том факте, что любой человек или машина будут генерировать «короткие» числа?

Вы произвольно выбрали функцию вероятности чисел, которые, вероятно, выберет Алиса. Скорее всего, это неправильно.

Вам следовало либо провести психологическое исследование, чтобы определить, какие числа люди могут выбрать (научный ответ), либо остановиться на том, что «не существует такой вещи, как случайная выборка всех чисел». (ответ математики).

Я ввел функцию в Grapher в Mac OS X, и вот что у меня получилось: http://flickr.com/photos/boredzo/4344177011/

Я ввел функцию неправильно, или это ошибка Grapher, или функция, как указано, неверна?

За исключением крайних случаев * (см. Ниже)

Если оба числа с вероятностью 50% будут больше 0 (и с вероятностью 50% будут меньше 0)

и вы смотрите на одно из чисел (X), и оно больше 0,

скрытое число (H) может быть любым числом больше X или любым числом меньше 0 и меньше X.

потенциальное количество значений H может быть, если меньше, чем X: ∞ + X или если больше, чем X: ∞ - X,

соотношение чисел H, которые потенциально меньше, чем X, составляет: (∞ + x) / (∞ - h)

что, похоже, будет больше 1.

Это больше единицы? интуиция подсказывает, что будет, но я думаю, что

∞ - n = ∞ (поправьте меня, если я ошибаюсь),

поэтому (∞ + X) / (∞ - X) = ∞ / ∞ = 1/1

Итак, если Алиса выберет * любые * два вещественных числа (от -∞ до ∞), тогда не будет больше чисел, которые больше (или меньше), чем первое число, на которое вы смотрели. Таким образом, вероятность правильно угадать составляет всего 50%. Однако, если есть шанс, что Алиса выберет меньший диапазон, чем этот, тогда соотношение станет:

(n + x) / (n - h), что больше 1

(где n - очень большой, но конечный набор действительных чисел)

поэтому я думаю, что если вы догадались, что H меньше, чем X, когда X>0 (и наоборот),

то у вас есть как минимум 50% -ный шанс быть правым,

если только Вселенная не против вас, и подбрасывание монеты каждый раз сбивает вас с толку. вероятность 1 / (2 ^ n), где n - количество бросков (предположений)

* Вы также получаете интересный крайний случай, когда (скажем) одно число равно 4, а другое - 3,999… это два разных действительных числа, но они имеют одинаковое значение.

Питер: Вы действительно правильно ввели функцию.

Это не 0 при -10 или 1 при +10 .. это просто так выглядит из-за ограниченного разрешения экрана.

Функция get очень, очень близка, но на самом деле никогда не достигнет 0 или 1, за исключением тех пределов, где x ->+ - бесконечность. Линии при y = 0 и y = 1 известны как асимптоты. См. Http://en.wikipedia.org/wiki/Asymptote для получения дополнительных сведений, если вам интересно.

Питер: Это не 0 при -10 и 1 при +10, просто похоже. Функция асимптотически приближается к 0 с отрицательной стороны и асимптотически ближе к 1 с положительной стороны, что означает, что она приближается все ближе и ближе, но никогда не достигает ее. И монотонно просто означает, что он увеличивается только между переходами от более низких значений к более высоким значениям x. Вид кривой не исключает этого.

Питер, похоже, проблема в том, что Grapher не обладает достаточной точностью, чтобы отличить функцию от 0 или 1 за пределами интервала [-10, 10]. Функция становится очень, очень близкой к нулю, когда вы приближаетесь к -inf, но никогда не достигает его. Точно так же он становится очень близким к единице по мере того, как вы приближаетесь к + inf, но никогда не достигнете этого.

WV: у амеб есть (… души тоже?)

Я чувствую, что проблему можно упростить.

Вы случайным образом выбираете меньшее или большее из двух чисел.

Если ваше число больше нуля, оставьте его. В противном случае замените его.

(Я не учитываю возможность того, что число будет равно нулю, так же как вы не учитываете возможность того, что число равно p (x).)

Если вы выбрали большее число, вы с меньшей вероятностью его обменяете, потому что оно больше нуля, чем меньшее число.

Как можно выбрать случайное действительное число без уточнения? Оставляя в стороне очевидный парадокс, что любой результат будет иметь коэффициент 1 / бесконечность, я даже не могу придумать алгоритм, который бы возвращал неквалифицированное случайное вещественное число за конечное время.

Я выбираю A (1000, 1001) и A (1001, 1000). Что больше?

Функция кажется правильной. Это монотонный серп.

Если x ->-inf, знаменатель переходит к + inf, а функция переходит к 0.

Если x = 0, функция переходит к 1 / (1 + 1) = 0,5

Если x ->+ inf, знаменатель переходит к 1 и функция переходит к 1

Некоторое время назад я работал над этой головоломкой. Думаю, можно выбрать любую функцию вероятности (для переключения), которая монотонно убывает. Его легче понять для конечного диапазона чисел, но идею можно легко распространить на множество всех действительных чисел.

Какая интересная загадка. После построения графика предоставленной функции и объяснения нет процесса, который мог бы выбирать случайные числа с равным распределением из бесконечного множества, я думаю, что понимаю это интуитивно, но математика не имеет особого смысла.

Кроме того, поскольку я уверен, что это никогда не утомляет, я люблю ваш комикс и с нетерпением жду попытки расшифровать вашу книгу. Видя, как мне удалось упорствовать только около 2 часов, прежде чем искать ваш ответ на этот вопрос и безумно высокий рейтинг страницы в Google на форумах, я, вероятно, случайно или целенаправленно буду искать все ответы.

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

(Ваш подход к сравнению случайного числа в (0, 1) с p (x) на самом деле просто сравнение x со случайным числом из (-inf, inf), выбранным с обратным логистическим распределением.)

Хорошо, вот, к чему сводится ваша процедура, с точки зрения статистики:

–Предположите распределение по всем элементам диапазона, в котором рисует Алиса. Это может быть нормальное (гауссово) распределение или что-то безумное, ориентированное на четные числа, или неизвестно что.

–Запишите его кумулятивную функцию распределения. Это $ cdf (x) = int_ ^ xf (y) dy $, где f (y) - ваше распределение вероятностей, и вы интегрируете от нижней части диапазона до x, чтобы найти CDF в Икс.

- Сделайте свою ничью, затем посмотрите в своей таблице CDF (x), чтобы найти шансы того, что истинное значение меньше x. Если интеграл проб. распределение до x составляет 92% распределения, тогда у вас есть 92% шансов, что другой конверт меньше.

Конечно, шансы, которые вы получите в конце, находятся в контексте модели, которую вы использовали на первом этапе. То есть, расчет шансов N = 0,5 * p (x) ... использует выбранную вами функцию p (.), А не ту, которая объективно верна, поэтому вы говорите, что шансы лучше, чем 50/50, на основе субъективных оценок. шансы, которые вы придумали.

Чтобы быть точным, логистическая функция, которую вы используете, - это CDF логистического распределения (см. Http://en.wikipedia.org/wiki/Logistic_distribution), поэтому вы предположили, что Алиса вначале делает ничьи из логистического распределения, а затем оцените шансы получить правильный ответ, используя то же предполагаемое распределение.

Вы можете использовать другие распределения: почему бы не Нормальное распределение, сосредоточенное вокруг нуля, или Нормальное распределение, сосредоточенное вокруг пятнадцати, оба из которых имеют соответствующий домен, и оба из них создают CDF, который, конечно, равен нулю при $ -infty $ и единице по цене $ + infty $. Или, может быть, просто точечная масса в нуле, которая выражается в том же нейтральном убеждении, что положительное так же вероятно, как и отрицательное, которое вы выражаете в предположении логистического распределения, без лишнего багажа?

Я мог бы продолжить: приведенная выше установка также неявно предполагает, что A и B нарисованы независимо. Логистическое распределение предполагает, что ноль - это середина пути, и что значения, близкие к плюсовой или минусовой бесконечности, менее вероятны, чем значения, близкие к нулю. Мы предполагаем, что 10 менее вероятно, чем девять (т. Е. Что Алиса не человек). Все это, вероятно, в порядке, но добавьте структуру, которая не была указана в задаче. Учитывая то, что было написано, единственное не неверное предположение о распределении будет нейтральным априорным, как неправильное равномерное распределение (p (x) = 1 для всех x), где CDF безнадежно неопределен, и мы вернулись к тому, что способ угадать, какой конверт имеет большее значение. Вместо этого вы сделали ряд предположений в логистическом распределении, а затем использовали эти предположения для определения субъективных вероятностей.Это прекрасный человеческий подход к проблеме, но он работает именно в той степени, в которой вы верите в предположения.

Когда вы говорите: «Здесь важно иметь в виду, что не существует такой вещи, как случайная выборка всех чисел». Вы немного преувеличиваете. Вы только что продемонстрировали (косвенно), как взять случайную выборку реальных чисел, а не равномерно взвешенную. В конце концов, ваша стратегия изоморфна «Выберите случайное действительное число от 0 до 1 и назовите его« x ». Вычислить случайное действительное число r (x) = - ln ((1 / x) - 1). Если оно ниже, чем число, которое вы видели, угадайте «меньше». В противном случае угадывай «выше».

Просто придираться, но не совсем правильно говорить, что нельзя выбирать из реальных чисел случайным образом, просто нельзя выбирать из реальных чисел с равномерным распределением. Случайно! = Униформа.

Что ж, если полагаться на p (x) хорошо, то p (x-100) или p (x + 100000) тоже хорошо?

Тем не менее, должны ли мы выбирать только одну функцию, чтобы добиться успеха, или мы можем произвольно переключаться между любой из них?

@Aaron Meurer - Вы сказали:

«Другими словами, если она может придумать бесконечную последовательность цифр от 1 до 9 (десятичное разложение), почему она не может выбрать место из бесконечного множества с равной вероятностью для размещения десятичную точку, если она хочет? "

Потому что выбор случайного места для десятичной точки - это то же самое, что выбор случайного натурального числа (т. Е. Позиции, в которой следует разместить десятичную точку). Однако невозможно выбрать случайное натуральное число единообразно.

@Peter Hosey - изображение, с которым вы связались, является правильным графиком функции, и оно удовлетворяет всем свойствам, упомянутым Рэндаллом (монотонность и т. Д.). То, что что-то похоже на 1 или 0 на графике, не означает, что оно точно равно 1 или 0.

Питер Хози, вы не изобразили это неправильно, и это не указано неверно. Если вы увеличите масштаб очень близко к x = -10, вы увидите, что оно действительно близко к 0. Это никогда не будет точно нулевым, пока вы не достигнете -infinity.

Это была моя ошибка. У меня не было Grapher, показывающего мне достаточную десятичную точность, и когда я выбрал функцию при x = 10, я поверил этому, когда он заявил, что y = «1.0000». Увеличение и увеличение точности показало, что на самом деле она была асимптотической, как я первоначально думал (и отклонил на основании неточной выборки).

Спасибо Нику Девенишу за его нежный, понимающий комментарий к моему скриншоту, который побудил меня во второй раз взглянуть глубже. Спасибо также Тиму Паренти за его комментарий по поводу определения термина «монотонный».

Я вижу проблему в вашем решении. Вы полагаетесь на тот факт, что невозможно выбрать действительно случайное число из всех действительных чисел, а затем требуете в своем решении, чтобы вы выбрали действительно случайное число из [0, 1], несмотря на то, что эти множества имеют одинаковую мощность. Если в одном невозможно, то в другом невозможно.

Для тех, кто читает, кто этого не понимает, будет полезно, если вы примете во внимание следующее. Дано число от 0 до 1: если оно находится в [0, .5], удвойте его, чтобы получить число - любое число - в [0, 1]. В противном случае он находится в (.5, 1]. Вычтите 0,5 и удвойте, чтобы получить число в (0, 1], и возьмите обратное, чтобы получить любое число в [1, бесконечность). Это дает способ отображения любого точка в [0, 1] в любую точку в [0, бесконечность). Должно быть достаточно легко увидеть, как распространить это на все положительные и отрицательные числа. Поэтому, если вы можете выбрать действительно случайное число в [0, 1], вы можете тривиально сопоставить его с любым числом.

Вы рассчитали «общие шансы правильно угадать» как (что-то, что легко преобразовать в)

N = (1 + p (B) - p (A)) / 2

и поскольку p, как определено, строго монотонно возрастает (и B>A)

что и есть ваш желаемый результат.

Однако пусть q - любая другая строго монотонно возрастающая функция такая, что 0

но мы не можем сказать ничего более сильного, чем это.

Теперь, применяя тот же аргумент, который вы использовали для p (который основан только на том факте, что p удовлетворяет критериям, которые мы наложили на q, но не на каких-либо других деталях определения логистической функции), вы также должны заключить

Новости спорта

Изначально сайт создавался для пользователей со всех стран мира. Международный домен ориентирован на самых разных пользователей. Страницы сайта переведены на 46 языков, среди которых есть и азербайджанский. Это выгодно выделяет платформу на фоне конкурентов, так как многие из них либо не работают на территории данной страны, либо не имеют местной локализации.

Больше новостей