Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Комбинаторика на Всесибе: игры, графы, конструктивы

Тема Всесиб (Всесибирская открытая олимпиада школьников)

Комбинаторика на Всесибе: игры, графы, конструктивы

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела всесиб (всесибирская открытая олимпиада школьников)

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#119873

В выпуклом $n$ -угольнике проведены диагонали, разбивающие его на треугольники, и не пересекающиеся по внутренним точкам. При этом из каждой вершины выходит чётное, может быть нулевое, количество диагоналей. Доказать, что это возможно тогда и только тогда, когда $n$ делится на $3.$

Источники: Всесиб-2025, 11.5(см. sesc.nsu.ru)

Подсказки к задаче

Подсказка 1:

Хм... А правда ли, что для n=3 такую триангуляцию всегда можно придумать? Попробуем построить пример, допустим, для девятиугольника, а потом обобщим.

Подсказка 2:

Пронумеруем вершины от 1 до 9. Заметим, что выбрав 5 подряд идущих вершин и соединив их через одну (пятую соединим с первой), образуются нужные нам треугольники без пересечений. Как это замечание помогает построить пример? Как это можно обобщить?

Подсказка 3:

Давайте попарно соединим вершины 1, 3k и 3k+2 для всех k = 1, 2, ..., m - 1, где m = n/3. Это и есть нужная нам триангуляция. Нетрудно убедиться, что при таком разбиении из всех вершин выходит чётное количество рёбер. Сколько их будет для каждой вершины?

Подсказка 4:

Так... Пример удалось построить, но как показать, что он существует только для n кратных 3? У нас в распоряжении есть разбиение на треугольники и знание о чётности степеней вершин. Как их можно связать?

Подсказка 5:

Давайте раскрасим наши получившиеся треугольники в два цвета так, чтобы любые два треугольника, имеющие общую сторону, были разного цвета. Почему это всегда можно сделать? Что теперь можно сказать про диагонали триангуляции и стороны исходного многоугольника?

Подсказка 6:

Заметим, что все стороны изначального n-угольника одного цвета. Пусть белого. Тогда каждая диагональ триангуляции и каждая сторона исходного многоугольника будут сторонами ровно одного белого треугольника. Пусть их k. Как тогда можно выразить n через k?

Подсказка 7:

Да! 3k = n - 3 + n = 2n - 3. Почему тогда n кратно 3?

Показать доказательство

Сначала покажем, как осуществить требуемую в условии триангуляцию $n−$ угольника, если $n$ делится на $3.$ Занумеруем вершины $n−$ угольника по часовой стрелке числами от $1$ до $n= 3m.$ Проведём диагонали, попарно соединяющие вершины $1,3k,3k+2$ для всех $k =1,2,...,m − 1,$ они и образуют искомую триангуляцию. При этом из вершины номер $1$ выходит $2m − 2$ диагонали, из вершин $3k,3k +2$ для всех $k= 1,2,...,m− 1$ по $2$ диагонали и из вершин $2,$ $3m$ и $3k +1$ для всех $k= 1,2,...,m − 1$ — $0$ диагоналей.

Теперь докажем, что, если можно осуществить требуемую в условии триангуляцию $n−$ угольника, то $n$ делится на $3.$ Триангуляцию из условия будем дальше называть хорошей.

Рассмотрим хорошую триангуляцию $n−$ угольника. Хорошо известно, что её треугольники можно раскрасить в $2$ цвета, белый и чёрный, так, что любые два треугольника, имеющих общую сторону, окрашены в разные цвета. Этот факт легко доказать индукцией по числу диагоналей, начав с монотонной окраски всего многоугольника, добавляя по одной диагонали и меняя каждый раз окраску всех частей многоугольника с одной из сторон от добавляемой диагонали на противоположный цвет.

Заметим, что, если из каждой вершины $n−$ угольника выходит чётное число диагоналей, то каждая его сторона является стороной треугольников одного, скажем чёрного, цвета. Тогда каждая диагональ триангуляции и каждая сторона $n−$ угольника являются сторонами в точности одного из чёрных треугольников. Если чёрных треугольников $k$ штук, то $3k= n− 3+ n= 2n− 3,$ откуда следует, что $2n − 3$ делится на $3.$ Отсюда легко следует, что и $n$ делится на $3.$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#126314

По кругу в некотором порядке выписаны все натуральные числа от 1 до 100 включительно. Пара не соседних чисел $a$ и $b$ называется хорошей, если все числа, выписанные по одну из сторон от хорды, соединяющей $a$ и $b,$ меньше $a$ и $b.$ Какое количество хороших пар чисел может содержаться среди выписанных, в зависимости от порядка записи? Найти все возможные значения.

Источники: Всесиб - 2025, 10.5 ( см. sesc.nsu.ru)

Подсказки к задаче

Подсказка 1

Попробуйте выписать числа от 1 до n по часовой стрелке. Какие пары будут хорошими?

Подсказка 2

Все пары, содержащие число n, кроме каких?

Подсказка 3

Кроме тех пар, в которых содержатся соседние с n числа. Получим целых n-3 хороших пар. :)

Подсказка 4

Давайте попробуем доказать, что их всегда будет n-3. Воспользуйтесь методом математической индукции.

Подсказка 5

Можно перебором доказать базу для n = 4.

Подсказка 6

Осталось доказать переход. Мы добавляем ещё одно число. Какое число не содержит ни одна хорошая пара?

Подсказка 7

Этим число будет единица. А что будет, если мы её выкинем?

Подсказка 8

Заметим, что есть хорошая пара соседних с 1 чисел, которая пропадает при вычёркивании единицы.

Показать ответ и решение

Первое решение

Если записать числа от 1 до $n$ по часовой стрелке, то хорошими будут все пары, содержащие число $n,$ кроме пар соседних с $n$ чисел $(n;1)$ и $(n;n − 1).$ Всего $n− 3$ пары.

Докажем индукцией по $n,$ что если по кругу выписаны все натуральные числа от 1 до $n,$ то количество хороших пар всегда равно $n − 3$ вне зависимости от порядка записи.

База индукции: $n = 4.$

Числа от 1 до 4 можно выписать по кругу четырьмя различными способами:

(1234);(1243);(1324);(1423)

Хорошими в них будут единственные пары:

(-2 4);( 2-3);( 3 4);( 4 3)

При этом $n− 3= 4− 3= 1.$ База индукции выполнена.

Шаг индукции.

Пусть утверждение индукции выполнено для всех количеств чисел от 4 до $n,$ докажем для $n+ 1.$ Рассмотрим все натуральные числа от 1 до $n+ 1,$ выписанные в произвольном порядке. Заметим, что ни одна хорошая пара чисел не содержит число 1, и пара чисел, записанных слева и справа от 1, образуют хорошую пару. Назовем такую пару маленькой.

Теперь вычеркнем единицу, получим $n$ выписанных чисел от 2 до $n +1.$ Пары, которые были хорошим для исходных $n+ 1$ чисел, кроме маленькой, останутся хорошими и для полученных $n$ чисел, верно и обратное.

