?

Log in

No account? Create an account

Previous Entry Поделиться Next Entry
Субботние развлечения: любимая задача
trim_c

На сайте N+1 в субботнем выпуске опубликовали любопытную но на мой личный взгляд очень трудную задачу, познакомьтесь.

В компании «Тинькофф» работает много выпускников математических и естественно-научных специальностей, поэтому мы попросили некоторых из них поделиться с читателями N + 1 самым сокровенным — любимой математической задачей. Как известно, такая задача есть у всякого, кто увлечен математикой. Более того, зачастую любимая задача позволяет узнать о человеке больше, чем его CV

N + 1: Представьтесь, пожалуйста.

Привет, меня зовут Антон.

Чем вы занимаетесь в компании «Тинькофф»?

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

Расскажите, какая задача у вас самая любимая?

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

В каком контексте вы столкнулись с ней?

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


Антону задача кажется несложной. На мой взгляд, прикидочно она выглядит весьма непростой.
И потому я предлагаю вам решить эту же задачу в одномерном варианте.

На отрезок длины L (не обязательно целое число, забавно что считать L целым, решать даже сложнее - ИМХО) два игрока поочередно выкладывают отрезки длины единица. Найти оптимальную стратегию для одного из игроков.

Очевидно, что задача намного проще. Тем не менее она уже достаточно сложна для субботнего развлечения.

У каждого своя любимая задача - это правда. Для меня любимая задача - найти на сколько частей пространство размерности N делят k гиперплоскостей общего положения (можно и спрашивать каково максимальное число частей пространства, на которые его делят k гиперплоскостей, ответ будет как раз для гиперплоскостей общего положения)

Это замечательная задача по числу идей, на которых можно демонстрировать правильный подход к задачам вообще
Метки: ,

Последние записи в журнале



  • 1
Первый пятак кладется в центр стола. В дальнейшем нужно просто отзеркаливать ход соперника.

вы правы Причем это справдливо для люой фигуры имеющей центр симметрии

Edited at 2019-08-17 10:29 (UTC)

Разве при таком подходе главным не становится - кто первым из игроков сделает ход?

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

А если Ваш соперник прикинул на ход раньше?
При отзеркаливании хода противника у Вас ВСЕГДА есть такой же ход, какой сделан им только что.

**А если Ваш соперник прикинул на ход раньше?***

Ну так тут и начнется самое интересное, в плане интервалов. )))

***При отзеркаливании хода противника у Вас ВСЕГДА есть такой же ход, какой сделан им только что.***

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

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

Попробуйте решить мою любимую хотя бы для трехмерного случая
Не обязательно найти формулу - достаточно найти процедуру - для формулы это вторая задача

Да, многолетнее отсутствие практики дает о себе знать. С двухмерной задачей разобрался: N(n)=n(n+1)/2+1. Понимаю что для трехмерной задачи эта формула будет описывать приращение. А вот на общую формулу пока "не вытянул".

Edited at 2019-08-17 20:13 (UTC)

Фактически вы задачу решили. Причем для любой размерности

Это задача с легендой - и с кучей идей.

Легенда - немцы подбрасывали любопытные задачки британским математикам работавшим над ЭНИГМОЙ

Первая идея формулы - вы продифференцировали целочисленное выражение - а потом интегрируете - т.е. нужны граничные условия

Так думал я пока не заметил очевидный ответ

Edited at 2019-08-18 08:36 (UTC)

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

Докажем формулу

Дифференцируя формулу получаем, что (n+1)-я гиперплоскость добавляет в разбиение n+1 частей.
Докажем это, сначала для плоскости.
(n+1)-я прямая пересекает другие n прямых в n точках, разбивая себя на n+1 интервалов.
Возьмем произвольный интервал разбиения, и в нем внутреннюю точку, а также же две близкие к ней точки (ближе, чем до концов интервала, и до всех точек пересечения прямых), находящиеся по разные стороны от прямой. При наличии этой прямой эти точки находятся в разных частях разбиения, а при ее отсутствии - в одной части. Таким образом, каждому интервалу соответствует один дополнительный элемент разбиения.
Доказательство для размерности N.
(n+1)-я гиперплоскость пересекает n других гиперплоскостей по n (N-2)-плоскостям. Проведем в (n+1)-й гиперплоскости прямую, перпендикулярную этим (N-2)-плоскостям. Эта прямая пересекает n других гиперплоскостей в n точках, разбивая себя на n+1 интервалов. Далее аналогично двумерному случаю.
Формула доказана.
7 лет назад ВП предлагал мне эту задачу, но я не справился. Зная ответ, данный Вами, получилось, как мне кажется.

Re: Докажем формулу

Поспешил-людей насмешил.
Вторая попытка.
1.Обозначим число частей f(N,q).
2.Если q<=N, то f(N,q)=2^q.
3.Пусть q>=N. Увеличим число гиперплоскостей, добавив еще одну. Пересечения с (q+1)-й гиперплоскостью других гиперплоскостей создадут на этой гиперплоскости разбиение с числом частей, равным f(N-1,q).
4. Каждой части в разбиении (q+1)-й гиперплоскости соответствует разбиение на 2 части одной из частей разбиения всего пространства. Таким образом, при добавлении гиперплоскости число частей пространства увеличивается на f(N-1,q).
5. Получаем рекуррентную формулу
f(N,q+1)= f(N,q)+ f(N-1,q).
Задача решена.
Перевести формулу из рекуррентного вида в аналитический – вопрос отдельный.

>>Придумайте выигрышную стратегию для одного из игроков, которая всегда приводит к победе.
Допустим такая стратегия существует. Допустим оба игрока знают ее. Могут ли они оба выиграть? Как принято говорить в математике мы пришли к противоречию )
Приходим к выводу что для первого и второго хода стратегии должны быть разные.

У меня любимой задачи нет, но во время обучения пытался решить частный случай теоремы Ферма для n=3. Формулировал ее примерно так: существует ли куб разрезанный на n^3 (в степени 3) разных кубиков из которых возможно сложить два целых куба другого размера. Надеялся как-то найти опоры в реальном мире, не абстрактном ))
Провозился с задачей с неделю и как в каком-то рассказе Лема пришел к неопровержимому выводу 0=0 ) Наш препод по матану с счастью рассказывал сколько математиков сошло с ума пытаясь решить общую задачу, так что я бросил это дело )

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

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

Отрезок длинны L, не целый, игроки выкладывают отрезки длины единица. Т.е. L=N+d, где N - это целое число. При этом очевидно что L>2. Иначе игра идет в один ход.

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

Тогда я стал думать как понять минимальное число ходов. И вывел какую формулу Ax+By=L=N+d, где A - отрезки 1-ой длины, а В-отрезки меньше 1, но число отрезков А(которое х)<N. Т.е. если между А и N есть нечетное число , то для первого игрока есть выигрышная стратегия. И не трудно прийти к выводу, что такая стратегия есть всегда, так как при любом размере отрезка L нечетное число будет. И если первый игрок воспользуется такой стратегией, то он всегда будет побеждать, чтобы не делал второй игрок. И у второго игрока есть шанс только в том случае, если первый игрок ошибется во всех ходах, так как любой отрезок после первого хода можно рассматривать как стартовый. а потом я загуглил симметричную стратегию по описанию игры с монетами, и понял, что это просто разновидность игры в 21. До симметричного размещения первого 1ого отрезка я бы не догадался все равно, так как отчего то считал, что отрезки нужно размещать строго слева на право последовательно.

Edited at 2019-08-17 20:38 (UTC)

Первый выигрывает всегда в области имеющей центр симметрии.
См. самый верхний пост sid_zp

  • 1