Теория информации в задачах на взвешивание
Одна из первых задач здесь после начала учёбы в ШАДе была вот эта классическая задача на взвешивание. Удивительным образом сегодня я её закольцую с учётом нового опыта.
В задачах подобного типа часто встаёт вопрос, а почему нельзя обойтись меньшим количеством операций? Иногда это очевидно, но формальное доказательство очень длинное и скучное. Так вот недавно узнал о технике, которая в некоторых случаях справляется с доказательством в несколько строчек.
Суть очень простая. Допустим, вы загадали целое число от 1 до 4, а ваш друг хочет его узнать. Друг может задавать вам вопросы типа «это число больше / меньше n?» и получать ответы «да / нет». Какое минимальное количество вопросов небходимо задать, чтобы гарантированно узнать число? (Необходимое количество вопросов не обязательно будет достаточным). Заметим, что ответ бинарен, поэтому в лучшем случае исходное множество вариантов при каждом ответе сокращается в 2 раза. Так как дважды два – четыре, то необходимо задать не менее двух вопросов. На языке теории информации говорят, что нужно передать вашему другу не менее 2 битов информации. Понятно, что в этом случае 2 битов достаточно.
В задачах на взвешивания ответ небинарен (<, >, =). Однако подход всё равно работает, в чём мы сегодня убедимся.
Итак, во-первых, добавлено новое решение для задачи с 12 монетами на языке теории информации (спасибо проф. мехмата МГУ Николаю Константиновичу Верещагину за прекрасные лекции!). Во-вторых, добавлена новая задача с 13 монетами, которая очень наглядно иллюстрирует, где именно возникает потребность в дополнительном взвешивании.
#ШАД
• Новое решение для 12 монет
• Весы и 13 монет
• Решение для 13 монет
Одна из первых задач здесь после начала учёбы в ШАДе была вот эта классическая задача на взвешивание. Удивительным образом сегодня я её закольцую с учётом нового опыта.
В задачах подобного типа часто встаёт вопрос, а почему нельзя обойтись меньшим количеством операций? Иногда это очевидно, но формальное доказательство очень длинное и скучное. Так вот недавно узнал о технике, которая в некоторых случаях справляется с доказательством в несколько строчек.
Суть очень простая. Допустим, вы загадали целое число от 1 до 4, а ваш друг хочет его узнать. Друг может задавать вам вопросы типа «это число больше / меньше n?» и получать ответы «да / нет». Какое минимальное количество вопросов небходимо задать, чтобы гарантированно узнать число? (Необходимое количество вопросов не обязательно будет достаточным). Заметим, что ответ бинарен, поэтому в лучшем случае исходное множество вариантов при каждом ответе сокращается в 2 раза. Так как дважды два – четыре, то необходимо задать не менее двух вопросов. На языке теории информации говорят, что нужно передать вашему другу не менее 2 битов информации. Понятно, что в этом случае 2 битов достаточно.
В задачах на взвешивания ответ небинарен (<, >, =). Однако подход всё равно работает, в чём мы сегодня убедимся.
Итак, во-первых, добавлено новое решение для задачи с 12 монетами на языке теории информации (спасибо проф. мехмата МГУ Николаю Константиновичу Верещагину за прекрасные лекции!). Во-вторых, добавлена новая задача с 13 монетами, которая очень наглядно иллюстрирует, где именно возникает потребность в дополнительном взвешивании.
#ШАД
• Новое решение для 12 монет
• Весы и 13 монет
• Решение для 13 монет
Telegraph
Весы и 13 монет (#132)
Есть 13 монет, из которых одна фальшивая, и чашечные весы. Монеты выглядят одинаково, но фальшивая отличается по весу от настоящих (но неизвестно, в какую сторону). Докажите, что трёх взвешиваний недостаточно, чтобы гарантированно найти фальшивую монету и…
Априори / Апостериори
В теории вероятности есть такие понятия как вероятность априорная и апострериорная. Первая (a priori) – это вероятность события в исходной постановке, а вторая (a posteriori) принимает в расчёт дополнительную информацию, которая поступает к нам в процессе наблюдения и которая, вообще говоря, может отличаться от исходной.
Для того чтобы узнать, как вероятность меняется при поступлении дополнительной информации, существует типовой инструментарий, который мы демонстрировали здесь. Несмотря на то, что применение указанного метода, приводит к правильному ответу, оно не приводит к пониманию сути. В нашем сегодняшнем решении мы покажем, как можно в две строчки решить задачу. При этом решение наглядно отражает процесс влияния дополнительной информации на распределение вероятностей в данном простейшем случае.
Похожая задачка может встретиться на #интервью в #Facebook (источник).
#тервер
• Монета с двумя орлами
• Решение
В теории вероятности есть такие понятия как вероятность априорная и апострериорная. Первая (a priori) – это вероятность события в исходной постановке, а вторая (a posteriori) принимает в расчёт дополнительную информацию, которая поступает к нам в процессе наблюдения и которая, вообще говоря, может отличаться от исходной.
Для того чтобы узнать, как вероятность меняется при поступлении дополнительной информации, существует типовой инструментарий, который мы демонстрировали здесь. Несмотря на то, что применение указанного метода, приводит к правильному ответу, оно не приводит к пониманию сути. В нашем сегодняшнем решении мы покажем, как можно в две строчки решить задачу. При этом решение наглядно отражает процесс влияния дополнительной информации на распределение вероятностей в данном простейшем случае.
Похожая задачка может встретиться на #интервью в #Facebook (источник).
#тервер
• Монета с двумя орлами
• Решение
Telegraph
Монета с двумя орлами (#133)
Есть 100 монет, из которых ровно одна с двумя орлами, а остальные обычные. Вы не глядя берёте любую и подбрасываете её. Выпадает орёл. Какова вероятность, что перед вами монета с двумя орлами? Сложность: 3/10 Решение Telegram
Про хард-скиллы в ШАДе
Рассказываю про технические навыки, полученные в ШАДе. Естественно, дисклеймер: всё сказанное ниже исключительно моё личное мнение и применимо не для всех.
Пререквизиты
— хотелось бы верить, что у меня достаточно прочная математическая база (мехмат МГУ + кфмн)
— более 4-х лет отраслевого опыта, поэтому было конкретное понимание по приложениям ML в «доменной» области (не металлургии)
— при этом на контрасте я был абсолютный ноль в ML, про нейросети слышал только из новостей, а прогал максимум макросы в Excel. Как сказал бы Греф, я был студентом вчерашнего дня)
Образовательная магистраль
Алгоритмы – Python – ML – Выпуклая оптимизация – Проект
Вокруг этой магистрали были различные обязательные и не очень сайдлайны, которые приходилось закрывать, но сейчас не про них
Алгоритмы и структуры данных.
Я бы назвал это one-man-show Максима Бабенко. Чтобы вы ощутили уровень донесения материала, в программировании и алгоритмах я был около нуля (тот минимум, что нужен для поступления), но понимал на лекции с ходу. А когда приходил домой, не мог вспомнить, почему на лекции всё было понятно. Это курс с практикой на C++. Первое время после курса я решал собесы на плюсах, а не на питоне, чему сейчас искренно удивляюсь. Но основной багаж – это культура кода и паттерны программирования.
Язык Python.
Это самый популярный язык в ML, must-have.
Машинное обучение.
Двухсеместровый курс – ядро моего образовательного трека. Да и в целом, программа Школы так или иначе выстраивается вокруг ML. 70% ценности – в домашках, которые очень ресурсоёмкие, но поэтому супер полезные. Больше всего запомнились следующие:
– Создание нейронки, которая генерирует текстовое описание по картинке. Тестил на личных фото, результат даже не всегда бредовый.
– Конкурс по HFT моделям от Spectral:Technologies с разбором лучших решений
Выпуклая оптимизация.
Не то, чтобы безусловно необходимая вещь, но понимание различных методов оптимизации полезно при тренировке моделей. Начинается всё, конечно, с выпуклых задач. Подача средняя, но порадовала домашка по созданию рекомендательной системы.
Проект,
как место приложения всего вышесказанного. Работа над проектом ведётся в течение второго года обучения (не всеми, а только студентами, которые выбрали прикладной трек). Можно принести свой проект, а можно выбрать из тех, что предлагают преподаватели. Я пришёл со своей идеей с потенциалом развития вне Школы. Опыт достаточно успешный, так как проектная гипотеза подтверждена, и есть смысл продолжать работу. Возможно, расскажу про него в отдельном посте когда-нибудь.
В заключение
Владение навыками создаёт ещё одну возможность – вам легче управлять продуктом / командой, так как вы понимаете возможнoсти моделей / инструментов.
У меня был коллега, который очень любил проводить аналогию на машинах. Буквально любой кейс он перекладывал на язык автолюбителя. Так вот, если вы управляете машиной (продуктом), знание механики под капотом (ML) не обязательно, но даёт выгоду в определённых случаях: обнаружение неисправности, общение в автосервисе на равных, и так далее.
Рассказываю про технические навыки, полученные в ШАДе. Естественно, дисклеймер: всё сказанное ниже исключительно моё личное мнение и применимо не для всех.
Пререквизиты
— хотелось бы верить, что у меня достаточно прочная математическая база (мехмат МГУ + кфмн)
— более 4-х лет отраслевого опыта, поэтому было конкретное понимание по приложениям ML в «доменной» области (не металлургии)
— при этом на контрасте я был абсолютный ноль в ML, про нейросети слышал только из новостей, а прогал максимум макросы в Excel. Как сказал бы Греф, я был студентом вчерашнего дня)
Образовательная магистраль
Алгоритмы – Python – ML – Выпуклая оптимизация – Проект
Вокруг этой магистрали были различные обязательные и не очень сайдлайны, которые приходилось закрывать, но сейчас не про них
Алгоритмы и структуры данных.
Я бы назвал это one-man-show Максима Бабенко. Чтобы вы ощутили уровень донесения материала, в программировании и алгоритмах я был около нуля (тот минимум, что нужен для поступления), но понимал на лекции с ходу. А когда приходил домой, не мог вспомнить, почему на лекции всё было понятно. Это курс с практикой на C++. Первое время после курса я решал собесы на плюсах, а не на питоне, чему сейчас искренно удивляюсь. Но основной багаж – это культура кода и паттерны программирования.
Язык Python.
Это самый популярный язык в ML, must-have.
Машинное обучение.
Двухсеместровый курс – ядро моего образовательного трека. Да и в целом, программа Школы так или иначе выстраивается вокруг ML. 70% ценности – в домашках, которые очень ресурсоёмкие, но поэтому супер полезные. Больше всего запомнились следующие:
– Создание нейронки, которая генерирует текстовое описание по картинке. Тестил на личных фото, результат даже не всегда бредовый.
– Конкурс по HFT моделям от Spectral:Technologies с разбором лучших решений
Выпуклая оптимизация.
Не то, чтобы безусловно необходимая вещь, но понимание различных методов оптимизации полезно при тренировке моделей. Начинается всё, конечно, с выпуклых задач. Подача средняя, но порадовала домашка по созданию рекомендательной системы.
Проект,
как место приложения всего вышесказанного. Работа над проектом ведётся в течение второго года обучения (не всеми, а только студентами, которые выбрали прикладной трек). Можно принести свой проект, а можно выбрать из тех, что предлагают преподаватели. Я пришёл со своей идеей с потенциалом развития вне Школы. Опыт достаточно успешный, так как проектная гипотеза подтверждена, и есть смысл продолжать работу. Возможно, расскажу про него в отдельном посте когда-нибудь.
В заключение
Владение навыками создаёт ещё одну возможность – вам легче управлять продуктом / командой, так как вы понимаете возможнoсти моделей / инструментов.
У меня был коллега, который очень любил проводить аналогию на машинах. Буквально любой кейс он перекладывал на язык автолюбителя. Так вот, если вы управляете машиной (продуктом), знание механики под капотом (ML) не обязательно, но даёт выгоду в определённых случаях: обнаружение неисправности, общение в автосервисе на равных, и так далее.
Сюрпост
Согласно учению древних мир состоит из четырёх стихий: земля, вода, воздух и огонь. В Китае же к числу четыре относятся с большим страхом, ведь оно созвучно со словом смерть. По представлениям древних египтян мир покоится на четырёх столбах. А четыре стороны света на четырех морях положены. Было у Макея четыре лакея, а ныне Макей сам лакей. Без четырех углов изба не рубится. Четыре кола вбито да небом покрыто. А мы сегодня пойдём…
#олимпиады
• На все четыре стороны
• Решение
Согласно учению древних мир состоит из четырёх стихий: земля, вода, воздух и огонь. В Китае же к числу четыре относятся с большим страхом, ведь оно созвучно со словом смерть. По представлениям древних египтян мир покоится на четырёх столбах. А четыре стороны света на четырех морях положены. Было у Макея четыре лакея, а ныне Макей сам лакей. Без четырех углов изба не рубится. Четыре кола вбито да небом покрыто. А мы сегодня пойдём…
#олимпиады
• На все четыре стороны
• Решение
Telegraph
На все четыре стороны (#134)
Клетки квадрата 50 х 50 раскрашены в двенадцать цветов. Докажите, что существует клетка, с четырёх сторон от которой (то есть сверху, снизу, слева и справа) имеются клетки одного с ней цвета (не обязательно соседние с этой клеткой, а именно: сверху в том…
Отраслевая адаптация
Исходная версия задачи формулируется для верблюдов и бананов. Суть в том, что верблюд может в качестве источника энергии использовать полезный груз, которые ему надо перенести. Понятно, чем больше расстояние, тем меньше он сможет доставить. Единственная (!) современная промышленная аналогия данному феномену – перевозка сжиженного природного газа (СПГ). Я не знаю другого энергоносителя, который использовался бы подобным образом. Нет ведь бензовоза, который бы сливал горючее из цистерны в топливный бак. Есть перспектива у морских перевозок аммиака и водорода, но пока всё ограничивается единичными экспериментами.
Оригинал – достаточно распространённая задача на #интервью, поэтому даже не буду перечислять компании. А в авторских обвесах брейнтизер подойдёт для нефтегазовой сферы.
У меня ещё одна задача припасена про перевалку СПГ, так что скоро вы опять пострадаете от моей профдеформации.
• Перевозка СПГ
• Решение
Исходная версия задачи формулируется для верблюдов и бананов. Суть в том, что верблюд может в качестве источника энергии использовать полезный груз, которые ему надо перенести. Понятно, чем больше расстояние, тем меньше он сможет доставить. Единственная (!) современная промышленная аналогия данному феномену – перевозка сжиженного природного газа (СПГ). Я не знаю другого энергоносителя, который использовался бы подобным образом. Нет ведь бензовоза, который бы сливал горючее из цистерны в топливный бак. Есть перспектива у морских перевозок аммиака и водорода, но пока всё ограничивается единичными экспериментами.
Оригинал – достаточно распространённая задача на #интервью, поэтому даже не буду перечислять компании. А в авторских обвесах брейнтизер подойдёт для нефтегазовой сферы.
У меня ещё одна задача припасена про перевалку СПГ, так что скоро вы опять пострадаете от моей профдеформации.
• Перевозка СПГ
• Решение
Telegraph
Перевозка СПГ (#135)
Необходимо перевезти сжиженный природный газ (СПГ) от завода до терминала, находящимися на расстоянии 1 000 миль друг от друга. Изначально в заводских хранилищах находится 3 000 тонн СПГ. В распоряжении у перевозчика есть всего одно судно-газовоз вместимостью…
С Новым годом 2024
Лучше всего, конечно, пять звёздочек!
Фильм «Карнавальная ночь»
Дорогие друзья! Внезапно оказалось, что это уже 7-й по счёту Новый год, который мы встречаем вместе с вами. Мы, два математика и два иллюстратора, делимся с вами красивыми задачами, всегда авторскими решениями и в классном оформлении. Вся эта кипучая деятельность держится в основном на одном – вашем интересе. Поэтому большое СПАСИБО за то, что вы с нами.
Пусть новый год принесёт вам очень много радости и счастья! А чтобы дополнить праздничный антураж – с нас задача!
• Разноцветное пространство
• Решение
Лучше всего, конечно, пять звёздочек!
Фильм «Карнавальная ночь»
Дорогие друзья! Внезапно оказалось, что это уже 7-й по счёту Новый год, который мы встречаем вместе с вами. Мы, два математика и два иллюстратора, делимся с вами красивыми задачами, всегда авторскими решениями и в классном оформлении. Вся эта кипучая деятельность держится в основном на одном – вашем интересе. Поэтому большое СПАСИБО за то, что вы с нами.
Пусть новый год принесёт вам очень много радости и счастья! А чтобы дополнить праздничный антураж – с нас задача!
• Разноцветное пространство
• Решение
Telegraph
Разноцветное пространство (#136)
Каждая точка пространства окрашена в один из пяти цветов, причём в каждый цвет окрашена по крайней мере одна точка. Докажите, что найдётся плоскость, все точки которой окрашены не менее чем в четыре цвета. Сложность: 4/10 Решение Telegram
Целое и дробное
Целой частью числа x называется максимальное целое число, не превосходящее x. Обычно целую часть числа обозначают квадратными скобками, например, [-√2] = -2. Дробной частью числа x называется число x - [x], то есть то, что остаётся от числа x после вычитания из него целой части. Обозначается фигурными скобками {x} = x - [x].
Если длина стороны квадрата равна x, то длина диагонали равна x√2. Если длина стороны куба равна x, то длина диагонали равна x√3. Если же длина стороны d-мерного куба равна x, то длина его диагонали равна x√d. Такова увертюра к сегодняшней задаче.
• Про дробную часть диагонали
• Решение
Целой частью числа x называется максимальное целое число, не превосходящее x. Обычно целую часть числа обозначают квадратными скобками, например, [-√2] = -2. Дробной частью числа x называется число x - [x], то есть то, что остаётся от числа x после вычитания из него целой части. Обозначается фигурными скобками {x} = x - [x].
Если длина стороны квадрата равна x, то длина диагонали равна x√2. Если длина стороны куба равна x, то длина диагонали равна x√3. Если же длина стороны d-мерного куба равна x, то длина его диагонали равна x√d. Такова увертюра к сегодняшней задаче.
• Про дробную часть диагонали
• Решение
Telegraph
Про дробную часть диагонали (#137)
Доказать, что при всех натуральных n выполняется неравенство Сложность: 4/10 Решение Telegram
Родственные задачи
Пополняем коллекцию логистических задач. Вообще есть гипотеза, что сегодняшняя задача и задачи из наших предыдущих постов:
– Королева бензоколонки (про кольцевую автодорогу)
– 50 байкеров (про максимальное расстояние на фиксированном количестве топлива)
– Перевозка СПГ (про максимальное количество доставленного груза)
эквивалентны. А именно, что есть некая общая постановка, к которой можно подогнать все задачи этого цикла. Было бы интересно в этом разобраться.
• Кругосветка
• Решение
Пополняем коллекцию логистических задач. Вообще есть гипотеза, что сегодняшняя задача и задачи из наших предыдущих постов:
– Королева бензоколонки (про кольцевую автодорогу)
– 50 байкеров (про максимальное расстояние на фиксированном количестве топлива)
– Перевозка СПГ (про максимальное количество доставленного груза)
эквивалентны. А именно, что есть некая общая постановка, к которой можно подогнать все задачи этого цикла. Было бы интересно в этом разобраться.
• Кругосветка
• Решение
Telegraph
Кругосветка (#138)
На острове есть аэропорт, в котором находится неограниченное количество одинаковых самолетов. При полной заправке самолёт может пролететь ровно половину пути вокруг света по большому кругу. Самолёты имеют возможность идеальной дозаправки в полёте без потери…
Игры на клетчатой бумаге
Клетка – неисчерпаемый источник задач, игр и головоломок. В дополнение к раз и два представляем ещё одну игру с симпатичным решением. Примечательно, что во всех упомянутых сейчас задачах применяются совершенно разные стратегии выигрыша.
#олимпиады #игра
• Игра в квадрат
• Решение
Клетка – неисчерпаемый источник задач, игр и головоломок. В дополнение к раз и два представляем ещё одну игру с симпатичным решением. Примечательно, что во всех упомянутых сейчас задачах применяются совершенно разные стратегии выигрыша.
#олимпиады #игра
• Игра в квадрат
• Решение
Telegraph
Игра в квадрат (#139)
На клетчатой доске 4х4 играют двое. Ходят по очереди, и каждый играющий своим ходом закрашивает одну клетку. Проигрывает тот, после чьего хода образуется квадрат 2х2, состоящий из закрашенных клеток. Кто выигрывает при правильной игре? Сложность: 3/10 Решение…
Иногда сложно придумать решение задачи. А насколько сложно придумать саму задачу? Мы в Матрёшке осилили этот вызов несколько раз. Зафиксировали своё достижение здесь и здесь.
На неделе через общего коллегу познакомился с Михаилом Евдокимовым – задачным композитором. Михаил сочиняет задачи для школьных математических олимпиад разного уровня: Московская Олимпиада Школьников, Турнир Городов, Матпраздник, Всерос.
Так как Михаил работал в различных компаниях, то у него собралась небольшая коллекция задач с собеседований, которые он начал публиковать на канале @kvantland. Далее следует репост.
На неделе через общего коллегу познакомился с Михаилом Евдокимовым – задачным композитором. Михаил сочиняет задачи для школьных математических олимпиад разного уровня: Московская Олимпиада Школьников, Турнир Городов, Матпраздник, Всерос.
Так как Михаил работал в различных компаниях, то у него собралась небольшая коллекция задач с собеседований, которые он начал публиковать на канале @kvantland. Далее следует репост.
Forwarded from Квантландия | Интересные задачи и не только
Вы думаете, что на собеседованиях при приёме на работу в крупную компанию задают только вопросы, требующие специальных знаний? Это не всегда так). Вот задачка для младших классов, с которой справились далеко не все кандидаты:
Три охотника сварили кашу. Первый дал две кружки крупы, второй — одну, третий — ни одной, но он расплатился семью патронами. Как должны поделить патроны первые два охотника, если все ели поровну?
Три охотника сварили кашу. Первый дал две кружки крупы, второй — одну, третий — ни одной, но он расплатился семью патронами. Как должны поделить патроны первые два охотника, если все ели поровну?
Шахматные задачи
Кроме математики мы также любим шахматы. Сегодня открывается турнир претендентов (и претенденток), который пройдёт в Торонто с 3 по 23 апреля. Победитель турнира сыграет матч за титул с действующим чемпионом мира по шахматам Дин Лижэнем. По этому поводу предлагаем вам решить авторскую задачу. Попутно также отметим, что шахматные задачи можно разделить на два типа:
– собственно шахматные, использующие полный набор правил и тренирующие навыки игры (например, как сегодняшняя)
– математические / логические, использующие некоторую шахматную механику, но решения которых лежат вне плоскости игры (например, как эта)
#шахматы #авторская
Условие (№140)
Какое максимальное количество ферзей можно получить на шахматной доске, играя по правилам? Какое максимальное количество фигур может присутствовать на доске в этот момент?
• Решение
Кроме математики мы также любим шахматы. Сегодня открывается турнир претендентов (и претенденток), который пройдёт в Торонто с 3 по 23 апреля. Победитель турнира сыграет матч за титул с действующим чемпионом мира по шахматам Дин Лижэнем. По этому поводу предлагаем вам решить авторскую задачу. Попутно также отметим, что шахматные задачи можно разделить на два типа:
– собственно шахматные, использующие полный набор правил и тренирующие навыки игры (например, как сегодняшняя)
– математические / логические, использующие некоторую шахматную механику, но решения которых лежат вне плоскости игры (например, как эта)
#шахматы #авторская
Условие (№140)
Какое максимальное количество ферзей можно получить на шахматной доске, играя по правилам? Какое максимальное количество фигур может присутствовать на доске в этот момент?
• Решение
Задача Бернулли-Эйлера о перепутанных письмах
Классическая задача Бернулли-Эйлера формулируется следующим образом.
Формулировка (№141)
Некто написал шесть писем шести различным людям и заготовил шесть конвертов с их адресами. Сколькими способами можно вложить письма в конверты, чтобы ни одно письмо не попало тому лицу, которому оно адресовано?
В качестве реверанса к предыдущему посту проинтерпретируем эту задачу в шахматных терминах: ладья на i-й вертикали и j-й горизонтали будет соответствовать i-му письму, упакованному в j-й конверт. С учётом этого получаем
Эквивалентную формулировку
Сколькими способами на доске 6х6 можно расставить 6 ладей так, чтобы они не били друг друга и не стояли на главной диагонали?
Альтернативная формулировка создаёт новый контекст с сопуствующим инструментарием. Поэтому возможно кому-то будет удобнее решать эту задачу в шахматных терминах.
#олимпиады #классическаязадача
• Решение
Классическая задача Бернулли-Эйлера формулируется следующим образом.
Формулировка (№141)
Некто написал шесть писем шести различным людям и заготовил шесть конвертов с их адресами. Сколькими способами можно вложить письма в конверты, чтобы ни одно письмо не попало тому лицу, которому оно адресовано?
В качестве реверанса к предыдущему посту проинтерпретируем эту задачу в шахматных терминах: ладья на i-й вертикали и j-й горизонтали будет соответствовать i-му письму, упакованному в j-й конверт. С учётом этого получаем
Эквивалентную формулировку
Сколькими способами на доске 6х6 можно расставить 6 ладей так, чтобы они не били друг друга и не стояли на главной диагонали?
Альтернативная формулировка создаёт новый контекст с сопуствующим инструментарием. Поэтому возможно кому-то будет удобнее решать эту задачу в шахматных терминах.
#олимпиады #классическаязадача
• Решение
С новым учебным годом
В прошлом году я преподавал в RSM 5-му и 7-му классам олимпиадную математику. Или как у них говорят, competition mathematics. Очень был рад, что начало сезона у олимпиадников идёт со сдвигом в пару недель относительно стандартной программы. Ну а теперь уже привычка.
Итак, возвращаемся с летних каникул к любимой теме соавтора Матрёшки – клетке. Очевидная шахматная аналогия не всегда помогает в решении задач по примеру сегодняшней.
А если вам вдруг захотелось поупражняться в задачах на клетчатой бумаге, то вот наша коллекция:
– Клеточный отбор (#30)
– Столбец квадратов (#54)
– Баги (#56)
– Дно коробки (#62)
– Робот на шахматной доске (#71)
и другие…
• Прямоугольники на доске 10х10
• Решение
В прошлом году я преподавал в RSM 5-му и 7-му классам олимпиадную математику. Или как у них говорят, competition mathematics. Очень был рад, что начало сезона у олимпиадников идёт со сдвигом в пару недель относительно стандартной программы. Ну а теперь уже привычка.
Итак, возвращаемся с летних каникул к любимой теме соавтора Матрёшки – клетке. Очевидная шахматная аналогия не всегда помогает в решении задач по примеру сегодняшней.
А если вам вдруг захотелось поупражняться в задачах на клетчатой бумаге, то вот наша коллекция:
– Клеточный отбор (#30)
– Столбец квадратов (#54)
– Баги (#56)
– Дно коробки (#62)
– Робот на шахматной доске (#71)
и другие…
• Прямоугольники на доске 10х10
• Решение
Teletype
Прямоугольники на доске 10х10 (#142)
Можно ли доску размером 10х10 покрыть без наложения прямоугольниками 4х1
Лог(ист)ические задачи
Когда-то я работал в компании #Новатэк, где мы с Коллегой проводили #интервью кандидатов к нам в управление. Среди прочих вопросов на собеседовании был единственный брейнтизер авторства моего Коллеги, который я считаю замечательным по нескольким причинам:
– моделирует реальные рабочие задачи
– простой
– легко ошибиться, если поспешить с ответом
В итоге на данную позицию мы провели очные встречи с 7 претендентами, среди которых только один смог решить. Но я убеждён, что все смогли бы дать правильный ответ, если бы спокойно обдумали задачу.
• Перевалка
• Решение
Когда-то я работал в компании #Новатэк, где мы с Коллегой проводили #интервью кандидатов к нам в управление. Среди прочих вопросов на собеседовании был единственный брейнтизер авторства моего Коллеги, который я считаю замечательным по нескольким причинам:
– моделирует реальные рабочие задачи
– простой
– легко ошибиться, если поспешить с ответом
В итоге на данную позицию мы провели очные встречи с 7 претендентами, среди которых только один смог решить. Но я убеждён, что все смогли бы дать правильный ответ, если бы спокойно обдумали задачу.
• Перевалка
• Решение
Teletype
Перевалка (#143)
Представьте себе транспортную систему, устроенную следующим образом. Есть завод в Арктике, чью продукцию могут забрать только...
Классические задачи по теории вероятностей
– Какова вероятность встретить на улице динозавра?
– 50 на 50, либо встретишь, либо нет.
Очень люблю задачи, в которых первоначальная интуиция оказывается ошибочной. Сегодня предлагаем поупражняться в теории вероятностей, решая классическую олимпиадную задачу (по ощущениям, начиная с 9-го класса). Авторство мне неизветсно, но самое раннее упоминание, которое удалось найти относится к 2001-му году на сайте родного мехмата. Поделитесь в комментариях, если вдруг владеете более ранним источником.
В этот раз мы к вам с ещё одним анонсом. В нашем канале перемешаны два ключевых направления «собеседовательное» и олимпиадное (фильтровать можно по хэштэгам #интервью и #олимпиады соответственно). Ответственный за олимпиадное направление делится своими ассоциациями и мыслями по задачам в разделе Дивертисмент.
#тервер #классическаязадача
• Сумасшедшая старушка
• Дивертисмент
• Решение
– Какова вероятность встретить на улице динозавра?
– 50 на 50, либо встретишь, либо нет.
Очень люблю задачи, в которых первоначальная интуиция оказывается ошибочной. Сегодня предлагаем поупражняться в теории вероятностей, решая классическую олимпиадную задачу (по ощущениям, начиная с 9-го класса). Авторство мне неизветсно, но самое раннее упоминание, которое удалось найти относится к 2001-му году на сайте родного мехмата. Поделитесь в комментариях, если вдруг владеете более ранним источником.
В этот раз мы к вам с ещё одним анонсом. В нашем канале перемешаны два ключевых направления «собеседовательное» и олимпиадное (фильтровать можно по хэштэгам #интервью и #олимпиады соответственно). Ответственный за олимпиадное направление делится своими ассоциациями и мыслями по задачам в разделе Дивертисмент.
#тервер #классическаязадача
• Сумасшедшая старушка
• Дивертисмент
• Решение
Teletype
Сумасшедшая старушка (#144)
При посадке в самолёт выстроилась очередь из n пассажиров, у каждого из которых имеется билет на одно из n мест. Первой в очереди стоит...
С наступающим 2025
Счастье для всех, даром, и пусть никто не уйдет обиженный!
Стругацкие
Дорогие! Пусть новый год будет для вас счастливым. Всем нам – ❤️ и 🕊
Традиционное, но ничуть не формальное, СПАСИБО за то, что вы с нами!
Мы знаем, что среди наших подписчиков есть люди, которые накануне праздников непременно захотят порешать задачки. Понимая нашу ответственность, публикуем.
Пара слов про саму задачу. Наверное, не будет большим спойлером сказать, что в задачах на поиск оптимума, как правило, есть две части:
1/ привести пример решения
2/ доказать, что оно оптимально
Первая часть обычно очень весёлая. Вторая же – наоборот. Поэтому часто её пропускают за «очевидностью». Несмотря на то, что сегодняшняя задачка достаточно известная, например, вот она на бразильской олимпиаде 2005 года, мы не нашли строгого доказательства оптимальности. Среди того, что получилось найти, одни переборы. Нам удалось эту лакуну закрыть весьма эстетично на языкетеории графов .
#олимпиады
• Фонарик и 8 батареек
• Решение
Счастье для всех, даром, и пусть никто не уйдет обиженный!
Стругацкие
Дорогие! Пусть новый год будет для вас счастливым. Всем нам – ❤️ и 🕊
Традиционное, но ничуть не формальное, СПАСИБО за то, что вы с нами!
Мы знаем, что среди наших подписчиков есть люди, которые накануне праздников непременно захотят порешать задачки. Понимая нашу ответственность, публикуем.
Пара слов про саму задачу. Наверное, не будет большим спойлером сказать, что в задачах на поиск оптимума, как правило, есть две части:
1/ привести пример решения
2/ доказать, что оно оптимально
Первая часть обычно очень весёлая. Вторая же – наоборот. Поэтому часто её пропускают за «очевидностью». Несмотря на то, что сегодняшняя задачка достаточно известная, например, вот она на бразильской олимпиаде 2005 года, мы не нашли строгого доказательства оптимальности. Среди того, что получилось найти, одни переборы. Нам удалось эту лакуну закрыть весьма эстетично на языке
#олимпиады
• Фонарик и 8 батареек
• Решение
Teletype
Фонарик и 8 батареек (#145)
У вас есть 8 батареек, 4 из которых разряжены, остальные заряжены. Фонарик вмещает 2 батарейки, причём для работы требуется, чтобы обе...
Понравился мем:
Новый год снова не будет простым
Немного нумерологии вам в ленту:
2025 = (20 + 25)² =
(1 + 2 + … + 9)² =
1³ + 2³ + … + 9³
Последнее тождество приписывается Никомаху из г. Геразы, греческому математику, жившему во 2-м веке. Это имя я узнал на днях, а в 4-м веке «книга Никомаха была столь же классическою для арифметики, как Евклид для геометрии», как пишет А.В. Васильев в своём историческом очерке про целые числа.
Новый год снова не будет простым
Немного нумерологии вам в ленту:
2025 = (20 + 25)² =
(1 + 2 + … + 9)² =
1³ + 2³ + … + 9³
Последнее тождество приписывается Никомаху из г. Геразы, греческому математику, жившему во 2-м веке. Это имя я узнал на днях, а в 4-м веке «книга Никомаха была столь же классическою для арифметики, как Евклид для геометрии», как пишет А.В. Васильев в своём историческом очерке про целые числа.
Страна Оз возвращается
Итак, заключительная часть увлекательной франшизы сегодня на ваших экранах. Если вы пропустили, то рекомендую начать с 1-й серии, а именно с этого поста шестилетней давности. 2-я часть вышла почти два года спустя здесь. Бессменный режиссёрский и актёрский состав.
Хотелось бы здесь оставить некоторый крючок, cliffhanger, с тем чтобы вы непременно ждали продолжения. Возможно ли такое в математике?
#олимпиады #графы
• Солнечные и лунные города страны Оз (#146)
• Дивертисмент
• Решение
Итак, заключительная часть увлекательной франшизы сегодня на ваших экранах. Если вы пропустили, то рекомендую начать с 1-й серии, а именно с этого поста шестилетней давности. 2-я часть вышла почти два года спустя здесь. Бессменный режиссёрский и актёрский состав.
Хотелось бы здесь оставить некоторый крючок, cliffhanger, с тем чтобы вы непременно ждали продолжения. Возможно ли такое в математике?
#олимпиады #графы
• Солнечные и лунные города страны Оз (#146)
• Дивертисмент
• Решение
Teletype
Солнечные и Лунные города страны Оз (#146)
В стране Оз есть три вида дорог: чёрные, белые и из жёлтого кирпича. Дороги в стране Оз построены таким образом, что они...
Квантландия возвращается
Рассказываем про бесплатный онлайн-турнир наших друзей из @kvantland. Всё просто:
1/ переходим на сайт турнира
2/ выбираем трек: для 4-6 класса или для 7-9 класса
3/ регистрируемся и решаем задачки
Решать можно в любое удобное время в феврале-марте. Взрослые тоже могут участвовать по фану и вне зачёта:)
Рассказываем про бесплатный онлайн-турнир наших друзей из @kvantland. Всё просто:
1/ переходим на сайт турнира
2/ выбираем трек: для 4-6 класса или для 7-9 класса
3/ регистрируемся и решаем задачки
Решать можно в любое удобное время в феврале-марте. Взрослые тоже могут участвовать по фану и вне зачёта:)