Количество хороших пар для полученных $n +1$ чисел, по предположению индукции, равно $n +1− 3= n− 2.$ Все эти пары останутся хорошими, если вернуть назад вычеркнутую единицу, и ещё к ним добавится новая пара чисел — маленькая. Всего получаем $n − 2+ 1= n− 1= n+ 1− 3$ хороших пар, что доказывает шаг индукции.

В итоге ответ — 97 хороших пар чисел.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение

Рассмотрим произвольную запись по кругу в некотором порядке всех натуральных чисел от 1 до 100. Будем считать их расположенными в вершинах правильного 100-угольника, обозначим его $C.$ Сначала докажем, что хорды, соответствующие двум разным хорошим парам чисел, не могут пересекаться по внутренним точкам.

Рассмотрим две хороших пары чисел $a< b,$ $c< d,$ в которых все 4 числа различны. Можно считать, что $a <c.$ Если хорды, соответствующие этим парам, пересекаются по внутренней точке, то числа $c$ и $d$ лежат по разные стороны от хорды $ab$ и оба больше $a,$ что противоречит «хорошести» пары $(a;b).$

Теперь предположим, что проведены хорды для всех хороших пар выписанных чисел. Как мы только что доказали, они не пересекаются по внутренним точкам, поэтому разбивают наш 100-угольник на несколько многоугольников с вершинами в вершинах 100-угольника. Если среди них есть многоугольник $M$ с более, чем тремя вершинами, рассмотрим самое маленькое из чисел в вершинах $M,$ обозначим его за $x,$ соседние с ним в $M$ числа обозначим за $y$ и $z.$ Рассмотрим возникающие при этом варианты расположения соответствующих им вершин в 100-угольнике $C.$

1) Все три числа $x,y,z$ записаны в трёх последовательных вершинах $C.$ Тогда $yz$ будет хорошей хордой $C,$ что противоречит предположению о том, что все хорошие хорды уже проведены.

2) Одна из пар $(x;y),$ $(x;z)$ является хорошей в $C,$ а вторая образует пару соседних вершин $C.$ Можно считать, что хорошей является пара $(x,y).$ Так как $x< z,$ все числа, лежащие в $C$ относительно $z$ с другой стороны от хорды $xy,$ меньше $x.$ Тогда хорда $yz$ снова будет не проведённой хорошей хордой $C.$

3) $(x;y)$ и $(x;z)$ являются хорошими в $C.$ В этом случае, так как $x< z,$ $y <z,$ маленькие числа для хорды $xy$ лежат в $C$ с другой относительно $z$ стороны, а маленькие числа для хорды $xz$ лежат в $C$ с другой относительно $y$ стороны. Следовательно, хорда $yz$ будет непроведенной хорошей хордой 100-угольника, у которой маленькие числа расположены в $C$ с той же стороны, что и $x.$ При том числа $y,x,z$ записаны в трёх последовательных вершинах многоугольника $M$ с более, чем тремя вершинами, поэтому $yz$ не может быть стороной $M,$ и тем более стороной $C.$

Таким образом, если хотя бы один из многоугольников, на которые разбивают 100-угольник хорошие хорды, не является треугольником, то всегда можно провести ещё одну хорошую хорду. Следовательно, все хорошие хорды разбивают 100-угольник на треугольники для любого порядка записи чисел от 1 до 100 в его вершинах.

Сумма величин всех углов 100-угольника $C$ равна $98⋅180∘$ (сумма внутренних углов выпуклого $n$ -угольника равна $(n− 2)⋅180∘).$ В данной ситуации, когда все вершины треугольников лежат в вершинах $C,$ она равна сумме углов во всех треугольниках разбиения. Сумма углов в каждом треугольнике разбиения равна $180∘,$ поэтому общее число треугольников разбиения равно 98. В общем числе $3⋅98$ сторон всех треугольников разбиения каждая хорда учитывается дважды, а каждая сторона — один раз. Следовательно, количество проведённых хороших хорд равно $(3⋅98− 100):2= 97$ для любого порядка записи чисел от 1 до 100 в его вершинах.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 3#80745

Найти все множества $X$ , состоящие из различных натуральных чисел от 1 до 50 такие, что: 1) X содержит не все числа от 1 до 50, но не меньше трёх из них, 2) X содержит числа 1 и 50, 3) для любых трёх чисел $x< y < z$ из X число $x− y+ z$ также принадлежит X.

Источники: Всесиб-2024, 11.2 (см. sesc.nsu.ru)

Подсказки к задаче

Подсказка 1

Попробуйте упорядочить все взятые числа, для фиксированного, подходящего под условия набора и посмотреть на три подряд идущих числа. Что можно сказать?

Подсказка 2

Если у нас есть три подряд идущих числа x, y, z: x < y < z, то число x + z - y, которое больше x, но меньше z, то оно равно y. Что же это значит?

Подсказка 3

Это значит, что y = (x + z)/2, а это критерий арифметической прогрессии. Значит, наш набор - это арифметическая прогрессия. Что мы можем тогда сказать, если она начинается с 1, а заканчивается 50?

Подсказка 4

Это значит, что 49 делится на разность между соседними членами. И либо это 1, либо 7, либо 49. Все варианты нам подходят или нет?

Показать ответ и решение

Отсортируем числа из множества $X$ по возрастанию:

x1 < x2 <x3 <...<xk

Для любых трех последовательных чисел $xi < xi+1 <xi+2$ число $xi+xi+2− xi+1$ по условию лежит в $X$ . Но

x < x+ x − x < x i i i+2 i+1 i+2

Тогда это число должно равняться $xi+1$ , откуда $xi+1 = xi+xi+2 2$ . В силу произвольности выбора номера $i$ получаем, что каждое число является средним арифметическим двух его соседей, но тогда это арифметическая прогрессия.

По условию числа $1,50∈ X$ , то есть $50= xk = x1+(k− 1)⋅d= 1+(k− 1)⋅d$ , где $d$ - разность прогрессии.

$(k− 1)⋅d= 49$ и в силу того, что $50> k> 2$ , а $d$ натуральное. Имеем единственное решение $k= 8,d =7$ .

Ответ:

$X = {1,8,15,22,29,36,43,50}$

Ошибка.
Попробуйте повторить позже

Задача 4#80748

У вредного Васи есть клетчатая полоска длины 13 клеток и лента длины $N≥ 13$ клеток, каждая шириной в одну клетку. Вася хочет разрезать полоску на кусочки произвольной длины из нескольких целых клеток по своему усмотрению, а затем уложить часть из них на ленту в некотором порядке так, чтобы в какой-то момент осталось не менее одного кусочка, ни один из которых уложить уже нельзя. При этом кусочки укладываются строго по клеткам и не могут выходить за пределы ленты, ни одна клетка не должна быть накрыта ими дважды и, если на ленте есть место, куда можно уложить очередной кусочек, Вася должен уложить его в одно из таких мест по своему выбору. При каком минимальном N, как бы Вася ни старался, ему не удастся задуманное, то есть придётся уложить все кусочки?

Источники: Всесиб-2024, 11.5 (см. sesc.nsu.ru)

Подсказки к задаче

Подсказка 1

Давайте попробуем себе немножко упростить задачу и посмотреть на финальный шаг, когда Вася не может уложить ни один из своих кусков, можно ли как-то без ограничения общности заменить их?

