А вот и обещанная задача
Есть гирьки массами 2⁰, 2¹, …, 2ⁿ грамм и чашечные весы, изначально находящиеся в равновесии. Нужно последовательно выставлять по одной гирьке на весы в некотором порядке так, чтобы в каждый момент времени правая чаша весов не перевешивала. Сколькими способами это можно сделать?
Есть гирьки массами 2⁰, 2¹, …, 2ⁿ грамм и чашечные весы, изначально находящиеся в равновесии. Нужно последовательно выставлять по одной гирьке на весы в некотором порядке так, чтобы в каждый момент времени правая чаша весов не перевешивала. Сколькими способами это можно сделать?
🎃31❤6👎6👍4🥰3🤩1
Так-так-так... Разыскиваются сильные команды, способные решить все задачи на JetBrains Math Challenge! Мне кажется, что в этот раз это будет не так просто... До окончания регистрации осталась всего неделя! А до самой олимпиады всего две недели (чуть меньше)!
(Кстати, это хороший способ потренироваться перед Колмом...)
(Кстати, это хороший способ потренироваться перед Колмом...)
JetBrains: Developer Tools for Professionals and Teams
JetBrains Academy Youth Challenge
Ultimate coding and math challenge for the school students from JetBrains Academy
😁5❤4
Forwarded from Fpmath comments
Пользуясь случаем, напомню следующую задачу.
У Белочки есть бесконечно много орехов: по одному ореху каждой из
масс 1 г, 2 г, 3 г, \dots. Она взяла n мешков, положила в каждый по
конечному числу орехов, после чего написала на каждом мешке суммарную
массу лежащих в нем орехов.
а) Докажите, что можно было собрать мешки с
такими же массами, использовав не более 4n-3 орехов.
б*) Какова точная оценка на число орехов, которого заведомо достаточно?
Пункт б) я решать не умею.
У Белочки есть бесконечно много орехов: по одному ореху каждой из
масс 1 г, 2 г, 3 г, \dots. Она взяла n мешков, положила в каждый по
конечному числу орехов, после чего написала на каждом мешке суммарную
массу лежащих в нем орехов.
а) Докажите, что можно было собрать мешки с
такими же массами, использовав не более 4n-3 орехов.
б*) Какова точная оценка на число орехов, которого заведомо достаточно?
Пункт б) я решать не умею.
❤17👍1
Forwarded from Математические кружки | «МТ кружки»
Опубликуем одну из задач нашей сегодняшней олимпиады «JetBrains Youth Challenge», автор — Д. В. Афризонов.
В лиге старших классов она была 4-й из 8, и её решили 8 команд из 50. А вы сможете?
#мт_задача
В лиге старших классов она была 4-й из 8, и её решили 8 команд из 50. А вы сможете?
#мт_задача
👍2❤1
Forwarded from Олимпиадная геометрия
Пост благодарности! Я бы хотел поблагодарить всех участников олимпиады за то, что они не поленились потратить свое воскресное время на решение задач, борьбу с лингвистическими и, порой, техническими трудностями, и это при том, что олимпиада эта не дает практически никаких бенефитов — без вас эта олимпиада была бы неполноценной.
Я бы хотел поблагодарить членов жюри, которые присоединились слушать задачи. Тоже ведь трудно заставить себя поучастовать в воскресном мероприятии, которое ничего кроме радости общения с единомышленниками тебе не принесет. Членам жюри тоже пришлось решать лингвистические и технические задачи, которые ставили перед ними участники. Спасибо вам! Хотелось бы, чтобы нас становилось больше и прослушка проходила в более спокойном режиме!
Я бы очень хотел поблагодарить авторов задач, которые не пожалели потратить свои творения на в общем-то никому пока неизвестную олимпиаду. В этом году, на мой взгляд, вариант получился значительно более интересным именно благодаря вам. Спасибо и тем, кто прислал свои задачи, но задачи нам почему-то не подошли. Я очень надеюсь, что вы не перестанете придумывать задачи и будете столь же отзывчивы на наши просьбы о помощи!
Я бы, конечно, хотел поблагодарить организаторов, потому что без их инициативы это мероприятие уж точно не состоялось бы. Организаторам всегда приходится не сладко, а работу их почти никто не видит.
Ну и конечно, я хотел бы поблагодарить своих коллег по методической комиссии!
Надеюсь олимпиада будет расти! И мы проведем ее еще лучше в следующем году. Пока что все задачи можно найти на аопсе. Но очень скоро мы доделаем и официальный файлик с условиями и решениями.
Я бы хотел поблагодарить членов жюри, которые присоединились слушать задачи. Тоже ведь трудно заставить себя поучастовать в воскресном мероприятии, которое ничего кроме радости общения с единомышленниками тебе не принесет. Членам жюри тоже пришлось решать лингвистические и технические задачи, которые ставили перед ними участники. Спасибо вам! Хотелось бы, чтобы нас становилось больше и прослушка проходила в более спокойном режиме!
Я бы очень хотел поблагодарить авторов задач, которые не пожалели потратить свои творения на в общем-то никому пока неизвестную олимпиаду. В этом году, на мой взгляд, вариант получился значительно более интересным именно благодаря вам. Спасибо и тем, кто прислал свои задачи, но задачи нам почему-то не подошли. Я очень надеюсь, что вы не перестанете придумывать задачи и будете столь же отзывчивы на наши просьбы о помощи!
Я бы, конечно, хотел поблагодарить организаторов, потому что без их инициативы это мероприятие уж точно не состоялось бы. Организаторам всегда приходится не сладко, а работу их почти никто не видит.
Ну и конечно, я хотел бы поблагодарить своих коллег по методической комиссии!
Надеюсь олимпиада будет расти! И мы проведем ее еще лучше в следующем году. Пока что все задачи можно найти на аопсе. Но очень скоро мы доделаем и официальный файлик с условиями и решениями.
❤16👍6💔2
Forwarded from Математические кружки | «МТ кружки»
Опубликуем ещё одну задачу с олимпиады «JetBrains Youth Challenge», автор — К. А. Кноп.
В лиге младших классов она была 8-й из 8, и её решила всего 1 команда. Коллектив жюри ожидал большего количества решений этой задачи🙂
А оригинальная версия этой задачи была заметно сложнее — причём настолько, что методкомиссия даже не решилась вставлять её в лигу старших классов. Для продвинутых комбинаторов опубликуем и оригинальную формулировку тоже!
#мт_задача
В лиге младших классов она была 8-й из 8, и её решила всего 1 команда. Коллектив жюри ожидал большего количества решений этой задачи🙂
А оригинальная версия этой задачи была заметно сложнее — причём настолько, что методкомиссия даже не решилась вставлять её в лигу старших классов. Для продвинутых комбинаторов опубликуем и оригинальную формулировку тоже!
#мт_задача
❤11😇4👍2🔥2🗿2
Forwarded from Компьютерная математика Weekly (Grigory Merzon)
набросал вчера относительно длинный черновик поста с примерами того, что хотел бы закодить, но не могу (и почему именно не могу…)
но сегодня что-то посмотрел на один из примеров и решил, что глаза боятся, а… короче, код получился недлинный, но унесу все ж в комментарии
===
интересно считать количество разбиений разных фигур на доминошки
про прямоугольники 2×N и числа Фибоначчи и так все знают
а вот на картинке ацтекский бриллиант порядка 4 — сколькими способами его можно разбить на доминошки? а бриллиант порядка N?
тут общий ответ можно угадать по ответам для небольших N, но перебирать руками тяжеловато (для N=4 вариантов уже больше тысячи), компьютерный эксперимент действительно полезен
про разные способы этот ответ доказывать есть интересная брошюра Е.Смирнова «Три взгляда на ацтекский бриллиант», https://mccme.ru/free-books/dubna/smirnov-aztec.pdf
***
более естественная, казалось бы, идея — считать замощения обычного квадрата N×N… но там по ответам для маленьких N ничего угадать не возможно
все же перебрал на компутере и замощения квадрата 8×8 — в качестве ответа получилось название лекции С.Смирнова https://www.mathnet.ru/present18250
но сегодня что-то посмотрел на один из примеров и решил, что глаза боятся, а… короче, код получился недлинный, но унесу все ж в комментарии
===
интересно считать количество разбиений разных фигур на доминошки
про прямоугольники 2×N и числа Фибоначчи и так все знают
а вот на картинке ацтекский бриллиант порядка 4 — сколькими способами его можно разбить на доминошки? а бриллиант порядка N?
тут общий ответ можно угадать по ответам для небольших N, но перебирать руками тяжеловато (для N=4 вариантов уже больше тысячи), компьютерный эксперимент действительно полезен
про разные способы этот ответ доказывать есть интересная брошюра Е.Смирнова «Три взгляда на ацтекский бриллиант», https://mccme.ru/free-books/dubna/smirnov-aztec.pdf
***
более естественная, казалось бы, идея — считать замощения обычного квадрата N×N… но там по ответам для маленьких N ничего угадать не возможно
все же перебрал на компутере и замощения квадрата 8×8 — в качестве ответа получилось название лекции С.Смирнова https://www.mathnet.ru/present18250
❤9👍6🥰2🖕1
Forwarded from fp math (Fedor Petrov)
Всегда любил каплинги (они же спаривающие меры, они же многозначные отображения, они же полиморфизмы, они же планы перевозок и пр.) Идея в том, что для сравнения вероятностей двух событий надо умно реализовать их на одном вероятностном пространстве. Простой пример: красим каждую грань многогранника с вероятностью p независимо от остальных. Тогда вероятность того, что есть три попарно смежные покрашенные грани, возрастает с ростом p. Доказательство: пусть лучше каждая грань выбирает число от 0 до 1, и мы красим её, если число меньше p. Тогда наши события при разных p просто вложены друг в друга, и монотонность очевидна.
Лёша Куликов обратил внимание на свежую работу на эту тему.
Пусть n человек рассаживаются по k автобусам, выбирая, в который автобус сесть, равномерно и независимо. Рассмотрим вероятность p(k) того, что кто-то окажется единственным в своём автобусе (n считаем постоянным, а k переменным).
Теорема. p(k) возрастает по k при данном n.
Доказательство.Сравним p(k+1) и p(k). Можно считать, что дело обстоит так: сначала люди рассаживаются по k+1 автобусу, потом автобус семёрка ломается и люди оттуда рассаживаются по остальным. Нас интересуют вероятности двух событий: A - что до поломки был одинокий пассажир, B - что он есть после поломки и пересаживания. Сравним события A\B и B\A. Как могло произойти событие B\A? Скажем, Вася пересел из семёрки в пустую тройку, причём до поломки одиноких не было. Но до поломки могло быть так, что Вася - единственный в семёрке, потому что остальные, выбравшие семёрку, выбирали бы тройку (а всё остальное как было), а потом Вася пересел в тройку. В этом случае происходит A\B, и это имеет ту же вероятность.
Лёша Куликов обратил внимание на свежую работу на эту тему.
Пусть n человек рассаживаются по k автобусам, выбирая, в который автобус сесть, равномерно и независимо. Рассмотрим вероятность p(k) того, что кто-то окажется единственным в своём автобусе (n считаем постоянным, а k переменным).
Теорема. p(k) возрастает по k при данном n.
Доказательство.
arXiv.org
Lonely passengers: a short proof
A fixed number of passengers independently board one of several buses uniformly at random. The lonely passenger problem is to prove that the probability of at least one passenger being the only...
❤4🔥2🖕2👍1