Ломоносов, 2023, 7-8 класс, задача 2

Простая

Источник:

Олимпиада «Ломоносов», Отборочный этап, 2023, 7–8 классы

( баллов)

У каждого ученика в классе не менее друзей, причём не более учеников имеют одинаковое число друзей. Какое наименьшее число учеников может быть в классе?

Ответ

Ответ:

Решение. Нарисуем граф: ученики — это точки, ребро — дружба между учениками. Так как у каждого не менее друзей, то всего учеников хотя бы . Ровно учеников быть не может, так как тогда все вершины будут соединены со всеми, и у всех учеников будет поровну друзей, что противоречит условию. Значит, учеников хотя бы . Пример для — вершин, где каждая соединена с каждой, но одного ребра нет (получается учеников с друзьями у каждого и — с -ю).

Верный ответ

Максимум: 10

Похожие задачи

Ломоносов, 2023, 10 класс, задача 4; 11 класс, задача 4

(10 баллов) Четыре купца Арсений, Богдан, Вакула и Гаврила получили из казны 50 золотых червонцев. Они их решили разделить так, чтобы каждому досталось нечётное количество червонцев. Сколько есть разных способов дележа?

Простая

Комбинаторика

Ломоносов, 2020, 7–8 классы, задача 8; 9 класс, задача 9

(14 баллов — 7–8 классы; 12 баллов — 9 класс) Целеустремлённый паук хочет доползти до мухи, попавшей в его паутину (см. рисунок). При этом ползти он может только вверх и вправо по нитям паутины. Сколько есть различных способов у паука достигнуть свою цель? Паук и муха на паутине

Простая

Комбинаторика

Ломоносов, 2023, 7-8 класс, задача 3

(15 баллов) Карта Флатландии — прямоугольник, разбитый на губернии прямыми. Какое наибольшее число губерний может быть на карте, если проведены 2022 прямые?

Простая

Комбинаторика

Ломоносов, 2024, 9 класс, задача 7; 10 класс, задача 5

(15 баллов — 9 класс; 10 баллов — 10 класс) В ресторане «Обломов» выпекают 3 вида пирожков: с мясом, с рыбой, с грибами. Повар обратил внимание, что 25 ноября среди тех, кто заказывал по 4 пирожка, не повторился ни один набор пирожков. Какое максимальное количество посетителей «Обломова» могли заказ

Простая

Комбинаторика