Подсказка 2

Да, давайте скажем, что в конце у Васи остался ровно 1 кусок длины x, и он положил до этого k отрезков. Давайте тогда попробуем как-то оценить N, интуитивно должно казаться, что длина каждого из k кусочков должна быть как можно меньше, и они должны выступать в качестве ограничителей для нашего кусочка x.

Подсказка 3

Если всё ещё не получается получить оценку, то не расстраивайтесь и подумайте, какое наибольшее расстояние может быть между двумя соседними кусочками, чтобы между ними не поместился кусок x, а сколько таких промежутков, куда можно в теории положить x (не забудьте, что лента по краям тоже ограничена), а также не забудьте про сами k кусочков, они тоже занимают место на ленте.

Подсказка 4

Мы получили, что N ≤ (x-1)(k+1) + (13-x) ≤ 48, остаётся только придумать пример, когда N=48 (потому что для меньших свойство о непокрываемости), и радоваться решённой задаче!

Показать ответ и решение

Заметим, что если в какой-то ход Васи осталось больше одного кусочка, а оставшиеся поместить нельзя, то можно рассмотреть разрезание, где все эти кусочки объединяются в один, а другие выкладываются на ленту тем же образом. Понятно, что такой кусок-склейка также не будет помещаться.

Значит, можно без ограничения общности предположить, что у Васи должен остаться ровно один кусок, который нельзя поместить. Пусть его длина $x$ , а количество положенных кусочков равно $k$ . Тогда $x+ k≤ 13$ , при этом длина полосы $N ≤ (x − 1)⋅(k+1)+ 13− x$ , так как $13 − x$ - количество клеточек занятых остальными кусочками, а $k+ 1$ - количество ’зазоров’, в которые теоретически мы могли поместить кусок длины $x$ , но он не поместился, так как размеры зазоров не превосходят $(x− 1)$ .

Тогда Вася достигает своей цели при

N ≤(x− 1)⋅(k+ 1)+13− x≤ (x− 1)⋅(14− x)+ 13− x =

= −x2+ 14x− 1≤ −72+ 14⋅7− 1 =48

То есть если $N ≥ 49$ , то Вася не сможет выполнить задуманное.

А при $N < 49$ Васе достаточно разрезать полоску на $6$ кусков размера $1$ и $1$ кусок размера $7$ , при этом расположить $6$ кусков размера $1$ он должен на расстояний не более $6$ клеток друг от друга и от концов. (Чего он сможет достичь, так как $N ≤ 6⋅7+ 6$ )

Ответ: 49

Ошибка.
Попробуйте повторить позже

Задача 5#68024

На одной стороне каждой из 100 карточек написали одно из натуральных чисел от 1 до 100 включительно (каждое число записано ровно на одной карточке), после чего перевернули их обратными сторонами вверх и разложили в произвольном порядке на столе. За один вопрос Вася может указать на две любые карточки, после чего получает от ведущего ответ, являются ли записанные на них числа соседними (отличающимися на 1). За какое минимальное число вопросов Вася может гарантированно назвать хотя бы одну пару карточек, на которых написаны соседние числа?

Источники: Всесиб-2023, 11.5 (см. sesc.nsu.ru)

Подсказки к задаче

Подсказка 1

Поймём, что эта задача на оценку + пример! Чтобы придумать пример, подумайте о том, сколько соседей у каждого числа от 1 до 100.

Подсказка 2

Да, у каждого числа от 2 до 99 включительно — два соседа, а у чисел 1 и 100 — один сосед! Тогда можно увидеть алгоритм: задавать вопросы про одну и ту же карточку, постоянно меняю другую карточку. Какой ответ даёт этот алгоритм?

Подсказка 3

Верно, при таких действиях за 98 вопросов мы точно сможем назвать соседние числа! Осталось доказать, что за меньшее число вопросов доказать нельзя. Для этого нужно подумать о задаче в терминах теории графов. Тогда карточки — это вершины, а вопросы — это ребра! Что нужно найти в графе, чтобы доказать, что 98 — искомый ответ на задачу?

Подсказка 4

Да, надо найти Гамильтонов путь (такой путь, в котором каждая вершина встречается ровно один раз) по всем вершинам в графе, в котором ни одно ребро не является ребром, которое появилось вследствие вопроса Васи! Попробуйте посмотреть на задачу при малых n и доказать это утверждение по индукции!

Подсказка 5

База индукция тривиальна, поэтому давайте сразу подумаем о переходе! Такс, а что если посмотреть на вершину из которой выходит ровно одно ребро? А что будет в графе без неё? Можно ли в нём построить нужный нам путь?

Подсказка 6

Да. если есть такая вершина, то задача легко решается по индукции, ведь мы всегда можем переходить от случая с n вершинами к n+1 вершине с помощью добавления одного нужного нам ребра! Но вот незадача: что если нет вершин, из которых ихходит ровно одно ребро?

Подсказка 7

А если нет вершин с степенью 1, то можно точно утверждать, что есть хотя бы две вершины со степенью 0. Остаётся посмотреть на две этих вершин и еще одну вершину степень которой хотя бы 2!

Показать ответ и решение

Пример. Пусть Вася выберет какую-то карточку $A$ и задаст $98$ вопросов, в каждом из которых он спросит про $A$ и одну из $99$ карточек, отличных от $A.$ Общее количество чисел, не соседних с числом, написанным на $A$ не превосходит $98,$ если на $A$ написано $1$ или $100,$ и $97,$ если на $A$ написаны числа от $2$ до $99.$ Тогда либо в одном из $98$ ответов будет дан положительный ответ, и Вася нашёл нужную пару соседних чисел, либо все эти карточки содержат числа, не соседние с числом на $A.$ Следовательно, оставшаяся карточка содержит число, соседнее с числом на $A.$ Таким образом, Васе достаточно $98$ вопросов.

Оценка. Докажем, что, если Вася задаст всего $97$ любых вопросов, он может не найти ни одной пары карточек с соседними числами. Предположим противное, что задав некоторые $97$ вопросов он смог точно указать на пару карточек с соседними числами. Переведём задачу на язык теории графов. Карточки будем считать вершинами графа $G,$ а заданные Васей вопросы – рёбрами $G$ (синими рёбрами), соединяющими соответствующие пары карточек. К этим рёбрам нужно добавить ещё одно, соответствующее той паре карточек, на которых написана пара соседних, по версии Васи, чисел. Теперь нужно доказать, что вершины $G$ могут быть занумерованы в таком порядке, что ни одно ребро не соединяет две вершины с соседними номерами. То есть, нужно дорисовать в графе путь из $99$ рёбер, проходящий последовательно по всем $100$ вершинам, и не содержащих ни одного из $98$ «Васиного» синего ребра. Это будет означать, что Васина догадка не верна. Назовём такой путь красным и будем строить его методом математической индукции по числу вершин графа $G.$

Предположим, что в любом графе с числом вершин $n≤ 99,$ в котором проведено не больше $n − 2$ синих рёбер, существует красный путь $P$ по всем вершинам, не содержащий синих рёбер. Построим красный путь в $G.$

