ВсОШ-1999, Региональный этап, 10.7
В.Л. Дольников

#2. Каждый голосующий на выборах вносит в избирательный бюллетень фамилии n кандидатов. На избирательном участке находится n+1 урна. После выборов выяснилось, что в каждой урне лежит по крайней мере один бюллетень и при всяком выборе (n+1) -го бюллетеня по одному из каждой урны найдется кандидат, фамилия которого встречается в каждом из выбранных бюллетеней. Докажите, что по крайней мере в одной урне все бюллетени содержат фамилию одного и того же кандидата.

Каналу срочно требуется аватарка

UPD. И это не конкурс идиотских картинок

Клеточки и разрезания по пятницам.

Задача с командной олимпиады проходящего сейчас 61-го Уральского турнира. Задача предлагалась в 8-ом классе под номером 8.

#3. Ацтекский диамант ранга n — это клетчатая фигура «ромбик» из 2n(n + 1) клеток, вдоль каждой «стороны» которого расположено n клеток. При каких n ацтекский диамант ранга n можно разрезать на прямые тетрамино и S-тетрамино (фигурки можно поворачивать и переворачивать)?

#клеточки #разрезания

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

Решение задачи #1

Кажется, автор задачи Вл.Л. Дольников и поэтому вряд ли он предлагал решение этой задачи из соображений, предложенное выше (где делится на две части самый тяжелый кусочек сыра). Скорее, его изначальное решение следующее. Представим наши кусочки сыра как однородные отрезки (что тоже предлагалось выше) и сомкнём окружность из них. Любая прямая, проходящая через центр будет делить общую массу пополам. Рассмотрим ориентированную прямую и функция число кусочков справа минус число кусочков слева, тогда из соображений непрерывности (aka Борсук-Улам) - непрерывного вращения прямой - несложно завершается решение. (Еще нужно заметить, что функция принимает четные значения тогда и только, когда прямая проходит через точку стыка и внутренность какого-то отрезка.)

Задача с первого тура проходящего сейчас 61-го Уральского турнира. Задача предлагалась в высшей старшей лиге.

#4. Дан набор из 2n натуральных чисел, сумма которых кратна n. Разрешается выбрать n чисел и прибавить ко всем одно и то же натуральное число. Докажите, что можно сделать все числа равными, выполнив не более 2n − 1 таких операций.

#комбичисла

Задача #2 частенько ставит в ступор, хотя она и не очень сложная.

Предположим противное, то есть в каждой урне для каждого кандидата есть бюллетень, который его не содержит. Перенумеруем урны числами от 1 до n+1. Возьмем произвольный бюллетень из последней урны. В нем n фамилий — занумеруем их числами от 1 до n. Далее возьмем из k-ой урны тот бюллетень, который не содержит k-ую фамилию. Полученный таким образом набор бюллетеней противоречит условию задач.

Граф по понедельникам

Автор А.В. Шаповалов, задача с какого-то Матпраздника.

#5. Среди 49 школьников каждый знаком не менее чем с 25 другими. Докажите, что можно их разбить на группы из двух или трёх человек так, чтобы каждый был знаком со всеми в своей группе.

#граф

Решение задачи #3 с командной олимпиады Уральского турнира.

Решение выглядит довольно традиционна для таких задач — раскраска. Покрасим часть клеток диаманта, как показано на картинке слева (парами диагоналей). Тогда каждое положение одной из предложенных тетраминошек устроено так, что разность числа закрашенных и незакрашенных клеток в ней делится на 4. Но тогда и во всем диаманте число закрашенных клеток должно иметь тот же остаток от деления на 4, что и число незакрашенных. Нетрудно проверить, что это выполнено при n, имеющих остаток 0 или 3 от деления на 4. Разрезания диамантов ранга 3 и 4 приведены на рисунке справа (снизу вверх), там же можно увидеть как делать переход от 4k к 4k+3 и от 4k+3 к 4k+4.

James Propp написал в сентябрьском Math Horizons решение задачи выше

ВсОШ-1999, Регион, 11.3, С.Л. Берлов

#6. В классе каждый болтун дружит хотя бы с одним молчуном. При этом болтун молчит, если в кабинете находится нечетное число его друзей – молчунов. Докажите, что учитель может пригласить на факультатив не менее половины класса так, чтобы все болтуны молчали.