С наступающим Новым годом!
Вы ещё с нами? 🙂
Друзья, спасибо за вашу поддержку в этом году! Последнее время вести канал непросто, но именно ваш интерес мотивирует продолжать.
С другой стороны, мне нравится, что это очень гибкая история, которая подстраивается под время. У меня нет цели публиковаться во что бы то ни стало, так как главное условие качества – всё должно быть в кайф!
Поэтому, друзья, всем отличных праздников! И, конечно, дз на каникулы прилагается.
PS Думаю, мы вас ещё потревожим в этом году с традиционным опросом, так как нам очень не хватает обратной связи...
#олимпиады #графы
Семейный альбом (#103)
Вы ещё с нами? 🙂
Друзья, спасибо за вашу поддержку в этом году! Последнее время вести канал непросто, но именно ваш интерес мотивирует продолжать.
С другой стороны, мне нравится, что это очень гибкая история, которая подстраивается под время. У меня нет цели публиковаться во что бы то ни стало, так как главное условие качества – всё должно быть в кайф!
Поэтому, друзья, всем отличных праздников! И, конечно, дз на каникулы прилагается.
PS Думаю, мы вас ещё потревожим в этом году с традиционным опросом, так как нам очень не хватает обратной связи...
#олимпиады #графы
Семейный альбом (#103)
Medium
Семейный альбом (#103)
В семейном альбоме есть десять фотографий. На каждой из них изображены три человека: в центре стоит мужчина, слева от мужчины — его сын, а…
🎄
Друзья, ещё раз с наступающими праздниками! По традиции – опрос. Напомню, что если у вас есть дополнительные пожелания, замечания, комментарии – welcome в личку.
Друзья, ещё раз с наступающими праздниками! По традиции – опрос. Напомню, что если у вас есть дополнительные пожелания, замечания, комментарии – welcome в личку.
С какой периодичностью вы бы хотели видеть новые посты?
Final Results
28%
чаще 1 раза в неделю
42%
1 раз в неделю
12%
2-3 раза в месяц
5%
1 раз в месяц
1%
реже 1 раза в месяц
12%
без разницы
Разминка
Во-первых, спасибо всем, кто проголосовал в новогоднем опросе. Очень приятно видеть, что есть интерес к нашим материалам на еженедельной основе. Мотивирует продолжать делится с вами только самыми интересными задачами, выражаясь словами поэта:
Изводишь единого слова ради
Тысячи тонн словесной руды
Я считаю, что год нужно начинать плавно, поэтому сегодня предлагается суперлёгкая задача. Без подвоха. Но в то же время – не без изюминки (на мой вкус). Её я услышал случайно, когда на праздниках просматривал интервью Солодникова (ещёнепознер) с Зиминым (вымпелком). Кстати, всем рекомендую посмотреть. В нём очень интересная подводка к книжке Бронштейна «Солнечное вещество». Ну и, конечно, великолепно отрекомендован (неумышленно) детский задачник Арнольда. Из него и взят сегодняшний вопрос...
В силу суперлёгкости – публикуем без решения. Но если хочется свериться – смотрите видео по ссылке выше (время выставлено).
Кирпич (#104)
Во-первых, спасибо всем, кто проголосовал в новогоднем опросе. Очень приятно видеть, что есть интерес к нашим материалам на еженедельной основе. Мотивирует продолжать делится с вами только самыми интересными задачами, выражаясь словами поэта:
Изводишь единого слова ради
Тысячи тонн словесной руды
Я считаю, что год нужно начинать плавно, поэтому сегодня предлагается суперлёгкая задача. Без подвоха. Но в то же время – не без изюминки (на мой вкус). Её я услышал случайно, когда на праздниках просматривал интервью Солодникова (ещёнепознер) с Зиминым (вымпелком). Кстати, всем рекомендую посмотреть. В нём очень интересная подводка к книжке Бронштейна «Солнечное вещество». Ну и, конечно, великолепно отрекомендован (неумышленно) детский задачник Арнольда. Из него и взят сегодняшний вопрос...
В силу суперлёгкости – публикуем без решения. Но если хочется свериться – смотрите видео по ссылке выше (время выставлено).
Кирпич (#104)
Telegraph
Кирпич (#104)
Кирпич весит 1 килограмм и полкирпича. Сколько весит кирпич? Сложность: 1/10 Источник: Арнольд В.И. – Задачи для детей от 5 до 15 лет (2004)
Задача с красивым ответом
Сегодняшняя задача появлялась на собеседованиях в разных компаниях (например, #Palantir, инфо с Glassdoor) примерно с 2010 года. Недавно её предложили моему другу на #интервью в #Сбербанк. Хотя больше она подходит для Почты России.
А ещё в этой задаче красивый ответ. Я бы даже сказал, гармоничный.
50 байкеров (#105)
Сегодняшняя задача появлялась на собеседованиях в разных компаниях (например, #Palantir, инфо с Glassdoor) примерно с 2010 года. Недавно её предложили моему другу на #интервью в #Сбербанк. Хотя больше она подходит для Почты России.
А ещё в этой задаче красивый ответ. Я бы даже сказал, гармоничный.
50 байкеров (#105)
Medium
50 байкеров (#105)
Колонна из 50 мотоциклов готовится к мотошествию. Топливный бак каждого мотоцикла рассчитан на 100 км. На пути не будет заправок, но…
Кони Гугла
Говорят, что эта задачка стала известной, так как её справшивают на #интервью в #Google. На мой взгляд, очень остроумный пример задачи нахождения k-й порядковой статистики.
Кстати, в #Yandex тоже есть кони.
А есть ли в ваших компаниях ̶к̶о̶н̶и̶ любимые задачи, которые почти всегда предлагаются соискателям? Добро пожаловать в личку.
Кони (#106)
Говорят, что эта задачка стала известной, так как её справшивают на #интервью в #Google. На мой взгляд, очень остроумный пример задачи нахождения k-й порядковой статистики.
Кстати, в #Yandex тоже есть кони.
А есть ли в ваших компаниях ̶к̶о̶н̶и̶ любимые задачи, которые почти всегда предлагаются соискателям? Добро пожаловать в личку.
Кони (#106)
Medium
Кони (#106)
Есть 25 лошадей. В одной гонке может участвовать до 5 лошадей. Секундомера нет. Какое минимальное количество забегов нужно провести, чтобы…
Задача о дилижансе. Облегчённая версия
Лёгкое прикосновение к разделу теории графов о кратчайших путях.
Задача кратчайшего пути – задача поиска пути между двумя вершинами на графе, минимизирующего сумму весов рёбер, его составляющих.
Сложность решения, конечно, зависит от того, что нам известно про граф. В общем случае для решения пользуются специальными алгоритмами. В нашей задаче есть изначальные сведения о графе, и требуется только доказать оценку сверху на длину кратчайшего пути.
#олимпиады #графы
На перекладных (#107)
Лёгкое прикосновение к разделу теории графов о кратчайших путях.
Задача кратчайшего пути – задача поиска пути между двумя вершинами на графе, минимизирующего сумму весов рёбер, его составляющих.
Сложность решения, конечно, зависит от того, что нам известно про граф. В общем случае для решения пользуются специальными алгоритмами. В нашей задаче есть изначальные сведения о графе, и требуется только доказать оценку сверху на длину кратчайшего пути.
#олимпиады #графы
На перекладных (#107)
Medium
На перекладных (#107)
В стране 2020 городов, и из каждого выходит не менее 100 дорог. Известно, что из любого города можно проехать по дорогам в любой другой…
Задача брадобрея
Это бородатая задача, но я хочу рассказать о ней здесь по двум причинам.
Во-первых, мне её предложили на #интервью в компании #Совкомфлот, а значит могут предложить и вам. В нашей компании это стало устойчивой фразой: прежде чем браться за любую задачу, проверьте, не решаете ли вы задачу брадобрея.
Во-вторых, это антиномия, то есть рассуждение, которое содержит внутреннее противоречие. Например, может ли всемогущий бог создать камень, который не сможет поднять? Всё это вариации парадокса Рассела – рассуждения, показавшего противоречивость наивной теории множеств.
Ранее мы уже говорили про классификацию феноменов, которые часто объединяют под словом #парадокс. Там же рассмотрена задача о днях рождений – парадокс другого типа.
Присылайте ваши любимые парадоксы. Самый интересный – в ленту.
Брадобрей (#108)
Это бородатая задача, но я хочу рассказать о ней здесь по двум причинам.
Во-первых, мне её предложили на #интервью в компании #Совкомфлот, а значит могут предложить и вам. В нашей компании это стало устойчивой фразой: прежде чем браться за любую задачу, проверьте, не решаете ли вы задачу брадобрея.
Во-вторых, это антиномия, то есть рассуждение, которое содержит внутреннее противоречие. Например, может ли всемогущий бог создать камень, который не сможет поднять? Всё это вариации парадокса Рассела – рассуждения, показавшего противоречивость наивной теории множеств.
Ранее мы уже говорили про классификацию феноменов, которые часто объединяют под словом #парадокс. Там же рассмотрена задача о днях рождений – парадокс другого типа.
Присылайте ваши любимые парадоксы. Самый интересный – в ленту.
Брадобрей (#108)
Medium
Брадобрей (#108)
В деревне живёт единственный брадобрей, который бреет всех жителей деревни, которые не бреются сами, и только их.
👍1
«Последняя задача из матрешки напомнила», —
ТОНКИЙ ТРОЛЛИНГ от подписчика.
ТОНКИЙ ТРОЛЛИНГ от подписчика.
YouTube
Клиника. Загадка про монеты(Лучший момент)
Мы ВКонтакте - http://vk.com/coolof
ПОДПИШИСЬ на нас и смотри Самые яркие эпизоды из мультфильмов, кино и сериалов!
ПОДПИШИСЬ на нас и смотри Самые яркие эпизоды из мультфильмов, кино и сериалов!
Международная олимпиада
Значит так, пора выходить из анабиоза. Для такого случая есть бодрящая задачка с Международной #олимпиады. Это первая задача с соревнований такого уровня в Матрёшке, поэтому если вы ни разу не решали задач с «международки», попробуйте, специальных знаний не требуется. На мой взгляд, интересная возможность оценить сложность материала, с которым работают ребята.
Международная математическая олимпиада (MMO) – это Чемпионат мира по математике среди школьников старших классов, проводящийся каждый год в одной из стран. Первая MMO прошла в 1959 году в Румынии с участием семи стран. В последние годы в ММО участвуют более 100 стран с 5 континентов.
Я на международные этапы не отбирался, но если у вас есть такой опыт – отмечайтесь 👨🎓 внизу и делитесь впечатлениями в личку!
Чехарда (#109)
Значит так, пора выходить из анабиоза. Для такого случая есть бодрящая задачка с Международной #олимпиады. Это первая задача с соревнований такого уровня в Матрёшке, поэтому если вы ни разу не решали задач с «международки», попробуйте, специальных знаний не требуется. На мой взгляд, интересная возможность оценить сложность материала, с которым работают ребята.
Международная математическая олимпиада (MMO) – это Чемпионат мира по математике среди школьников старших классов, проводящийся каждый год в одной из стран. Первая MMO прошла в 1959 году в Румынии с участием семи стран. В последние годы в ММО участвуют более 100 стран с 5 континентов.
Я на международные этапы не отбирался, но если у вас есть такой опыт – отмечайтесь 👨🎓 внизу и делитесь впечатлениями в личку!
Чехарда (#109)
Medium
Чехарда (#109)
На бесконечной шахматной доске происходит следующая игра. В начале n² фишек занимают квадратное поле n x n, по одной фишке в каждой клетке…
Авторские задачи
В начале «Снежной королевы» злые тролли смастерили странное зеркало, которое всё искажало. Набаловавшись на земле, они решили поглумиться и над небом. Чем выше тролли поднимались, тем сильнее зеркало кривлялось, и в какой-то момент оно выскользнуло у них из рук и разбилось на мелкие осколки. В зависимости от того, куда попадал осколок, он начинал проявлять себя по-разному. Дальше – больше, но интереснее Ганса Христиана Андерсена нам всё равно не рассказать, поэтому перечитайте сказку сами – не пожалеете!
Для нас же важно, что если абстрагироваться и принять зеркало за плоскость, осколки – за треугольники, квадраты или шестиугольники, то мы получим головоломку, которая имеет неожиданную связь с прошлым постом. На Международной олимпиаде российская сборная выступает под руководством Назара Хангельдыевича Агаханова, выпускника мехмата МГУ, ныне доцента МФТИ. Он и придумал сегодняшнюю задачу, которая предлагалась уже на Всеросе. Мы её лишь слегка дополнили.
А вообще авторов прекрасных задач великое множество. Хорошая коллекция собрана здесь.
#олимпиады
Правильные клетки (#110)
В начале «Снежной королевы» злые тролли смастерили странное зеркало, которое всё искажало. Набаловавшись на земле, они решили поглумиться и над небом. Чем выше тролли поднимались, тем сильнее зеркало кривлялось, и в какой-то момент оно выскользнуло у них из рук и разбилось на мелкие осколки. В зависимости от того, куда попадал осколок, он начинал проявлять себя по-разному. Дальше – больше, но интереснее Ганса Христиана Андерсена нам всё равно не рассказать, поэтому перечитайте сказку сами – не пожалеете!
Для нас же важно, что если абстрагироваться и принять зеркало за плоскость, осколки – за треугольники, квадраты или шестиугольники, то мы получим головоломку, которая имеет неожиданную связь с прошлым постом. На Международной олимпиаде российская сборная выступает под руководством Назара Хангельдыевича Агаханова, выпускника мехмата МГУ, ныне доцента МФТИ. Он и придумал сегодняшнюю задачу, которая предлагалась уже на Всеросе. Мы её лишь слегка дополнили.
А вообще авторов прекрасных задач великое множество. Хорошая коллекция собрана здесь.
#олимпиады
Правильные клетки (#110)
Medium
Правильные клетки (#110)
В каждую клетку бесконечной клетчатой плоскости записано одно из чисел 1, 2, 3, 4 так, что каждое число встречается хотя бы один раз…
Геометрия на решётке для гриля
Рассмотрим важный класс геометрических задач, своего рода «целочисленную геометрию». Объекты на целочисленных решётках изучаются даже в теории вероятностей. Например, случайные блуждания с их разносторонними практическими применениями.
Целочисленной решёткой Z² называется множество точек декартовой плоскости с целыми координатами. Бывает удобным представлять себе целочисленную решётку как бесконечный лист клетчатой бумаги. Многоугольник считается расположенным на Z², если все его вершины являются точками (узлами) этой решётки.
Площадь S многоугольника, расположенного на решётке, считается по простой формуле S=I+E/2-1, где I – количество узлов строго внутри многоугольника, E – на его границе, включая вершины. Эта формула названа в честь австрийского математика Георга Пика, доказавшего её в 1899 году.
Для доказательства формулы Пика во всей её полноте, придётся иметь дело с так называемыми примитивными треугольниками. Будем есть слона по частям или, как сказал бы Боб Дилан: «I can’t eat all that stuff in a single bite». Примитивные треугольники сравнимы с глыбами, которые каменотёс обрабатывает лишь тремя ударами резца, создавая тем самым заготовки для более изысканных произведений искусства.
#олимпиады #геометрия
Примитивные треугольники (#111)
Рассмотрим важный класс геометрических задач, своего рода «целочисленную геометрию». Объекты на целочисленных решётках изучаются даже в теории вероятностей. Например, случайные блуждания с их разносторонними практическими применениями.
Целочисленной решёткой Z² называется множество точек декартовой плоскости с целыми координатами. Бывает удобным представлять себе целочисленную решётку как бесконечный лист клетчатой бумаги. Многоугольник считается расположенным на Z², если все его вершины являются точками (узлами) этой решётки.
Площадь S многоугольника, расположенного на решётке, считается по простой формуле S=I+E/2-1, где I – количество узлов строго внутри многоугольника, E – на его границе, включая вершины. Эта формула названа в честь австрийского математика Георга Пика, доказавшего её в 1899 году.
Для доказательства формулы Пика во всей её полноте, придётся иметь дело с так называемыми примитивными треугольниками. Будем есть слона по частям или, как сказал бы Боб Дилан: «I can’t eat all that stuff in a single bite». Примитивные треугольники сравнимы с глыбами, которые каменотёс обрабатывает лишь тремя ударами резца, создавая тем самым заготовки для более изысканных произведений искусства.
#олимпиады #геометрия
Примитивные треугольники (#111)
Medium
Примитивные треугольники (#111)
Треугольник с вершинами в узлах целочисленной решётки называется примитивным, если кроме своих вершин он не содержит внутри себя и на…
Ним
– Я знаю одну игру, в которой всегда выигрываю.
– Если вы не можете проиграть, это не игра.
– Я могу проиграть, но я всегда выигрываю.
В прошлом году в Мариенбаде
Логичным продолжением игр Баше, рассмотренных в постах Ёлочные игрушки (#18) и Ёлочные игрушки возвращаются (#17), является конечная игра с полной информацией ним.
Поклонникам арт-хауса рекомендуется к просмотру фильм В прошлом году в Мариенбаде, где игра занимает центральную часть сюжета. Здесь мы разбираем вариант стандартного условия выигрыша, когда победителем считается взявший последний предмет. В фильме играют в мизер, другими словами, когда взявший последнее является проигравшим. С точки зрения выигрышной стратегии мизер слегка сложнее, но имеет много общего со стандартным вариантом игры.
#игра #математикавискусстве
Игра Ним (#112)
– Я знаю одну игру, в которой всегда выигрываю.
– Если вы не можете проиграть, это не игра.
– Я могу проиграть, но я всегда выигрываю.
В прошлом году в Мариенбаде
Логичным продолжением игр Баше, рассмотренных в постах Ёлочные игрушки (#18) и Ёлочные игрушки возвращаются (#17), является конечная игра с полной информацией ним.
Поклонникам арт-хауса рекомендуется к просмотру фильм В прошлом году в Мариенбаде, где игра занимает центральную часть сюжета. Здесь мы разбираем вариант стандартного условия выигрыша, когда победителем считается взявший последний предмет. В фильме играют в мизер, другими словами, когда взявший последнее является проигравшим. С точки зрения выигрышной стратегии мизер слегка сложнее, но имеет много общего со стандартным вариантом игры.
#игра #математикавискусстве
Игра Ним (#112)
Medium
Игра Ним (#112)
На столе лежат четыре кучки из 1, 3, 5 и 7 предметов. Играют двое. За один ход может быть взято любое количество предметов (большее нуля)…
©
Давно ли вы катались на канатных дорогах? В этом году мне выдалось путешествие по городам Поволжья. Поэтому могу отрекомендовать канатку в Нижнем Новгороде / «на Бору» (местные так поправили). Отменные виды по-над Волгой.
Короче, недавно писали про авторские задачи. Лет десять назад я тоже придумал одну. Как говорится, не судите строго.
Итак, эксклюзив для подписчиков.
Кстати, если у вас есть свои задачки – присылайте, самые крутые обязательно запостим со всеми причитающимися почестями автору.
Канатка (#113)
Давно ли вы катались на канатных дорогах? В этом году мне выдалось путешествие по городам Поволжья. Поэтому могу отрекомендовать канатку в Нижнем Новгороде / «на Бору» (местные так поправили). Отменные виды по-над Волгой.
Короче, недавно писали про авторские задачи. Лет десять назад я тоже придумал одну. Как говорится, не судите строго.
Итак, эксклюзив для подписчиков.
Кстати, если у вас есть свои задачки – присылайте, самые крутые обязательно запостим со всеми причитающимися почестями автору.
Канатка (#113)
Medium
Канатка (#113)
Проехав от одного конца канатной дороги до другого, вы насчитали 100 встречных кабинок. Сколько всего кабинок на канатной дороге?
Леммы с красивым названием
В математике есть много утверждений с забавными названиями. Мой фаворит – это теорема о причёсывании ежа. Ещё есть такая лемма в теории графов, которая формулируется на языке рукопожатий: в любом коллективе число людей, совершивших нечётное число рукопожатий, чётно. Как ни странно, но доказательство леммы о рукопожатиях элементарно, хотя название-то какое!
В общем, к чему это я. Сегодняшнюю задачку можно решить и без лемм с красивым названием. На стиле. Просто к слову пришлось.
#графы
Страна Оз. Дороги (#114)
В математике есть много утверждений с забавными названиями. Мой фаворит – это теорема о причёсывании ежа. Ещё есть такая лемма в теории графов, которая формулируется на языке рукопожатий: в любом коллективе число людей, совершивших нечётное число рукопожатий, чётно. Как ни странно, но доказательство леммы о рукопожатиях элементарно, хотя название-то какое!
В общем, к чему это я. Сегодняшнюю задачку можно решить и без лемм с красивым названием. На стиле. Просто к слову пришлось.
#графы
Страна Оз. Дороги (#114)
Medium
Страна Оз. Дороги (#114)
В стране Оз есть три вида дорог: чёрные, белые и из жёлтого кирпича. Из каждого города выходит ровно по одной дороге каждого вида. Из…
IMO 2020
На прошлой неделе завершилась Международная Математическая Oлимпиада. Поздравляем наших ребят со вторым местом в неофициальном командном зачёте!
1. 🇨🇳 (215)
2. 🇷🇺 (185)
3. 🇺🇸 (183)
Подробная статистика.
Задачки прилагаются. Регламент: по 4,5 часа на три задачи.
На прошлой неделе завершилась Международная Математическая Oлимпиада. Поздравляем наших ребят со вторым местом в неофициальном командном зачёте!
1. 🇨🇳 (215)
2. 🇷🇺 (185)
3. 🇺🇸 (183)
Подробная статистика.
Задачки прилагаются. Регламент: по 4,5 часа на три задачи.
👍2
Как (не)правильно постить
Сразу отмечу следующее, хотя, наверное, и так уже понятно, но всё же, чтобы полностью снять экивоки. Большинство популярных контент-платформ (youtube, instagram) имеют рекомендательную ленту. Чтобы в неё попасть и там оставаться, нужно постить регулярно (= ежедневно). В телеграме другие механизмы продвижения и доставки контента (пока), поэтому писать можно как хочется, и ничего за это не будет. Конечно, пользователь сам может отписаться в любой момент, но алгоритмической дискриминации за нерегулярность не происходит. Чем я и пользуюсь. Другими словами, я объявляю все публикации НЕРЕГУЛЯРНЫМИ (это очень удобно 🙂), чтобы корректно управлять ожиданиями своей аудитории. Но не менее торжественно уточняю, что канал ЖИВ. А всем, кто с нами, огромное СПАСИБО!
Теперь продолжим математическую повестку с геометрии на клетчатой доске. В этот раз в «диагональном» варианте.
#олимпиады
Угловые соседи (#115)
Сразу отмечу следующее, хотя, наверное, и так уже понятно, но всё же, чтобы полностью снять экивоки. Большинство популярных контент-платформ (youtube, instagram) имеют рекомендательную ленту. Чтобы в неё попасть и там оставаться, нужно постить регулярно (= ежедневно). В телеграме другие механизмы продвижения и доставки контента (пока), поэтому писать можно как хочется, и ничего за это не будет. Конечно, пользователь сам может отписаться в любой момент, но алгоритмической дискриминации за нерегулярность не происходит. Чем я и пользуюсь. Другими словами, я объявляю все публикации НЕРЕГУЛЯРНЫМИ (это очень удобно 🙂), чтобы корректно управлять ожиданиями своей аудитории. Но не менее торжественно уточняю, что канал ЖИВ. А всем, кто с нами, огромное СПАСИБО!
Теперь продолжим математическую повестку с геометрии на клетчатой доске. В этот раз в «диагональном» варианте.
#олимпиады
Угловые соседи (#115)
Medium
Угловые соседи (#115)
Клетки доски 9 х 9 окрашены в красный и синий цвета. Докажите, что найдётся или клетка, у которой ровно два красных угловых соседа, или…
Год в условии задачи
Интересной традицией для авторов олимпиадных задач является использование года проведения в условии. Чаще всего год можно заменить на произвольное n и решать задачу в общем виде. Иногда это условно общий случай, например, если используется делимость года на некоторое число.
Сегодня предлагаем задачу Московской олимпиады 1994 года для 8 класса. Если заменить в формулировке год на текущий, то получится очень простой случай. Поэтому мы оставили оригинальное условие и дополнительно предлагаем вам решить задачу в общем случае.
#олимпиады #игра
Игра в квадраты (#116)
Интересной традицией для авторов олимпиадных задач является использование года проведения в условии. Чаще всего год можно заменить на произвольное n и решать задачу в общем виде. Иногда это условно общий случай, например, если используется делимость года на некоторое число.
Сегодня предлагаем задачу Московской олимпиады 1994 года для 8 класса. Если заменить в формулировке год на текущий, то получится очень простой случай. Поэтому мы оставили оригинальное условие и дополнительно предлагаем вам решить задачу в общем случае.
#олимпиады #игра
Игра в квадраты (#116)
Medium
Игра в квадраты (#116)
Двое играют на доске 19 х 94 клеток. Каждый по очереди отмечает квадрат по линиям сетки (любого возможного размера) и закрашивает его…
❤1
Конструктивные и неконструктивные доказательства
Доказательства существования чего-либо (например, системы наименования улиц, или раскраски, как в сегодняшней задаче) бывают конструктивными и неконструктивными.
В первом случае объект, существование которого доказывается, предъявляется в явном виде.
В последнем случае лишь доказывается, что «суслик есть», хоть мы его и не видим. Например, так работает принцип Дирихле.
В решении приводятся оба варианта доказательства. Однако понятно, что с практической точки зрения ценнее конструктивный вариант.
#олимпиады #графы
Цветочный город (#117)
Доказательства существования чего-либо (например, системы наименования улиц, или раскраски, как в сегодняшней задаче) бывают конструктивными и неконструктивными.
В первом случае объект, существование которого доказывается, предъявляется в явном виде.
В последнем случае лишь доказывается, что «суслик есть», хоть мы его и не видим. Например, так работает принцип Дирихле.
В решении приводятся оба варианта доказательства. Однако понятно, что с практической точки зрения ценнее конструктивный вариант.
#олимпиады #графы
Цветочный город (#117)
Telegraph
Цветочный город (#117)
В городе Цветочном В площадей и Р улиц (Р ≥ В+1). Каждая улица соединяет две площади и не проходит через другие площади. По существующей в городе традиции улица может называться либо Синей, либо Красной. Ежегодно в городе происходит переименование: выбирается…