1) Пусть в $G$ есть «крайняя» вершина $V,$ из которой выходит ровно одно ребро $e.$ В графе $G1,$ полученном из $G$ удалением вершины $v$ и ребра $e$ число вершин равно $99,$ а рёбер – не больше $97,$ выполнено предположение индукции, поэтому в $G1$ можно построить красный путь длины $98$ с началом в вершине $a$ и концом в вершине $b.$ Тогда ребро $e$ не соединяет вершину $v$ с одной из $a$ или $b,$ проведя красное ребро из $v$ в эту вершину, получим красный путь длины $99$ в $G.$

2) Пусть в $G$ нет вершин, из которых выходит ровно одно ребро. В таком случае все синие рёбра инцидентны в сумме $196$ вершинам степени не меньше $2$ каждая, следовательно, среди них не больше $98$ различных. Следовательно, в $G$ не меньше двух вершин $u,v$ из которых не выходит ни одного синего ребра. Удалим из $G$ вершины $u,v$ и два ребра, выходящие из некоторой четвёртой вершины $s$ (но не саму вершину). Полученный граф $G1$ снова удовлетворяет предположению индукции и в нём можно построить красный путь длины $97$ с началом в вершине $a$ и концом в вершине $b.$ Если он не проходит через $s,$ или проходит, но не проходит через удалённые рёбра, соединим $a$ с $u$ и $b$ с $v$ и получим красный путь в $G$ длины 99. В оставшихся случаях, обозначим за $x$ и $y$ вторые концы удалённых рёбер. Если красный путь в $G1$ проходит через $x,s,y,$ заменим этот фрагмент на $x,u,s,v,y.$ Если он проходит только через одно удалённое ребро, скажем, через $x,s,$ заменим его на $x,u,v s.$ В обоих случаях получится красный путь в $G.$

База индукции - случаи графов с 3 и 4 вершинами - очевидна.

Ответ: 98

Ошибка.
Попробуйте повторить позже

Задача 6#71446

Перестановка чисел $1,2,3,...,n$ в некотором порядке называется забавной, если в ней каждое число, начиная со второго слева, либо больше всех чисел, стоящих левее него, либо меньше всех чисел, стоящих левее него. Например, перестановка $3,2,1,4,5,6$ является забавной, а перестановка $3,1,2,4,5,6$ — нет. Найти количество всех различных забавных перестановок чисел $1,2,3,..,n.$

Источники: Всесиб-2022, 11.3 (см. sesc.nsu.ru)

Подсказки к задаче

Подсказка 1

Если собирать последовательности с первого элемента, то будет трудно...но можно пойти с конца! Сколько есть вариантов для последней позиции?

Подсказка 2

Всего 2!(какие?). Теперь мы можем выбирать предпоследнюю цифру, но ведь она связана с последней? Какие тогда комбинации последних двух цифр могут быть?

Подсказка 3

(n-1, n), (1, n), (2, 1), (n, 1). Интересно, было 2 варианта, стало 4...попробуем обобщить наши рассуждения. Подумаем, как выглядят первые k чисел при любом k от 1 до n.

Показать ответ и решение

Пойдём с конца. Последнее число $a n$ забавной перестановки либо больше, либо меньше всех чисел множества $1,2,3,..,n,$ следовательно, оно равно 1 или $n.$ Предпоследнее число $an−1$ забавной перестановки либо больше, либо меньше всех чисел множества $1,2,3,...,n,$ кроме $an,$ то есть это наименьший или наибольший элемент во множестве $1,2,3,...,n− 1$ или во множестве $2,3,...,n.$ В каждом из случаев есть ровно две возможности выбора, варианты для двух последних чисел перестановки выглядят так $(n − 1,n),(1,n),(2,1),(n,1).$ Несложно убедиться, что при любом $k =n,n− 1,...,2,1$ первые $k$ чисел $a1,a2,...,ak$ перестановки образуют интервал из $k$ подряд идущих чисел из множества $1,2,3,...,n,$ а число $ak$ является в этом интервале минимальным или максимальным — всего две возможности, кроме самого первого числа $a1,$ для которого остаётся единственная возможность. Всего получаем ровно $n−1 2$ возможностей выбора.

Ответ:

$2n−1$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#80611

В некоторых клетках прямоугольной доски размера $101$ на $99$ сидят по одной черепашке. Каждую минуту каждая из них одновременно переползает в одну из клеток доски, соседнюю с той, в которой они находятся, по стороне. При этом, каждый следующий ход делается ими в направлении, перпендикулярном предыдущему: если предыдущий ход был горизонтальным — налево или направо, то следующий будет вертикальным — вверх или вниз, и наоборот. Какое максимальное количество черепашек может перемещаться по доске неограниченное время так, что в каждый момент в каждой клетке будет находиться не более одной черепашки?

Источники: Всесиб - 2021, 11.5 (см. sesc.nsu.ru)

Подсказки к задаче

Подсказка 1

Задачка на оценку+пример, попробуем тогда сначала придумать какой-нибудь пример, а дальше, отталкиваясь от него, догадаться до оценки! Какие мы можем придумать простейшие траектории черепашек, удовлетворяющие условиям задачи?

Подсказка 2

Самое простое, что можно придумать — заставить черепашек двигаться по циклам в квадратах 2*2. Сколько тогда двигающихся по таким траекториям черепашек мы можем разместить на поле?

Подсказка 3

После того, как мы придумали пример, переходим к оценке. По условию черепашки при каждом шаге поворачивают на 90 градусов. Тогда на каком поле относительно начального черепашка окажется после одного шага, двух шагов? Исходя из этих соображений, как можно покрасить поле так, чтобы у движения черепашки были удобные ограничения относительно этой раскраски?

Подсказка 4

Поле можно раскрасить в 4 цвета “в горошек”, и из-за того, что длины сторон поля нечётные, количество клеток разных цветов не будет одинаковым. А черепашка двигается по этой раскраске так, что обязательно проходит по циклу все 4 цвета. Осталось лишь посчитать количество клеток разных цветов и из этого получить оценку!

Показать ответ и решение

Сначала покажем, что $9800$ черепашек могут так перемещаться. Выделим в верхнем левом углу прямоугольник $100 ×98.$ Поставим в каждую его клетку по черепашке. Разобьем его на квадратики $2× 2.$ И пусть в каждом квадратике черепашки перемещаются по циклу против часовой стрелки. Тогда все черепашки всегда смогут сделать ход.

Докажем, что большего количества черепашек быть не может. Раскрасим нашу доску в $4$ цвета в горошек (в первой строке чередуются цвета $1$ и $2,$ во второй — $4$ и $3,$ в третьей — снова $1$ и $2,$ и так далее). Заметим, что клеточек цвета $4$ ровно $100⋅98 4 = 2450.$ Рассмотрим клеточки второго цвета. Заметим, что все черепашки на клеточках второго цвета через $2$ хода попадут в клеточки четвертого цвета. Тогда в данный момент черепашек на клеточках второго цвета не больше, чем черепашек на клеточках четвертого цвета, то есть также не больше, чем $2450.$ Нам осталось оценить сверху количество черепашек, стоящих в данный момент на клеточках первого и третьего цвета. Чтобы это сделать, достаточно подождать один ход, тогда все эти черепашки попадут на клеточки второго и четвертого цвета. А затем проделать те же самые рассуждения. То есть всего черепашек действительно не больше, чем $2450⋅4= 9800.$

