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

Логика → .04 Учти лишнее

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

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

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

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

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

Разделы подтемы Логика

Строим пример

Невозможность определить гарантированно

Эффект +- 1

Учти лишнее

Много объектов и большие числа

Истинные и ложные высказывания

Утверждение о существование и построение отрицания к ним

Рассуждения от противного

Рыцари и лжецы

Мудрецы и фокусы

Принцип Дирихле

Оценка + пример

Круги Эйлера

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

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

Задача 1#33259

Сколько клеток содержится в квадратной рамке $14× 14$ шириной в $2$ клетки?

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

Добавим к этой рамке внутренний квадрат $10×10$ . Тогда мы получим целый квадрат $14× 14$ , и в нем $14⋅14= 196$ клеток. При этом мы добавили $10 ⋅10= 100$ клеток. Значит, в самой рамке содержится $196 − 100= 96$ клеток.

Ответ: 96

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

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

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

Задача 2#33260

У скольких трехзначных чисел произведение цифр делится на $3$ ?

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

Как мы знаем, всего трехзначных чисел $900$ . Вместо того, чтобы считать числа, у которых произведение цифр делится на $3$ , посчитаем те, у которых произведение цифр не делится на $3$ .

Произведение цифр числа не делится на $3$ , тогда и только тогда, когда в его записи не встречаются цифры $0$ , $3$ , $6$ и $9$ . Поэтому на каждое из трех мест мы можем поставить только одну из шести цифр: $1$ , $2$ , $4$ , $5$ , $7$ , $8$ . Применим правило умножения: при выборе очередной цифры количество способов ее выбрать не зависит от цифр, выбранных ранее, и всегда равно $6$ . Поэтому трехзначных чисел, произведение цифр которых не делится на $3$ , $6⋅6⋅6= 216$ .

Чтобы теперь узнать искомое количество чисел, достаточно вычесть найденные $216$ чисел из общего количества трехзначных чисел: $900− 216 =684$ , и именно у стольких трехзначных чисел произведение цифр делится на $3$ .

Ответ: 684

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

Задача 3#33261

Пастбище для гиппогрифов представляет из себя квадрат $10× 10$ километров. При этом каждый гиппогриф живет в отдельном огороженном забором загоне в форме прямоугольника $1×2$ километра (таким образом, всего в на пастбище обитают $50$ гиппогрифов). Какова суммарная длина внутренних заборов, ограждающих гиппогрифов друг от друга?

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

Проведем в каждом загоне $1× 2$ дополнительный забор, разделив его на две клетки $1× 1$ километра. Так как всего загонов $50$ штук, на это мы потратим лишних $50$ километров забора. Получим квадрат $10× 10$ , полностью разбитый на клетки $1× 1$ .

Теперь нетрудно посчитать суммарную длину внутренних заборов. Всего $9$ горизонтальных линий забора, каждая имеет длину $10$ километров. Получается $9⋅10= 90$ километров. Такую же длину имеют вертикальные заборы. Значит, суммарная длина заборов сейчас составляет $90⋅2= 180$ километров. Но здесь учтены лишние $50$ километров забора, которые мы добавили сами. Поэтому, чтобы посчитать исходную длину заборов, нужно из $180$ вычесть добавленные $50$ километров: $180− 50 =130$ километров.

Ответ: 130 км

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

Задача 4#33321

Сколько чисел от $1$ до $300$ не делится на $3$ ?

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

Посчитаем сначала, сколько среди данных чисел делящихся на $3$ . Их ровно треть, так как каждое третье число делится на $3$ , то есть $300:3= 100$ . Все остальные числа на 3 не делятся, и поэтому их количество равно $300− 100= 200$ .

Ответ: 200

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

Задача 5#33322

Совунья вырезала из прямоугольника $20× 30$ (20 столбцов, 30 строк) крест, в котором вертикальная полоска имеет ширину 3 клетки, а горизонтальная — 2 клетки. Сколько всего клеток в таком кресте?

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

Посчитаем, сколько всего клеток в вертикальной полосе. Так как строк в прямоугольнике 30, то высота вертикальной полоски равна 30 клеточкам, а ширина, по условию, равна 3 клеткам. Значит, в вертикальной полосе креста $30⋅3= 90$ клеток.

Далее, считаем, сколько всего клеток в горизонтальной полосе. Так как столбцов в прямоугольнике 20, то длина горизонтальной полоски равна 20 клеточкам, а ширина, по условию, равна 2 клеткам. Значит, в горизонтальной полосе креста $20⋅2= 40$ клеток.

При этом некоторые клетки были посчитаны как в вертикальной полосе, так и в горизонтальной, а именно все клетки на пересечении этих полос. Так как ширина вертикальной полоски равна 3 клеткам, а ширина горизонтальной — 2 клеткам, то прямоугольник на пересечении этих полос имеет размеры $3⋅2$ клеток, то есть состоит из $3 ⋅2 =6$ клеток. Именно эти 6 клеток мы и посчитали дважды. Поэтому, чтобы получить настоящее количество клеток в кресте, надо сложить полученные выше клетки и вычесть из них 6, посчитанных дважды. В итоге получается $90 +40− 6= 124$ клеток в кресте, вырезанном Совуньей.

