После небольших каникул возобновляем трансляцию уроков математики, которые ведёт в сообществе «Математика — великая и ужасная!» профессор Нелли Литвак.
Напомним, в этой группе Нелли вместе с журналистом Аллой Кечеджан помогают взрослым гуманитариям освоить великую и ужасную науку «с нуля». И вот уже 3 месяца они постоянно доказывают, что: а) математику может постигнуть каждый; б) социальные сети — отличное пространство для образования.
Учёные давно доказали, что «математического гена» не существует. Математику, как и велосипед, в состоянии осилить любой человек.
Занятие 8. Как нужно начинать, чтобы выигрывать
Это задание не имеет ничего общего с нашем предыдущим материалом. Это просто игра, которую моя дочь принесла из школы. Игра называется «Одиннадцать».
Игроки называют числа по порядку от 1 до 11. Каждый игрок называет одно, два или три числа. Кто сказал «11», тот проиграл.
Например, играют трое.
А: 1, 2
Б: 3, 4, 5
В: 6, 7
А: 8
Б: 9, 10
В: 11
В проиграл.
ЗАДАНИЕ. Вы играете вдвоём. Если вы начинаете, то вы ВСЕГДА выигрываете. Вопрос — как? И главное: объясните ваше решение!
Проверить себя и посмотреть объяснения других участников группы можно в этом обсуждении.
В решении многие заметили, что для выигрыша надо называть числа на расстоянии 4 друг от друга: 2, 6, 10. Это очень правильная и действительно основополагающая закономерность в данной задаче.
Что я могу добавить?
Когда я решала эту задачку, то я автоматически начала решать «с конца». Моя первая мысль была не о кратности четырём. В первую очередь я подумала: «Что нужно сделать, чтобы назвать 10?» В конце игры ни о чём думать не надо. Кто сказал «10», тот автоматически выиграл. Если бы мы играли не в 11, а в 1, то это была бы не игра!
Как бы так сделать, чтобы сказать 10? Если до этого я скажу 7, 8 или 9, то ничего не получится, 10 назовёт противник. Зато если я скажу 6 — бинго!
Я могу сказать 10, что бы ни делал оппонент. Получается, что игра в 11 — это, по сути, игра в 7. Следующее «выигрышное» число найти совсем просто. Поскольку принцип игры не изменился, то я в той же ситуации, что и до этого, только всё сдвинулось на 4.
Чтобы сказать 10, нужно сказать 6 = 10 ─ 4. А чтобы сказать 6, нужно отступить ещё на 4 шага назад.
6 ─ 4 = 2. Значит, мои выигрышные числа 2, 6, 10.
Моё решение ничем не лучше других решений. Но это не случайно, что практически на автомате я стала «считать с конца».
Лирическое отступление. Зачем считать с конца
Такой подход — считать по этапам, начиная с последнего — лежит в основе очень мощного метода оптимизации, который называется Динамическое Программирование. И я так много им пользовалась, что это было первое, что пришло мне в голову!
В работе я часто сталкивалась с задачами оптимизации. Динамическое программирование — один из мощных математических методов оптимизации. Этот метод ещё в 1940-1950-х годах разработал Ричард Беллман. В университете (на четвёртом курсе — ха-ха, далеко мы с вами зашли!) нам объясняли первые принципы динамического программирования так:
Представьте себе, что вы едете на дачу. Вы можете выбрать Окский мост или Волжский (то есть дело происходит в моём родном Нижнем Новгороде). После Окского — два городка и три железнодорожных переезда. После Волжского — шоссе без светофоров. Зато сейчас Окский мост свободен, а на Волжском пробка. Через какой мост ехать?
Может, мы немножко постоим на Волжском и потом долетим по шоссе? А может, на шоссе тоже будет пробка? А после Окского моста можно либо застрять на переезде, либо не застрять. Так что оптимальное начало выбрать трудно.
Теперь представьте, что мы почти доехали до дачи, и у нас две дороги: асфальтовая длинная в объезд или короткая просёлочная по прямой. Тут всё понятно. Если сухо — едем по проселочной, если грязно, то по асфальту. Неважно, через какие мосты и пробки мы добирались до этого последнего кусочка. Если у нас есть несколько вариантов для последнего этапа, мы всегда можем выбрать лучший. Потому что этап у нас остался только один, и нам всё про него известно.
А потом к оптимальному окончанию нужно прибавить несколько возможностей для предыдущего этапа и выбрать лучшую комбинацию двух последних этапов, и так далее, с конца до начала. Примерно так и работает динамическое программирование.
Я много раз сталкивалась с динамическим программированием в самых разных контекстах. Постепенно, после большого количества теории и научной практики, у меня развилась неискоренимая привычка считать с конца!
Динамическое программирование применяется повсюду. Например, оно легло в основу Алгоритма Витерби, который часто используется в распознавании речи.
Вот так от детской игры мы подошли к серьёзным практическим задачам. В следующий раз начнём разбираться с великими и ужасными логарифмами. Читая активные обсуждения в сообществе, я не сомневаюсь — гуманитарии с этим справятся.
