Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Применение классических комбинаторных методов к разным задачам

Тема КОМБИНАТОРИКА

Применение классических комбинаторных методов к разным задачам → .03 Двойной подсчёт

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

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

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

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

Подтемы раздела комбинаторика

Разделы подтемы Применение классических комбинаторных методов к разным задачам

Вероятностный метод (усреднение)

Индукция в комбинаторике

Дискретная непрерывность

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

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

Задача 61#95760Максимум баллов за задание: 7

Из $60$ четырехугольников составили кольцо (см. рис.). В вершинах четырёхугольников записали по целому числу, а на каждой стороне записали сумму чисел в её концах. Могло ли случиться так, что в вершинах и на сторонах в итоге были записаны в точности по разу числа $1,2,3,...,300?$

$PIC$

Источники: Лига открытий - 2018

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

Общая сумма на сторонах должна быть равна утроенной сумме в вершинах. Тогда сумма всех чисел должна быть равна учетверенной сумме в вершинах. Однако $1+ 2+...+300$ не кратно $4.$

Ответ:

Нет

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

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

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

Задача 62#99840Максимум баллов за задание: 7

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

Источники: Лига открытий - 2018

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

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

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

Задача 63#92720Максимум баллов за задание: 7

Вдоль прямолинейной дороги стоят $30$ столбов на одинаковом расстоянии. Грибник вышел из леса в некоторой точке на дороге. Оказалось, что сумма расстояний от грибника до всех столбов равна $3600$ метрам. Какое наибольшее возможное расстояние между столбами?

Источники: Лига открытий - 2017

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

Оценка. Пусть расстояние между столбами равно $x$ метров. Разделим все столбы на пары первый–последний, второй–предпоследний, и так далее. Получим всего $15$ пар. Рассмотрим первую пару. Так как столбы в ней расположены друг от друга на расстоянии $29x,$ то и сумма расстояний от грибника до этих двух столбов не меньше $29x.$ Продолжая эти рассуждения для следующих пар, получим, что сумма расстояний от грибника до всех столбов не меньше $2 29x +27x+ ...+ x= 15x.$ С другой стороны, по условию эта сумма расстояний равна $3600$ метрам, то есть $x$ не больше $3600 :225= 16$ метров.

Пример на $16$ метров получается, если грибник выйдет между $15$ -м и $16$ -м столбами. В таком случае во всех неравенствах выше достигается равенство.

Ответ:

$16$ метров

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

Задача 64#116309Максимум баллов за задание: 7

В одном интернет-сообществе каждый из участников имеет ровно $22$ друга (дружба обоюдная). При этом если два члена сети дружат, то у них нет общих друзей, а если не дружат, то у них ровно $6$ общих друзей. Сколько человек в этом интернет-сообществе?

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

Пусть в сообществе $N$ людей. Подсчитаем число упорядоченных троек $a− b− c$ , в которых $b$ дружит с $a$ и $c.$

Зафиксируем $b$ (это можно сделать $N$ способами). Тогда для него получится $22⋅21= 462$ таких троек. Итого получается $462N.$

С другой стороны можно сначала выбрать $a− N$ способов, потом $c− N − 23$ способа (нужно вычесть его друзей и его самого). Тогда $b$ можно выбрать 6 способами, итого $6N(N − 23).$

Получим уравнение $462N = 6N(N − 23),$ откуда $N = 100.$

Ответ: 100

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

Задача 65#73162Максимум баллов за задание: 7

Назовем множество $M$ точек на плоскости сбалансированным, если для любых точек $A,B ∈M$ существует точка $P ∈M$ , равноудаленная от $A$ и $B$ . Множество точек назовем хаотичным, если ни для каких трех точек $A,B,C ∈M$ не существует точки $P ∈M$ такой, что $PA = PB =P C$ . При каких натуральных $n$ существует сбалансированное, хаотичное множество из $n$ точек?

Источники: IMO shortlist - 2015, C2

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

Подсказка 1

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

Подсказка 2

Оказывается, что при нечетных n существуют. Постарайтесь для начала придумать пример, поищите сначала красивые конструкции.

Подсказка 3

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

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

Для нечетных $n$ достаточно отметить на окружности $n$ точек, образующих правильный $n$ угольник. Предположим, что для некоторого четного $n$ существует сбалансированное, хаотичное множество. Тогда для каждой из $2 C n$ пар точек существует равноудаленная от них точка из $M.$ Более того, одна такая точка может «обслуживать» не более $n−-2 2$ пар (так как множество хаотичное). Тогда всего точек в $M$ не меньше, чем $-C2n-> n n− 2$ — противоречие.

