Тема ПВГ (Покори Воробьёвы Горы)

Комбинаторика и логика на ПВГ

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

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

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

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

Подтемы раздела пвг (покори воробьёвы горы)

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

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

Задача 1#39648

На клетчатой бумаге нарисовали прямоугольный треугольник с катетами, равными $7$ клеткам (катеты идут по линиям сетки). Потом обвели все линии сетки, находящиеся внутри треугольника. Какое наибольшее количество треугольников можно найти на этом рисунке?

Источники: ПВГ-2017, 6.5 (см. pvg.mk.ru)

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

Подсказка 1

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

Подсказка 2

Верно, посмотрим на отрезки гипотенузы равные √2, их семь штук. Когда выберем какой-то такой отрезок, то и получится наш треугольник. Осталось тогда только понять, сколько таких отрезков различной длины будет?

Подсказка 3

Верно, единичных отрезков будет 7, длины 2 – 6 и так далее, осталось только сложить их.

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

Заметим, что треугольники здесь будут только прямоугольные с углом $45∘$ . Кроме того, их гипотенуза лежит на гипотенузе изначального треугольника, поскольку все остальные отрезки проходят только по линиям сетки. Заметим также, что положением гипотенузы задаётся весь треугольник, потому достаточно посчитать количество различных отрезков с концами в целых точках на отрезке длины $7$ (так получится, если уменьшить всю гипотенузу в $√- 2$ раз). Длины $1$ отрезков будет $7$ , длины $2$ — $6$ ,.. длины $7$ — $1$ . Итого имеем $7+ 6+ ...+ 1= 28$ различных треугольников.

Ответ:

$28$

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

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

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

Задача 2#36853

Футбольный мяч шьётся из $32$ кусочков кожи: белых шестиугольников и чёрных пятиугольников. Каждый чёрный кусочек граничит только с белыми кусочками, каждый белый кусочек граничит с тремя чёрными и тремя белыми. Сколько чёрных кусочков нужно для изготовления мяча?

Источники: ПВГ-2016, 11.2 (см. pvg.mk.ru)

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

Подсказка 1!

1) Итак, у нас в задаче есть многоугольники, которые друг с другом граничат, было бы удобно выбрать какую-то величину и считать ее с помощью условий...

Подсказка 2!

2) Так-так-так, у нас есть некоторая величина, например, количество границ черных и белых многоугольничков, про которую мы знаем и от белых многоугольников, и от черных... Что бы тут могло значить?

Подсказка 3!

3) Именно! Количество связей белых клеток с черными у нас считается с двух разных сторон! Это должно помочь...

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

Из условия получаем, что $x$ чёрных кусочков граничат суммарно с $5x$ белыми, соответственно $32 − x$ белых кусочков граничат с $3(32 − x)$ чёрными. То есть число границ между белыми и чёрными кусочками равно с одной стороны $5x,$ а с другой стороны $96− 3x.$ Отсюда находим, что $96 x= 8 = 12.$

Ответ:

$12$

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

Задача 3#82712

Из четырёх бегунов — Антона, Бориса, Виктора и Григория — второе место занял самый старший. При этом Антон пробежал дистанцию быстрее, чем Виктор, а Григорий — быстрее, чем Борис и Виктор. Известно также, что Борис старше Антона, а Виктор старше Григория. В каком порядке финишировали спортсмены?

Источники: ПВГ - 2015, 11.1 (rsr-olymp.ru)

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

Самым старшим может быть или Борис, или Виктор. Но Виктор не мог занять второе место, так как он уступил и Антону, и Григорию. Поэтому Борис — второй. Значит, Григорий — первый, Антон — третий, а Виктор четвертый.

Ответ: Григорий, Борис, Антон, Виктор

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

Задача 4#39430

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

Источники: ПВГ-2014 (см. pvg.mk.ru)

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

Подсказка 1

Поймем, что выбор, к примеру, вратаря, никак не влияет на выбор кого-либо другого(из другой группы) и наоборот. Что это значит? Как нам посчитать кол-во способов набрать одну группу?

Подсказка 2

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

Подсказка 3

Конечно, формула числа сочетаний. Осталось посчитать для каждой группы кол-во способов, потом перемножить это и получить ответ.

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

