Question

В классе есть 28 ребят. Известно, что каждый подарил по одной конфете ровно k одноклассникам (самому себе конфету никто не дарил). При каком наименьшем значении k обязательно (как бы они друг другу ни дарили конфеты) найдутся двое ребят в классе, которые подарили конфеты друг другу? ​

Answer 1

Ответ:

14

Пошаговое объяснение:

Всего подарено 28*к конфет

Различных пар в классе 28*27/2 (учли, что Вася,Петя и Петя, Вася -одна пара)

При каком  наименьшем к  28*к  больше  14*27 ?

к=14

Answer 2

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

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

Если каждая вершина имеет исходящую степень k, то общее количество ребер в графе будет равно 28 * k. Так как каждое ребро соответствует подарку конфеты, то общее количество подарков конфет будет равно 28 * k.

Теперь мы можем использовать принцип Дирихле: если имеется n объектов, и они разделены между m контейнерами, где n > m, то как минимум один контейнер содержит более одного объекта.

В нашем случае у нас 28 детей и 28 * k подарков конфет. По принципу Дирихле, если количество подарков конфет (28 * k) больше, чем количество детей (28), то как минимум двое детей обязательно обменялись подарками конфет.

То есть, нам нужно найти минимальное значение k, при котором 28 * k > 28. Решим это неравенство:

28 * k > 28

Разделим обе части неравенства на 28:

k > 1

Таким образом, минимальное значение k, при котором обязательно найдутся двое детей, которые обменялись подарками конфет, равно 2.

Итак, при k = 2 обязательно найдутся двое детей, которые подарили конфеты друг другу, вне зависимости от того, как бы они друг другу ни дарили конфеты.