Ответ: 124

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

Задача 6#33323

У Совуньи есть 8 одинаковых кубиков. На гранях каждого кубика написаны цифры от $1$ до $6$ по одному разу. Она собрала из этих $8$ кубиков куб $2× 2×2$ . Оказалось, что у кубиков, соприкасающихся гранью, на этой грани написано одно и то же число. Может ли сумма всех чисел, написанных на гранях большого куба $2×2 ×2$ , равняться $99$ ?

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

Сначала посчитаем сумму всех чисел на исходных $8$ кубиках. Сумма чисел на одном кубике равна $1+2 +3+ 4+ 5+ 6= 21$ , значит, сумма на всех восьми равна $21 ⋅8 =168$ .

Теперь посчитаем, на сколько меньше получится сумма на гранях большого куба $2× 2× 2$ . Как вообще могло получиться, что на большом кубе какого-то числа не оказалось? Такое возможно только тогда, когда число оказалось внутри, то есть грань, на которой написано число, соприкасается с гранью другого кубика, на котором также, по условию, написано это же число.

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

Ответ: Нет, не может

Курсы

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

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

Задача 7#39381

Два квадрата со стороной $10$ , пересекаясь, образуют квадрат со стороной $2$ . Чему равна площадь, которую они покрывают?

$PIC$

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

Площадь больших квадратов равна $100$ . Площадь маленького квадрата равна $4$ . Если сложить площади двух больших квадратов, то площадь маленького квадрата будет посчитана дважды. Значит, площадь, покрываемая этими двумя квадратами, равна $100+ 100− 4= 196$ .

Ответ: 196

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

Задача 8#39382

Треугольник с периметром $25$ см разделили на $4$ треугольника, как показано на рисунке. Периметры трёх треугольников у вершин равны $16$ см, $10$ см и $4$ см. Чему равен периметр центрального треугольника?

$PIC$

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

Сложим периметры трех маленьких треугольников, отмеченных серым на рисунке ниже. Полученное значение равно сумме периметров большого треугольника и белого треугольника. Значит, периметр белого треугольника равен периметру $16+ 4+ 10− 25= 30− 25= 5$ .

$PIC$

Ответ: 5

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

Задача 9#74585

Дан правильный $n$ -угольник $(n= 4k+ 2),$ в котором проведены все диагонали. Докажите, что они образуют не больше

n(n-− 1)(n-− 2)(n-− 3) n (n ) n (n ) ( n ) 24 − 4 ⋅ 2 − 1 + 1− 2 ⋅ 2 − 1 ⋅ 2 − 3

точек пересечения (не считая вершин).

Источники: ИТМО-2022, 11.7 (см. olymp.itmo.ru)

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

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

n(n− 1)(n− 2)(n− 3) --------24--------

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

Во-первых, поскольку количество вершин чётно, $n2$ "длинных"диагоналей (соединяющий противоположные вершины многоугольника) пересекаются в центре многоугольника. Эта точка посчитана

n (n ) 2-⋅-2 −-1 2

раз, в то время как должна быть посчитана 1 раз. Значит, из вычисленного количества надо вычесть

n ( n ) 2 ⋅-2 −-1-− 1 2

Во-вторых, для каждой "длинной"диагонали можно взять две симметричные относительно неё диагонали, не проходящие через центр многоугольника. "Длинную"диагональ можно выбрать $n 2$ способами. Для удобства представим себе, что выбранная диагональ расположена вертикально. По каждую сторону от этой диагонали остаётся $n 2 − 1$ вершина. Мы выбираем вершину $A$ слева от “длинной” диагонали, после чего для выбора вершины $B$ справа у нас остаётся $n 2 − 3$ варианта: мы не можем выбрать вершину, симметричную $A$ относительно "длинной"диагонали (иначе диагональ $AB$ будет симметрична сама себе) и вершину, симметричную относительно центра, иначе $AB$ будет "длинной а эти точки пересечения мы уже учли.

Симметричная диагональ $′ ′ A B$ выбирается единственным образом. Однако каждую пару диагоналей $AB$ и $′′ A B$ мы посчитали дважды, потому что в качестве первой выбранной диагонали могла быть взята любая из них. Таким образом, точку пересечения трёх диагоналей мы умеем искать

n (n ) ( n ) 2 ⋅ 2 − 1 ⋅ 2 − 3 --------2--------

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

n (n ) ( n ) 2 ⋅ 2 − 1 ⋅ 2 − 3

точек меньше.

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

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

Задача 10#63904

Найдите сумму всех натуральных чисел, не превосходящих 105, которые делятся на 3, но не делятся на 5.

Источники: ДВИ - 2020, вариант 201, задача 2 (pk.math.msu.ru)

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

Сначала возьмём все числа, кратные $3$ — это $3,6,9,...105$ . Их будет 35, а их сумма