Popov AcademyУсловие
На окружности отмечены различных точек, одна выделена. Рассматриваются все выпуклые многоугольники, вершины которых выбраны из отмеченных точек. Каких больше: имеющих выделенную точку своей вершиной или не имеющих? На сколько? У многоугольника не меньше трёх вершин.
О задаче · Продвинутый уровень · школьники и взрослые
Записать идеюЕсть запись
Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.
Черновик не сохраняется: текст только в этой вкладке.
Черновик изменён в другой вкладке. Твой текущий текст пока сохранён здесь, автоматическая запись остановлена.
Подсказка 1
К каждому многоугольнику без выделенной вершины добавьте её. Можно ли восстановить исходный многоугольник?
Подсказка 2
Какие многоугольники с выделенной вершиной нельзя получить этим способом?
Разобрать решение по шагам
Создайте соответствие вместо большого подсчёта
Возьмём любой многоугольник без выделенной точки и добавим её к множеству вершин, расположив их по порядку на окружности. Получается выпуклый многоугольник с выделенной вершиной и хотя бы четырьмя вершинами. На окружности никакие три различные точки не коллинеарны, поэтому вырождения нет.
Проверьте обратимость
Из любого многоугольника с выделенной вершиной и хотя бы четырьмя вершинами можно удалить выделенную точку. Останется хотя бы три вершины, то есть допустимый многоугольник без неё. Добавление и удаление взаимно обратны. Эти две большие группы имеют одинаковое количество элементов.
Посчитайте только непарный остаток
В группе с выделенной вершиной остаются ещё все треугольники с ней. Две другие вершины выбираются из точек. Для первой есть вариантов, для второй — . Так каждая пара учтена дважды: сначала одна точка, потом другая и наоборот. Разделим число упорядоченных выборов на два:
Поэтому многоугольников с выделенной вершиной ровно на больше.
Ответ
С выделенной вершиной больше на многоугольников.
Главная идея
Чтобы сравнить две огромные группы, попробуйте сопоставить их элементы попарно и посчитать лишь остаток.
Как заметить эту идею в другой задаче
Нужно сравнить количества объектов с отмеченным элементом и без него. Попробуйте добавлять или удалять отметку, а затем отдельно посчитайте объекты, которым пары не хватает.
Возможная ошибка
Удалять выделенную вершину у треугольника и считать оставшийся отрезок многоугольником.
Источник и примечания
Источник и редакция
А. В. Спивак. «Тысяча и одна задача по математике. 5–7 классы», 2002. С. 120, № 775 (уточнена разность количеств). Условие пересказано, объяснение и дополнительное упражнение подготовлены для сайта.
Проверь себя
Проверьте результат для пяти точек на окружности: сколько многоугольников в каждой группе?
Ответ к дополнительной задаче
С выделенной вершиной : шесть треугольников, четыре четырёхугольника и один пятиугольник. Без неё : четыре треугольника и один четырёхугольник. Разность — число способов выбрать две точки из остальных четырёх.
Тема, знания и приёмы
Подсчёт вариантов · Нужна школьная база
- Подмножества конечного множества
- Вершины многоугольника
Приёмы решения: Симметрия и попарное соответствие