Ответ:

$100⋅98= 9800$

Ошибка.
Попробуйте повторить позже

Задача 8#105719

В каждой клетке таблицы $3 ×3$ записано некоторое целое число так, что все восемь сумм троек чисел, записанных в клетках каждой строки, каждого столбца и каждой из двух диагоналей, равны одному числу $S$ (то есть таблица является магическим квадратом $3× 3).$ Докажите, что $S$ делится на $3.$

Подсказки к задаче

Подсказка 1:

Глобальная идея задачи такая: нужно найти какой-то набор клеток, посчитать сумму чисел в них двумя способами, приравнять и получить требуемое.

Подсказка 2:

Исходя из контекста понятно, что скорее всего этот набор будет состоять из каких-то строк, столбцов, диагоналей.

Подсказка 3:

Попробуйте подобрать их так, чтобы объединение строк, столбцов и диагоналей из этого набора представляло из себя весь квадрат.

Показать доказательство

Обозначим сумму чисел в каждой строке, каждом столбце и обеих диагоналях за $S.$ Рассмотрим сумму чисел в четырёх из рассматриваемых в условии троек: второй строки, второго столбца и двух диагоналей. Она равна с одной стороны $4S,$ а с другой — сумме всех чисел таблицы плюс утроенное число в центральной клетке. Сумма всех чисел таблицы равна $3S,$ поэтому $S$ равно утроенному числу в центральной клетке, то есть делится на $3.$

Ошибка.
Попробуйте повторить позже

Задача 9#74742

На доске $10× 10$ часть клеток отмечена, причём никакие три отмеченные клетки не образуют уголок. Доказать, что доску можно разбить на домино из двух соседних по стороне клеток, содержащие не более одной отмеченной клетки каждое.

Источники: Всесиб-2020, 10.4

Показать доказательство

Разобьём доску $10× 10$ на квадратики $2 ×2$ клетки. Ввиду того, что никакие три отмеченные клетки не образуют трёхклеточный уголок, каждый такой квадратик содержит не более двух отмеченных клеток. Если две отмеченные в нём клетки — соседние по стороне, то разобьём его на два домино линией сетки, содержащей эту сторону. В случаях, когда в квадратике отмеченные клетки не соседние, или их не больше одной, разбиваем его на домино произвольным способом, скажем, на горизонтальные. Разбив указанным образом каждый квадратик, получим разбиение доски $10×10$ на домино, содержащие не более одной отмеченной клетки каждое.

Ошибка.
Попробуйте повторить позже

Задача 10#108047

За одну операцию к любой из нескольких лежащих на столе кучек камней можно прибавлять столько же, сколько в ней уже содержится, из любой другой. Доказать, что любая начальная раскладка N камней по кучкам может быть собрана в одной куче в результате некоторого количества операций тогда и только тогда, когда N является степенью двойки.

Источники: Всесиб-2020, 11.5 (см. sesc.nsu.ru)

Подсказки к задаче

Подсказка 1

Хочется найти что-то, что в процессе меняется каким-то понятным образом, то есть полуинвариант.

Подсказка 2

Учитывая, что за операцию можно удалить количество камней в куче, возникает логичная мысль: следить за степенью вхождения двойки в количество камней в каждой куче.

Подсказка 3

Что можно сказать про степени вхождения двойки в куче A и B, если сделали операцию: переложили из A в B? Могла ли какая-то из степеней уменьшиться? Могла так случиться, что никакая из степеней не увеличилась?

Подсказка 4

Итак, пусть количество камней — степень двойки. Обратите внимание на количество кучек с минимальной степенью вхождения двойки. Какова чётность этого количества изначально и как она меняется в процессе?

Подсказка 5

Пусть теперь количество камней N = 2^t(2k+1). Предположим, что камни можно сложить в одну кучу. Попробуйте проделать операции в обратном порядке. Поищите противоречие, связанное с делимостью.

Показать доказательство

Для каждой кучки назовём её показателем максимальную степень двойки, на которую делится число содержащихся в ней камней, она может быть равна $0 1 =2$ . Рассмотрим поведение показателей кучек, участвующих в перекладывании. После перекладывания камней из кучки с $a 2 (2k+1)$ камнями в кучку с $b 2 (2l+ 1)$ камнями в первой остаётся $a b 2 (2k +1)− 2(2l+1)$ камней, а во второй становится $b+1 2 (2l+1)$ камней. Если $a= b$ , то

a b a+1 2 (2k+ 1)− 2 (2l+ 1)=2 (k− l),

поэтому оба показателя возрастут. Если $a⁄= b$ , то

a b c 2 (2k+ 1)− 2(2l+ 1)= 2(2m+ 1),

где $c =min{a,b}$ . При этом минимальный в данной паре кучек показатель сохраняется, а второй гарантированно становится больше минимального. Заметим, что количество кучек с минимальным среди всех показателем при произвольном перекладывании либо уменьшается на 2, либо не меняется.

Рассмотрим произвольную раскладку $N = 2t$ камней по более, чем одной кучке. В ней число кучек с минимальным показателем $2s,s<t$ будет чётным. Действительно, общее число камней $N = 2t$ и сумма количеств камней в не минимальных кучках делятся на $2s+1$ поэтому сумма количеств камней в минимальных кучках тоже делится на $2s+1$ , значит, их количество делится на 2. Если в раскладке есть хотя бы две кучки, разбиваем все кучки с минимальным показателем на пары, выполняем в каждой перекладывание из большей в меньшую и получаем раскладку с большим минимальным показателем, чем рассматриваемая. Проделав эту процедуру не более, чем $t$ раз, получим раскладку с минимальным показателем $t$ , то есть с единственной кучкой из $t 2 = N$ камней.

Пусть теперь $t N = 2(2k +1),k ≥1$ не является степенью двойки. Рассмотрим любой процесс сборки некоторой раскладки N камней по кучкам в одну и произведём его в обратном порядке, посредством процедур перекладывания, обратных к исходным, когда половина одной из кучек перекладывается в другую. При этом в обратном процессе количество камней в первой кучке (она же последняя в исходном процессе сборки) и всех получающихся на каждом шаге будет делиться на нечётное число $2k+ 1$ . Следовательно, любая раскладка, в которой есть кучка из числа камней, не делящегося на $2k+ 1$ , не может быть собрана в одной кучке. В частности, не может быть собрана в одну раскладка ${1, N − 1}$ по двум кучкам.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. В случае $N =2t(2k +1)$ можно предложить другое решение того, что раскладка ${1, N− 1}$ по двум кучкам не может быть собрана в одну. Этого достаточно для доказательства необходимости в условии задачи, то есть того, что любая начальная раскладка N камней по кучкам может быть собрана в одной куче только тогда, когда N является степенью двойки.

Докажем по индукции, что после $k$ перекладываний количества камней в кучках имеют вид

{ } 2k− ak⋅N,(ak+ 1)⋅N − 2k

для некоторого целого числа $ak ≥0$ .

База индукции при $k = 0$ очевидна:

{1,N − 1}= {z0 − 0⋅N,1⋅N − 20},