Выбор каждого вида игроков осуществляется независимо, поэтому количества способов нужно просто перемножить. Покажем, что число способов выбрать $k$ человек из $n$ подходящих на эту роль равно $k ---n!-- Cn =k!(n−k)!.$

Действительно, сначала рассмотрим все перестановки из $n$ человек (которых $n!$ ), будем брать в команду первых $k$ из них. Тогда нам не важен порядок этих $k$ человек, то есть нужно поделить на $k!$ , а также не важен порядок следующих за ними $n− k$ человек, то есть нужно поделить ещё на $(n− k)!$ . Что здесь означает не важен порядок? Если мы его изменим, то выбранная нами команда не поменяется.

В итоге мы показали, что способов $--n!-- k!⋅(n−k)!.$ Используя эту формулу для всех типов игроков и перемножая результаты, получаем

C12 ⋅C25 ⋅C38 = 2⋅10⋅56 =1120

Ответ: 1120

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

Задача 5#70307

У Игоря Горшкова есть все семь книг про Гарри Поттера. Сколькими способами Игорь может расставить эти семь томов на три различные книжные полки так, чтобы на каждой полке стояла хотя бы одна книга? (Расстановки, которые отличаются порядком книг на полке, считаются различными.)

Источники: ПВГ - 2014, 9 класс

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

Расставим книги в ряд $7!$ способами, так как все они различны. Чтобы распределить книги по трем полкам, поставим две перегородки между 7 шарами. Кол-во способов расставить перегородки: $6⋅5 2$ , итого $6⋅5 2 ⋅7!$

Ответ: 75600

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

Задача 6#34647

В школе было три урока. Но только $4$ школьника были на всех уроках. Каждый из остальных «учеников» присутствовал только на двух уроках, а один из уроков прогулял. На математике в классе было $17$ школьников, на физике — $18,$ на русском — $19.$ Сколько школьников присутствовало и на математике, и на физике? (не имеет значения, удостоили ли они своим посещением урок русского языка)

Источники: ПВГ-2012, 11.1 (см. pvg.mk.ru)

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

Подсказка 1

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

Подсказка 2

В пересечении всех трёх – 4 школьника, а вот изолированно на каждом круге – 0 школьников, то есть работаем мы только с областями на пересечении. Количества учеников в классе же показывает нам сумму чисел в трёх областях, а узнать нужно нам сумму чисел в двух. Попробуйте сначала определить общее количество учеников, потом вычесть из него подходящую тройку и получить количество учеников в любой удобной Вам области!

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

Заметим, что на математике, физике и русском было $13,14$ и $15$ «учеников» (прогульщиков) соответственно. Суммарно получается $42,$ но каждый «ученик» здесь посчитан дважды (потому что каждый из них посетил два предмета), то есть на самом деле их $21.$ А всего ребят в классе тогда $25.$ Получается, что на русский язык не пришли $6$ человек, зато они присутствовали и на физике, и на математике. Добавляя настоящих учеников (которым удалось не прогулять ни один предмет), получаем ответ.

Ответ: 10

Курсы

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

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

Задача 7#74088

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

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

1 подсказка

Непонятно, как работать с карандашами и коробкой. Попробуйте перевести задачу на математический язык.

2 подсказка

Давайте вместо карандашей рассмотрим числа, а вместо коробки - таблицу 2×6. Попробуйте теперь сформулировать эту задачу в новых терминах. Что вам напоминает эта формулировка?

3 подсказка

Если она ничего вам не напоминает, то вам стоит почитать про числа Каталана.

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

Заметим, что такая укладка карандашей соответствует таблице $2×6,$ куда мы ставим числа от $1$ до $12$ так, чтобы во всех столбцах и строках числа шли по возрастанию (таблица — это коробка, число — это номер карандаша по возрастанию длины: $1$ — самый короткий, $12$ — самый длинный). Данная формулировка задачи является одним из определений чисел Каталана и очень легко сопоставляется правильной скобочной последовательности: число — номер скобки, положение числа (в верхней строке или в нижней) — открытая это скобка или закрытая, соответственно.

Ответ:

$132$

Интенсивы

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

Предыдущий раздел

Следующий раздел