Задача #2 частенько ставит в ступор, хотя она и не очень сложная.
Предположим противное, то есть в каждой урне для каждого кандидата есть бюллетень, который его не содержит. Перенумеруем урны числами от 1 до n+1. Возьмем произвольный бюллетень из последней урны. В нем n фамилий — занумеруем их числами от 1 до n. Далее возьмем из k-ой урны тот бюллетень, который не содержит k-ую фамилию. Полученный таким образом набор бюллетеней противоречит условию задач.
Предположим противное, то есть в каждой урне для каждого кандидата есть бюллетень, который его не содержит. Перенумеруем урны числами от 1 до n+1. Возьмем произвольный бюллетень из последней урны. В нем n фамилий — занумеруем их числами от 1 до n. Далее возьмем из k-ой урны тот бюллетень, который не содержит k-ую фамилию. Полученный таким образом набор бюллетеней противоречит условию задач.
👍10❤2🔥1
Граф по понедельникам
Автор А.В. Шаповалов, задача с какого-то Матпраздника.
#5. Среди 49 школьников каждый знаком не менее чем с 25 другими. Докажите, что можно их разбить на группы из двух или трёх человек так, чтобы каждый был знаком со всеми в своей группе.
#граф
Автор А.В. Шаповалов, задача с какого-то Матпраздника.
#5. Среди 49 школьников каждый знаком не менее чем с 25 другими. Докажите, что можно их разбить на группы из двух или трёх человек так, чтобы каждый был знаком со всеми в своей группе.
#граф
👍15🥰3✍2❤1
Решение задачи #3 с командной олимпиады Уральского турнира.
Решение выглядит довольно традиционна для таких задач — раскраска. Покрасим часть клеток диаманта, как показано на картинке слева (парами диагоналей). Тогда каждое положение одной из предложенных тетраминошек устроено так, что разность числа закрашенных и незакрашенных клеток в ней делится на 4. Но тогда и во всем диаманте число закрашенных клеток должно иметь тот же остаток от деления на 4, что и число незакрашенных. Нетрудно проверить, что это выполнено при n, имеющих остаток 0 или 3 от деления на 4. Разрезания диамантов ранга 3 и 4 приведены на рисунке справа (снизу вверх), там же можно увидеть как делать переход от 4k к 4k+3 и от 4k+3 к 4k+4.
Решение выглядит довольно традиционна для таких задач — раскраска. Покрасим часть клеток диаманта, как показано на картинке слева (парами диагоналей). Тогда каждое положение одной из предложенных тетраминошек устроено так, что разность числа закрашенных и незакрашенных клеток в ней делится на 4. Но тогда и во всем диаманте число закрашенных клеток должно иметь тот же остаток от деления на 4, что и число незакрашенных. Нетрудно проверить, что это выполнено при n, имеющих остаток 0 или 3 от деления на 4. Разрезания диамантов ранга 3 и 4 приведены на рисунке справа (снизу вверх), там же можно увидеть как делать переход от 4k к 4k+3 и от 4k+3 к 4k+4.
❤6🤯6👍3✍1🔥1
Forwarded from Непрерывное математическое образование
propp.pdf
607.3 KB
James Propp написал в сентябрьском Math Horizons решение задачи выше
👍6❤2🤯2🔥1
ВсОШ-1999, Регион, 11.3, С.Л. Берлов
#6. В классе каждый болтун дружит хотя бы с одним молчуном. При этом болтун молчит, если в кабинете находится нечетное число его друзей – молчунов. Докажите, что учитель может пригласить на факультатив не менее половины класса так, чтобы все болтуны молчали.
#6. В классе каждый болтун дружит хотя бы с одним молчуном. При этом болтун молчит, если в кабинете находится нечетное число его друзей – молчунов. Докажите, что учитель может пригласить на факультатив не менее половины класса так, чтобы все болтуны молчали.
❤21👍5👎1
Граф по понедельникам
Решение задачи #5
Мне очень нравится официальное решение этой задачи... Почему Фёдор?
Представим, что сначала все 49 школьников стоят в коридоре, и будем постепенно запускать их в класс. При этом будем делать это так, чтобы в классе в любой момент времени дети были разбиты на требуемые группы. Пусть в коридоре стоит школьник Фёдор. Если он знаком с каким-то другим школьником, стоящим в коридоре, то просто запустим их двоих в класс. Иначе все знакомые Фёдора уже в классе. Так как в классе менее 50 школьников, они разбиты менее чем на 25 групп. Значит, среди знакомых Фёдора какие-то двое находятся в одной группе. Если это группа из двух школьников, то впустим Фёдора в класс, добавив его к этой группе. Если же это группа из трёх школьников, то попросим одного из знакомых Фёдора образовать с ним группу, а оставшихся школьников оставим вдвоём.
Так, постепенно впуская школьников в класс, мы добьёмся того, что все школьники будут разделены на требуемые группы.
Решение задачи #5
Мне очень нравится официальное решение этой задачи... Почему Фёдор?
Представим, что сначала все 49 школьников стоят в коридоре, и будем постепенно запускать их в класс. При этом будем делать это так, чтобы в классе в любой момент времени дети были разбиты на требуемые группы. Пусть в коридоре стоит школьник Фёдор. Если он знаком с каким-то другим школьником, стоящим в коридоре, то просто запустим их двоих в класс. Иначе все знакомые Фёдора уже в классе. Так как в классе менее 50 школьников, они разбиты менее чем на 25 групп. Значит, среди знакомых Фёдора какие-то двое находятся в одной группе. Если это группа из двух школьников, то впустим Фёдора в класс, добавив его к этой группе. Если же это группа из трёх школьников, то попросим одного из знакомых Фёдора образовать с ним группу, а оставшихся школьников оставим вдвоём.
Так, постепенно впуская школьников в класс, мы добьёмся того, что все школьники будут разделены на требуемые группы.
❤20👍4
Клеточки и разрезания по пятницам.
#7. Можно ли разрезать квадрат на 15 равных шестиугольников?
#разрезания
#7. Можно ли разрезать квадрат на 15 равных шестиугольников?
#разрезания
🤮24❤11✍3👍1👎1💩1
Разбираем задачу #6 про молчунов и болтунов
Официальное решение задачи состоит в построении искомого набора по индукции. Однако можно поступить иначе.
Пусть у нас k молчунов. Для любого подмножества молчунов (таких 2^k) выберем всех болтунов, которых можно к ним добавить — назовем это подходящей группой. Посчитаем сколько в среднем участников в такой подходящей группе. Каждый молчун попадает ровно в половину таких групп (его можно взять или не взять). Каждый болтун (скажем, Петя) тоже входит ровно в половину таких групп. Действительно, можно выделить петиного молчаливого друга (скажем, Васю) и разбить все подмножества молчунов на пары: содержащие Васю и не содержащие. В каждой паре к одному подмножеству Петю добавить можно, а ко второму нельзя. Поскольку каждый ученик входит ровно в половину подходящих групп, то в какой-то группе не менее половины всех учеников класса.
Официальное решение задачи состоит в построении искомого набора по индукции. Однако можно поступить иначе.
Пусть у нас k молчунов. Для любого подмножества молчунов (таких 2^k) выберем всех болтунов, которых можно к ним добавить — назовем это подходящей группой. Посчитаем сколько в среднем участников в такой подходящей группе. Каждый молчун попадает ровно в половину таких групп (его можно взять или не взять). Каждый болтун (скажем, Петя) тоже входит ровно в половину таких групп. Действительно, можно выделить петиного молчаливого друга (скажем, Васю) и разбить все подмножества молчунов на пары: содержащие Васю и не содержащие. В каждой паре к одному подмножеству Петю добавить можно, а ко второму нельзя. Поскольку каждый ученик входит ровно в половину подходящих групп, то в какой-то группе не менее половины всех учеников класса.
❤8👍4
Граф по понедельникам
61-й Уральский турнир Юных математиков. Второй тур, высшая старшая лига. (Romanian TST 2 2008, Problem 4)
#8. В связном графе с n вершинами каждое ребро содержится хотя бы в одном треугольнике. Найдите наименьшее возможное количество рёбер в этом графе.
#граф
61-й Уральский турнир Юных математиков. Второй тур, высшая старшая лига. (Romanian TST 2 2008, Problem 4)
#8. В связном графе с n вершинами каждое ребро содержится хотя бы в одном треугольнике. Найдите наименьшее возможное количество рёбер в этом графе.
#граф
🔥15👍6❤3
Не знаю, почему на задачу #7 была такая реакция. Мне эта задача кажется довольно прикольной, потому что опирается на факт, который появляется обычно в младшеклассных кружках.
Дело в том, что прямоугольник 5×9 можно разрезать на уголки из трех клеток. А для того, чтобы произвести разрезание квадрата на равные шестиугольники можно взять указанное разрезание прямоугольника 5×9 и растянуть его по вертикали в 9/5 раза.
Дело в том, что прямоугольник 5×9 можно разрезать на уголки из трех клеток. А для того, чтобы произвести разрезание квадрата на равные шестиугольники можно взять указанное разрезание прямоугольника 5×9 и растянуть его по вертикали в 9/5 раза.
🔥32🤮11👍6❤1🤡1
Комби числа с Венгерской олимпиады 1952-го года
#9. Из целых чисел от 1 до 3n выбрали n+2 каких-то чисел. Доказать, что при n>1 среди выбранных чисел непременно найдутся два таких, разность между которыми больше n, но меньше 2n.
При n = 60 авторы предлагают следующую переформулировку.
Библиотека открывается в 12 часов дня и закрывается в 15 часов. Входит в библиотеку разрешается с интервалом в одну минуту. Первый читатель может войти в библиотеку ровно в 12:00, последний — в 14:59. Входить в библиотеку читателям разрешается только по одному. Через час после прихода в библиотеку читатель засыпает над книгами и спит ровно час, если только закрытие библиотеки не прервет его сон. Входить в библиотеку, когда кто-нибудь из читателей спит, воспрещается. Доказать, что при столь странных правилах 62 человека не смогут побывать в библиотеке за один день.
#комбичисла
#9. Из целых чисел от 1 до 3n выбрали n+2 каких-то чисел. Доказать, что при n>1 среди выбранных чисел непременно найдутся два таких, разность между которыми больше n, но меньше 2n.
При n = 60 авторы предлагают следующую переформулировку.
Библиотека открывается в 12 часов дня и закрывается в 15 часов. Входит в библиотеку разрешается с интервалом в одну минуту. Первый читатель может войти в библиотеку ровно в 12:00, последний — в 14:59. Входить в библиотеку читателям разрешается только по одному. Через час после прихода в библиотеку читатель засыпает над книгами и спит ровно час, если только закрытие библиотеки не прервет его сон. Входить в библиотеку, когда кто-нибудь из читателей спит, воспрещается. Доказать, что при столь странных правилах 62 человека не смогут побывать в библиотеке за один день.
#комбичисла
👍8🥰5❤3
Forwarded from Математические кружки | «МТ кружки»
Всем привет!
Сегодня опять задача с кружка 7-го класса, и опять про здание! На этот раз про треугольный замок! Кстати, замок на фотографии — это Rushton Triangular Lodge, спроектированный сэром Томасом Трешамом.
Замок имеет форму правильного треугольника, разбитого на 25 одинаковых залов, каждый из которых также имеет форму правильного треугольника. В стене между любыми двумя залами есть дверь. Путник хочет обойти как можно больше залов, не заходя ни в один зал дважды. Какое наибольшее количество залов ему удастся обойти?
#мтзадача
Сегодня опять задача с кружка 7-го класса, и опять про здание! На этот раз про треугольный замок! Кстати, замок на фотографии — это Rushton Triangular Lodge, спроектированный сэром Томасом Трешамом.
Замок имеет форму правильного треугольника, разбитого на 25 одинаковых залов, каждый из которых также имеет форму правильного треугольника. В стене между любыми двумя залами есть дверь. Путник хочет обойти как можно больше залов, не заходя ни в один зал дважды. Какое наибольшее количество залов ему удастся обойти?
#мтзадача
👍14👎2❤1
Разбираем задачу #8.
Задача не очень хитрая.
UPD: Не очень верное решение ниже)
Надо воспользоваться как-то связностью, которая явно в задаче по делу. Сразу приходит идея выделить остовное дерево, поскольку это дает какую-то тривиальную оценку снизу на количество ребер. В нем как минимум n-1 ребро, при этом никакие три из них не образуют треугольник. Тогда легко видеть, что есть еще как минимум [n/2] дополнительных ребер.
Для нечетного n пример приведен на рисунке. Для четного требуется легкая модификация.
UPD: Не очень верное решение ниже)
Надо воспользоваться как-то связностью, которая явно в задаче по делу. Сразу приходит идея выделить остовное дерево, поскольку это дает какую-то тривиальную оценку снизу на количество ребер. В нем как минимум n-1 ребро, при этом никакие три из них не образуют треугольник. Тогда легко видеть, что есть еще как минимум [n/2] дополнительных ребер.
Для нечетного n пример приведен на рисунке. Для четного требуется легкая модификация.
👍9😁4
Forwarded from Математические кружки | «МТ кружки»
Всем привет! Разбираем задачу про треугольный замок.
В этой задаче более-менее сразу понятно, что все комнаты обойти нельзя (например, нельзя попасть во все угловые). Но как понять, какое наибольшее число комнат можно посетить? Доказательство таких утверждений состоит обычно из двух частей: оценка и пример. В большинстве задач такого типа пример построить довольно легко, а вот оценка требует изобретательности!
В данной задаче работает метод раскраски. Надо покрасить залы в шахматном порядке (зелёный и белый цвета на рисунке). Перемещаясь из зала в зал, мы обязательно меняем цвет. Белых залов всего 10, и цвета мы должны чередовать. Учитывая, что стартовать и финишировать мы можем в зелёных залах, можно рассчитывать на посещение максимум 10+11=21 зала. Пример с маршрутом по 21 залу — на рисунке.
В этой задаче более-менее сразу понятно, что все комнаты обойти нельзя (например, нельзя попасть во все угловые). Но как понять, какое наибольшее число комнат можно посетить? Доказательство таких утверждений состоит обычно из двух частей: оценка и пример. В большинстве задач такого типа пример построить довольно легко, а вот оценка требует изобретательности!
В данной задаче работает метод раскраски. Надо покрасить залы в шахматном порядке (зелёный и белый цвета на рисунке). Перемещаясь из зала в зал, мы обязательно меняем цвет. Белых залов всего 10, и цвета мы должны чередовать. Учитывая, что стартовать и финишировать мы можем в зелёных залах, можно рассчитывать на посещение максимум 10+11=21 зала. Пример с маршрутом по 21 залу — на рисунке.
👍18❤3
Клеточки и разрезания по пятницам
61-й Уральский турнир Юных математиков. Финал, старшая высшая лига, бои за 1-4 места. USA TSTST 2023
#10. Дано натуральное n. Докажите, что можно закрасить некоторые клетки бесконечной клетчатой плоскости в зелёный цвет так, чтобы любой прямоугольник из n клеток содержал нечётное число зелёных клеток.
#клеточки
61-й Уральский турнир Юных математиков. Финал, старшая высшая лига, бои за 1-4 места. USA TSTST 2023
#10. Дано натуральное n. Докажите, что можно закрасить некоторые клетки бесконечной клетчатой плоскости в зелёный цвет так, чтобы любой прямоугольник из n клеток содержал нечётное число зелёных клеток.
#клеточки
❤13👍5
Разбираем задачу #9
Во-первых, не умаляя общности можно считать, что в наборе есть число 3n (иначе можно добавить ко всем числам одно и то же). Во-вторых, это означает, что чисел от n+1 до 2n-1 в наборе нет — они все образовывали бы с 3n искомую пару. Остальные числа разобьем на пары
(1, 2n), (2,2n+1), ..., (n, 3n-1)
— все эти пары удовлетворяют условию и в какой-то паре по принципу Дирихле выбраны оба числа.
Во-первых, не умаляя общности можно считать, что в наборе есть число 3n (иначе можно добавить ко всем числам одно и то же). Во-вторых, это означает, что чисел от n+1 до 2n-1 в наборе нет — они все образовывали бы с 3n искомую пару. Остальные числа разобьем на пары
(1, 2n), (2,2n+1), ..., (n, 3n-1)
— все эти пары удовлетворяют условию и в какой-то паре по принципу Дирихле выбраны оба числа.
🔥9
Хоть сегодня и понедельник, но будет не граф, а задача про множества, но по духу похожая на граф.
61-й Уральский турник Юных математиков. Финал. Высшая старшая лига. Бои за 1-4 места.
#11. В каждом зоопарке обитает ровно 100 видов животных. Зоопарки бывают двух типов: с вайфаем и без вайфая. Для любой пары зоопарков разного типа есть вид животных, который содержится в обоих зоопарках. Докажите, что все виды животных можно разделить на три непересекающихся списка так, чтобы в каждом зоопарке обитали животные не менее чем из двух списков.
#множества
61-й Уральский турник Юных математиков. Финал. Высшая старшая лига. Бои за 1-4 места.
#11. В каждом зоопарке обитает ровно 100 видов животных. Зоопарки бывают двух типов: с вайфаем и без вайфая. Для любой пары зоопарков разного типа есть вид животных, который содержится в обоих зоопарках. Докажите, что все виды животных можно разделить на три непересекающихся списка так, чтобы в каждом зоопарке обитали животные не менее чем из двух списков.
#множества
👍10🕊2🤯1😭1
Разбираем задачу #10
Легко заметить, что если пример построен для какого-то n, то он годится для np, где p — нечетное простое число. Поэтому достаточно строить пример для степеней двойки. Поэтому пусть n=2^k. Далее считаем, что в зеленых клетках стоят единички, а в белых — нули.
Не знаю, как младшеклассники должны строить пример для степени двойки, но я знаю такой метод. Надо для каждого m<k расставить единички так, чтобы в каждом прямоугольнике 2^m×2^(k-m) стояло нечетное число единиц, а в прямоугольники любой другой формы и той же площадью — четное. А затем сложить все такие раскраски по модулю 2.
Искомая раскраска для 2^m×2^(k-m) строится так: надо поставить единичку в клетку, если координата по y делится на 2^m, а координата по x делится на 2^(k-m).
В целом, сумму таких раскрасок, наверное, можно записать явно для каждой клетки...
Легко заметить, что если пример построен для какого-то n, то он годится для np, где p — нечетное простое число. Поэтому достаточно строить пример для степеней двойки. Поэтому пусть n=2^k. Далее считаем, что в зеленых клетках стоят единички, а в белых — нули.
Не знаю, как младшеклассники должны строить пример для степени двойки, но я знаю такой метод. Надо для каждого m<k расставить единички так, чтобы в каждом прямоугольнике 2^m×2^(k-m) стояло нечетное число единиц, а в прямоугольники любой другой формы и той же площадью — четное. А затем сложить все такие раскраски по модулю 2.
Искомая раскраска для 2^m×2^(k-m) строится так: надо поставить единичку в клетку, если координата по y делится на 2^m, а координата по x делится на 2^(k-m).
В целом, сумму таких раскрасок, наверное, можно записать явно для каждой клетки...
❤6👍2