то есть $a0 = 0$ .

Шаг индукции: либо мы перекладываем камни из правой кучки в левую, тогда в левой станет $2k+1 − 2akN$ , а в правой останется $(2ak+ 1)N − 2k+1$ камней, при этом $ak+1 = 2ak$ , либо мы перекладываем камни из левой кучки в правую, тогда в левой останется $2k+1− (2ak+ 1)N$ , а в правой станет $2(ak +1)N − 2k+1$ камней, при этом $ak+1 = 2ak+ 1$ .

Если после некоторого $k$ -ого перекладывания раскладки ${1, N − 1}$ останется всего одна кучка, то число камней в другой станет равным 0 , следовательно, выполнится равенство одно из равенств $2k− ak⋅N =0$ или $(ak+ 1)⋅N − 2k =0$ . В обоих случаях N будет делителем числа $2k$ , то есть тоже степенью двойки противоречие с тем, что в рассматриваемом случае $N = 2t(2k+ 1)$ . Следовательно, при любом N , отличном от степени двойки, раскладка ${1, N$ $1}$ не может быть собрана в одну кучку.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Объединяя оба случая $N = 2t$ и $N = 2t(2k +1)$ , получаем доказательство более общего утверждения: раскладка N камней может быть собрана в одной кучке тогда и только тогда, когда количество камней в каждой её кучке делится на набольший нечётный делитель N .

Ошибка.
Попробуйте повторить позже

Задача 11#85754

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

Подсказки к задаче

Подсказка 1

Часто полезно рассматривать что-то крайнее. Выберете какой-нибудь параметр и исследуйте его.

Подсказка 2

Рассмотрите вершину из которой выходит наибольшее количество одноцветных ребер. Посмотрите на связи между соседями этой вершины.

Показать доказательство

Рассмотрим вершину $A,$ из которой выходит наибольшее количество одноцветных рёбер. Пусть они $1$ цвета. Пусть соединена первых цветом с $A1,A2,...,Ax.$ Рассмотрим оставшиеся $n− x− 1$ вершину, с которыми $A$ соединена другими цветами. Любая из этих вершин соединена со всеми $Ai$ либо первым цветом, либо тем же цветом, которым она соединена с $A.$ Однако заметим, что между $A$ и вершинами, отличными от $Ai$ может быть не более $n− 2− x$ рёбер первого цвета, поскольку есть $x$ рёбер $AAi.$ Но, как мы выяснили ранее, имеется $n− x− 1 >n − 2 − x$ вершина, не соединённая с $A$ первым цветом. Значит, среди них есть одна вершина $X$ такая, что цвет всех рёбер $XAi$ совпадает с цветом ребра $XA.$ Но тогда из $X$ выходит $x +1$ одноцветное ребро, это противоречит выбору $A.$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#88677

Дядя Андрей и девочка Маша играют в игру. У них имеются две упаковки сока по $24$ литра: один грушёвый, другой вишнёвый. Кроме того, у Андрея есть кружка в $500$ мл, а у Маши — две кружки по $240$ мл. Игроки пьют сок по очереди по следующим правилам: они наполняют все свои кружки до краёв, а затем выпивают налитое до дна. При этом запрещается смешивать два вида сока в одной ёмкости. Если кто-то не может сделать ход, то ходит его соперник. Игра заканчивается, когда никто не может сделать ход. Побеждает тот, кто выпил больше сока. Может ли кто-либо обеспечить себе победу, если Андрей выбирает, кто ходит первым?

Подсказки к задаче

Подсказка 1

Какой-то непривычный вопрос в задачке, да? Получается, что помимо победы Андрея или Маши еще могло быть, что никто из них не выиграл? Если так, то и Андрей, и Маша должны налить себе одинаково сока. Хм, емкости Маши меньше Андрея, но Маша может сделать больше ходов (за счет двух кружек). Непонятно, может ли кто-то гарантировать победу, но наверняка и Андрей, и Маша могут выпить примерно половину всего сока. Начнем разбираться с Андреем (его ходы более простые). Сколько литров он точно успеет выпить, пока может ходить? Вдруг он выиграет независимо стратегии?

Подсказка 2

Заметим, что объемы всех емкостей кратны 20 мл. Значит, если в упаковках <500 мл сока, то в них не более 480 мл сока. Тогда Андрей заведомо успеет сделать (48 000 - 960) / 980 = 48 ходов (За 1 ход Маши и 1 ход Андрея они выпивают 980 мл). То есть Андрей явно не проигравший - выпил ровно половину всего сока. Правда, Маша тоже могла выпить 24 литра сока суммарно. Хм, вариант ничьи всё более вероятен? Разбираемся с Машей. Выбор первого игрока за Андреем, поэтому может ли Маша набрать 24 литра сока в обоих случаях (за первого и второго игрока)? Стратегия с использованием симметрии или дополнения хода может помочь одному из игроков (как думаете кому именно?:))

Подсказка 3

Теперь можно уверенно сказать, что Маша тоже может не проиграть. Пусть она всегда пьет тот же сок, что и Андрей. То есть на пару за ход они выпивают 980 мл из одной упаковки. А если Маша ходит первой, то пусть она первым ходом выпьет по 240 мл из каждой упаковки. Сколько в обоих случаях будет сока в упаковках, когда Андрей не сможет ходить? Поймите, почему Маша выпьет 24 л и тоже не проиграет.

Показать ответ и решение

Докажем, что Андрей может выпить $24$ литра сока, как бы ни действовала Маша, и покажем, что Маша может ходить так, что тоже выпьет $24$ литра.

Предположим, Андрей выпил менее $24$ литров, то есть смог сделать не более $47$ ходов. Тогда Маша сделала не более $49$ ходов. Значит, на данный момент выпито не более $47⋅500+49⋅480= 47020,$ то есть не выпито хотя бы $980$ мл сока.

С другой стороны, так как объёмы всех ёмкостей делятся на $20,$ то и количество оставшегося сока в каждой упаковке делится на $20.$ Если Андрей не может сделать ход, то оно не превосходит $480$ мл в каждой упаковке, но тогда сока осталось не более $960$ мл. Значит, Андрей при любых обстоятельствах сможет сделать $48$ ходов.

Докажем, что Маша тоже может выпить $24$ литра сока, как бы ни действовал Андрей. Пусть Маша ходит второй и наполняет оба стакана тем же соком, что и Андрей в свой ход. Тогда за одну пару ходов они выпивают $980$ мл из упаковки, и после $24$ ходов в этой упаковке останется $480$ мл сока, которые Андрей выпить не может, а Маша может. За $24$ хода Маша выпивала на каждом на $20$ мл меньше, чем Андрей, т.е. в итоге выпила на $480$ меньше, что компенсирует, допивая последнее из этой пачки. Таким образом, если она ходит второй, то может выпить по крайней мере половину всего.

Если она ходит первой, то пусть первым ходом выпивает из каждой пачки по $240$ мл, а затем повторяет ходы. Аналогичными рассуждениями, в каждой пачке в конце остаётся $240$ мл (если в какой-то больше, то Андрей пока ещё ходит туда), что Маша допьёт и компенсируем разницу в выпитом до нуля.