Ответ:

Для нечётных $n ≥3$

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

Задача 66#77984Максимум баллов за задание: 7

На плоскости проведено $102$ прямых и отмечены все точки их пересечения. Может ли на какой-нибудь окружности оказаться ровно $105$ отмеченных точек?

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

Подсказка 1

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

Подсказка 2

С одной стороны каждая прямая пересекает окружность максимум в двух точках => всего точек будет не более 204, с другой стороны каждую точку мы посчитали как минимум 2 раза (так как это точки пересечения прямых).

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

Пусть на какой-либо окружности $ω$ лежит $N$ точек пересечения. Тогда каждая прямая пересекает $ω$ не более чем в двух точках. При этом каждую отмеченную точку мы считаем по крайней мере $2$ раза, так как через нее проходят две (а может быть и больше) прямые. И из этого следует, что $N ≤ 102.$

Итак, ни на какой окружности не может быть больше $102$ точек пересечения. Для полноты картины отметим, что если проведенные прямые суть стороны $102$ -угольника, вписанного в окружность $ω,$ то $N = 102.$

Ответ:

Не может

Курсы

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

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

Задача 67#80614Максимум баллов за задание: 7

В стране $2000$ городов. Каждый город связан беспосадочными двусторонними авиалиниями с некоторыми другими городами, причём для каждого города число исходящих из него авиалиний есть степень двойки (то есть $1,2,4,8,...$ ). Для каждого города $A$ статистик подсчитал количество маршрутов, имеющих не более одной пересадки, связывающих $A$ с другими городами, а затем просуммировал полученные результаты по всем $2000$ городам. У него получилось $100000.$ Докажите, что статистик ошибся.

Источники: Всеросс., 2000, РЭ, 11.8(см. math.ru)

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

Подсказка 1:

Глобальная идея задачи такая: нужно обозначить через 2^{n_i} количество авиалиний, выходящих из i-го города, посчитать суммарное количество авиалиний и показать, что оно не может быть 100 000.

Подсказка 2:

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

Подсказка 3:

Если степень вершины x, то x маршрутов с одной авиалинией и x(x - 1) с двумя. Если не понимаете, почему так, то сначала обязательно разберитесь.

Подсказка 4:

Итак, теперь вы поняли, что количество авиалиний равно сумме 4^{n_i} по всем i от 1 до 2000. Осталось показать, что оно не может равняться 100 000. Теория чисел в помощь.

Подсказка 5:

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

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

Назовём беспосадочный перелёт из одного города в другой коротким маршрутом, а перелёт из одного города в другой с одной пересадкой в пути длинным маршрутом. Перенумеруем города и обозначим через $ni 2$ $(i=1,...,2000)$ число рейсов, выходящих из $i$ -го города.

Будем учитывать короткие маршруты в их конечных пунктах, а длинные — в пунктах пересадки. Тогда, если из города выходит $x$ авиалиний, то в нём будет учтено $x$ коротких маршрутов и $x(x− 1)$ длинных (так как из каждого смежного города через данный проходит $x− 1$ длинных маршрутов), а всего — $2 x+ x(x − 1)= x$ маршрутов. Таким образом, общее число маршрутов равно

22n1 + ...+ 22n2000 =4n1 + ...+ 4n2000

Поскольку $4$ в любой степени при делении на $3$ дает остаток $1,$ то остаток от деления на $3$ у общего числа маршрутов такой же, как у числа $2000,$ то есть $2,$ а у числа $100000$ этот остаток равен $1.$

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

Задача 68#125775Максимум баллов за задание: 7

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

Источники: Всеросс, ОЭ, 1997, 9.5 (см. math.ru)

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

Пусть сумма чисел в наборе равна $M,$ тогда число $a$ из набора заменяется на число $b= M − a.$ Просуммируем эти равенства для всех $a$ :

b1+...+b1997 = 1997M − (a1 +...+a1997),

откуда $M = 0,$ так как

b1+ ...+ b1997 =a1+ ...+ a1997 = M.

Выходит, что набор не изменится, если каждое его число заменить на противоположное. Значит, для любого числа $a,$ входящего в набор, число $b= −a$ также входит в набор, и все числа разбиваются на пары $(a,−a).$ Из нечётности их количества следует, что в набор входит число $a= −a,$ то есть $a= 0.$

Предыдущая подтема

Следующая подтема