Значит, никто не может обеспечить себе победу.

Ответ:

Нет, не может.

Ошибка.
Попробуйте повторить позже

Задача 13#68082

Трое играют в настольный теннис, причём игрок, проигравший партию, уступает место игроку, не участвовавшему в ней. В итоге оказалось, что первый игрок сыграл $21$ партию, а второй $10.$ Сколько партий сыграл третий игрок?

Источники: Всесиб - 2017, 10.2(см. sesc.nsu.ru)

Показать ответ и решение

По условию первый игрок сыграл $21$ партию, поэтому всего было сыграно не менее $21$ партии. Из каждых двух партий подряд второй игрок хотя бы в одной должен участвовать, значит, партий было не более $2⋅10+1 =21.$ Следовательно, была сыграна всего $21$ партия, и второй игрок участвовал в каждой из них. В $10$ партиях он встречался с первым, а в оставшихся $11$ партиях — с третьим. Пример такого турнира: первый игрок встречается со вторым в партиях с чётными номерами, а с третьим – в партиях с нечётными номерами.

Ответ: 11

Критерии оценки

Если ответ угадан и приведѐн пример турнира: 1 балл.

Присутствует замечание, что из каждых двух партий подряд второй игрок хотя бы в одной должен участвовать: 2 балла.

Не приведѐн пример турнира: минус 1 балл.

Ошибка.
Попробуйте повторить позже

Задача 14#88463

Однажды Алексей и Данил играли в такую игру. Если на доске записано некоторое число $x,$ то его можно стереть, а вместо него записать $2x$ или $x− 1000.$ Проигрывает тот, кто получил число не больше $1000$ или не меньше $4000.$ Оба игрока стремятся победить. В какой-то момент ребята перестали играть. Кто проиграл, если первым числом было $2017?$

Подсказки к задаче

Подсказка 1

Попробуем понять, из каких чисел нельзя сделать ход. Если, например, число меньше 2000, но больше 1000, то можно его 1 раз умножить на 2 и получить число, между 2000 и 4000. А что можно сделать с числом, которое находится между 2000 и 4000?

Подсказка 2

Верно! Можно два раза вычесть 1000. Из какого числа тогда не получится сделать ход?

Подсказка 3

Конечно, только из числа 2000! А как доказать, что никто не мог получить 2000?

Показать ответ и решение

Если число меньше $2000,$ но больше $1000,$ то умножением на $2$ можно получить число, которое меньше $4000.$ Если число меньше $4000,$ но больше $2000,$ то вычитанием $1000$ (возможно, два раза) можно получить число между $1000$ и $2000.$ Таким образом, единственное число, из которого нельзя сделать ход — это $2000.$

Докажем, что $2000$ никто получить не мог. Заметим, что исходное число не делится на $5.$ Если мы умножаем его на $2$ или вычитаем из него $1000,$ то новое число снова не делится на $5.$

Таким образом, Алексей и Данила могли бы продолжать свою игру вечно и никто не проиграл.

Ответ:

Никто не проиграл

Ошибка.
Попробуйте повторить позже

Задача 15#96566

В каждой клетке таблицы $5 ×5$ записано по одной букве так, что в любой строке и в любом столбце не больше трёх различных букв. Какое наибольшее число различных букв может быть в такой таблице?

Показать ответ и решение

Если в каждой строке не больше двух различных букв, то общее их число не превосходит $10= 5⋅2$ . Далее можно считать, что в первой строке ровно три различных буквы. Если каждая из оставшихся строк имеет хотя бы одну общую букву с первой, то общее число букв не превосходит $3+ 4⋅2= 11$ . Пусть имеется строка, можно считать, вторая, в которой три различных буквы, отличных от букв первой строки. Тогда в каждом столбце кроме букв первой и второй строк может быть не более одной новой буквы, всего не более $3+ 3+ 5⋅1= 11$ .

Пример расстановки 11 различных букв: по главной диагонали таблицы из левого нижнего угла в правый верхний записаны первые пять различных букв, по соседней снизу диагонали — следующие четыре, в левом верхнем углу — десятая, а в остальных клетках — одиннадцатая буквы.

Ответ: 11

Ошибка.
Попробуйте повторить позже

Задача 16#70787

По координатной плоскости, стартуя в начале координат, прыгает кузнечик. Первый прыжок длины один см направлен вдоль оси $OX,$ каждый следующий прыжок на $1$ см длиннее предыдущего, и направлен перпендикулярно предыдущему в одну из двух сторон по его выбору. Сможет ли кузнечик после сотого прыжка оказаться в начале координат?

Подсказки к задаче

Подсказка 1

Давайте прочитаем ещё раз условие и поймём, что от нас вообще хотят в задаче. Нужно, чтобы кузнечик попрыгал и вернулся обратно. А что это значит, если вертикальные прыжки он тоже делает? Как можно переформулировать задачу?

Подсказка 2

Верно, кузнечик должен вернуться обратно на ось 0x. Причём заметим, что он делает в вертикальном направлении прыжки чётной длины. Тогда за чётностью напрямую тут смотреть особо не поможет, потому что никакого противоречия не будет. Тогда какой остаток удобнее всего рассмотреть с чётными числами? А сколько различных остатков будет?

Подсказка 3

Ага, здесь удобно смотреть на остатки при делении на 4. Заметим также, что их тут всего два различных — 25 остатков 2 и 25 остатков 0. Но число 0 делится на 4, тогда и сумма этих остатков должна делиться на 4. А так ли это? Поймите это, посмотрев на количество остатков 2, и получите противоречие. Победа!

Показать ответ и решение

Кузнечник делает прыжки длиной $1,3,...99$ вдоль оси $Ox,$ а длиной $2,4,...100$ — вдоль оси $Oy.$ Покажем, что по оси $Oy$ он не сможет попасть в $0,$ тогда и в начале координат он не окажется. Действительно, рассмотрим остатки прыжков по модулю $4$ — это $2,0,2,0,...2,0,$ то есть по $25$ нулей и двоек. Поскольку двоек нечётное количество, то при любой расстановке знаков получится число, дающее остаток $2$ при делении на $4,$ значит, кузнечик не сможет попасть в $0$ и не попадёт в начало координат.

Ответ:

Нет

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#94874

Квадрат разбили на $100$ прямоугольников девятью вертикальными и девятью горизонтальными прямыми (параллельными его сторонам). Среди этих прямоугольников оказалось ровно $9$ квадратов. Докажите, что среди них есть хотя бы два одинаковых.

Показать доказательство

Заметим, что если два квадрата из девяти находятся в одной горизонтальной строке, то они имеют одинаковую высоту, а будучи квадратами — и одинаковую ширину, так что в этом случае всё доказано. Аналогично в случае с вертикальным столбцом.

Рассмотрим случай, когда все квадраты находятся в разных строках и в разных столбцах, и докажем, почему данный случай невозможен.

Действительно, тогда квадраты попадают в девять столбцов из десяти и в девять строк из десяти, и остаётся одна свободная строка и один свободный столбец, но тогда прямоугольник, стоящий на пересечении ”свободной” строки и ”свободного” столбца, будет ещё одним, десятым квадратом. В самом деле, ширину свободного столбца можно найти, вычтя суммарную ширину девяти квадратов из ширины большого квадрата. Точно так же высота свободной строки равна разности высоты большого квадрата и суммы высот девяти квадратов, а высота любого квадрата равна его ширине. Но по условию десятого квадрата нет, так что третий случай невозможен.

Ошибка.
Попробуйте повторить позже

Задача 18#101081

В футбольном турнире участвовало $10$ команд, каждая из которых с каждой из остальных сыграла по одному матчу. По окончании турнира выяснилось, что для любой тройки команд найдутся две команды из этой тройки, набравших равное число очков в играх с командами из этой тройки. Докажите, что все команды можно разбить не более, чем на три подгруппы таких, что любые две команды из одной подгруппы сыграли между собой вничью. За выигрыш в футболе команда получает $3$ очка, за ничью — $1$ очко и за проигрыш — $0$ очков.

Показать доказательство

Рассмотрим некоторую команду $A.$ Поделим все остальные команды на три группы — те, кого команда $A$ выиграла, те, кому $A$ проиграла, и те, с кем у $A$ ничья(группы могут быть пустыми).

Возьмём две команды $B$ и $C$ из первой группы, если в этой группе не меньше двух команд. Пусть $B$ выиграла $C.$ Тогда в тройке команд $A,B$ и $C$ у $A$ 6 очков, у $B$ 3 очка, а у $C$ — 0, что противоречит условию о том, что для любой тройки команд найдутся две команды из этой тройки, набравшие равное число очков в играх с командами из этой тройки. Аналогично, команда $C$ не могла победить $B,$ то есть между $C$ и $B$ ничья. А так как $B$ и $C$ выбраны произвольно, то можно сделать вывод, что между любыми двумя командами из первой группы ничья.

Теперь возьмём две команды $D$ и $E$ из второй группы. Если $D$ выиграла $E,$ то у $A$ 0 очков, у $D$ 6 очков, а у $E$ — 3, что опять же противоречит условию. Таким образом, между любыми двумя командами из второй группы ничья.

Наконец, возьмём две команды $F$ и $G$ из третьей группы. Если $F$ выиграла $G,$ то у $A$ 2 очка, у $F$ 4 очка, а у $G$ — 1, что невозможно по условию. Получается, между любыми двумя командами из третьей группы ничья.

Разобьём команды на три подгруппы так, чтобы любые две команды из одной подгруппы сыграли между собой вничью: первая подгруппа это те, кого команда $A$ выиграла, вторая — те, кому $A$ проиграла, и третья — те, с кем $A$ сыграла в ничью и сама команда $A.$ Первая и вторая подгруппы могут быть пустыми, а значит, всего подгрупп не более трёх, и внутри каждой все команды сыграли вничью.

Ошибка.
Попробуйте повторить позже

Задача 19#38862

Докажите, что в любой компании из $13$ человек либо найдётся человек, знающий четырёх других, либо найдутся четверо, попарно не знакомых. Знакомства обоюдны — если А знает Б, то и Б знает А.

Источники: Всесиб-2015, 11.4 (см. sesc.nsu.ru)

Подсказки к задаче

Подсказка 1!

1) Хм, какие-то попарные знакомства, это же граф! Давайте посмотрим на условие с таким взглядом. Нам нужно найти вершину степени хотя бы 4...

Подсказка 2!

2) Давайте попробуем идти от противного! То есть мы хотим попробовать из того, что степени всех вершин меньше трех, получить, что тогда есть независимое множество!

Подсказка 3!

3) Может рассмотрим первого человека и посмотрим, сколько тогда с ним незнакомых, поищем независимое множество там..

Показать ответ и решение

Будем говорить в терминах графа — либо найдётся вершина степени хотя бы $4$ , либо независимое множество размера $4$ . Пусть степень каждой вершины не больше $3$ . Выберем человека $A$ , он не знаком хотя бы с $9$ другими, поэтому достаточно найти независимое множество размера $3$ на них. Теперь выберем произвольную вершину $B$ из этих $9$ . Она соединена не более, чем с тремя из них, потому достаточно показать, что среди оставшихся $5$ найдутся две, между которыми нет ребра, что очевидно, поскольку любая из них имеет степень меньше $4$ , то есть в качестве $C$ берём любую из пяти, а в качестве $D$ ту, с которой $C$ не знаком.

Ответ:

что и требовалось доказать

Ошибка.
Попробуйте повторить позже

Задача 20#38863

Докажите, что среди пяти произвольных различных вершин правильного (все стороны и все углы которого равны) $15$ -и угольника всегда найдутся три, являющихся вершинами равнобедренного треугольника.

Подсказки к задаче

Подсказка 1!

1) Нам нужно найти равнобедренный треугольник в правильном многоугольнике. А равнобедренный треугольник означает, что мы хотим найти два равных отрезка с общей вершиной. Вершин пять. А сколько у нас всего отрезков будет?

Подсказка 2!

2) Да, 10! Теперь осталось посмотреть, сколько среди них может быть отрезков разной длины! Смотрите, если бы отрезков одной длины было хотя бы 3, мы бы смогли что-то сказать? А если только по два отрезка равной длины для всех длин?

Подсказка 3!

3) Это уже сложнее. Всего в 15-угольнике у нас 7 вариантов для длины отрезка. Сколько в таком случае у нас разных длин, если каждой длины по два отрезка?

Подсказка 4!

4) Верно, 3! А теперь давайте посмотрим на эти отрезки немного иначе. Если у нас нет треугольника, то будет 4 вершины, которые составляют эти две пары равных отрезков, образуют четырехугольник с равными сторонами или диагоналями. Осталось рассмотреть возможность существования в нашей фигуре подобного четырехугольника.

Показать доказательство

Каждой паре выбранных точек соответствует длина отрезка, их соединяющего, которая может принимать $7$ различных значений (длины диагоналей или стороны). Всего пар $2 C5 = 10$ . Если равны длины каких-то трёх отрезков, то по принципу Дирихле у каких-то двух есть общая точка, они и образуют равнобедренный треугольник.

Далее рассмотрим более сложный случай, то есть есть не более двух отрезков для каждой длины. Отсюда следует, что пар с равной длиной будет хотя бы $3$ . Если в какой-то паре отрезки совпали по одной из вершин, то мы нашли нужный треугольник, потому считаем, что в каждой паре отрезков все четыре вершины различны, то есть образуют четырёхугольник, в котором равны либо две стороны, либо диагонали.

Заметим, что обе пары сторон равны быть не могут, поскольку тогда мы бы получили прямоугольник, а в $15$ -угольнике не может быть диагонали-диаметра. Отсюда следует, что в четырёхугольнике не более двух пар равных отрезков, одной из которых будут диагонали. Однако пары равных отрезков три, потому есть два различных четырёхугольника, которые пересекаются по трём точкам (всего точек $5$ ).

Заметим, что каждый четырёхугольник является равнобедренной трапецией, в которой диагональ является наибольшим отрезком. При выборе любых трёх точек диагональ будет одним (наибольшим) из отрезков полученного треугольника, потому диагонали трапеций равны. Но тогда они образуют три равных отрезка из первого пункта, поскольку обе диагонали различных четырёхугольников не могут совпадать.