logoChat01.ai

Среди 28 человек некоторые − друзья. Но любые два ...

Created on: January 11, 2026

Answered using GPT-5.2 Thinking by Chat01

Question

Среди 28 человек некоторые − друзья. Но любые два человека, имеющие среди других одинаковое число друзей, между собой не дружат. Найдите максимальное возможное число разных пар друзей среди этих 28 человек.

Python

python
S = 27*1 + 26*2 + 25*3 + 24*4 + 23*5 + 22*6 + 21*7
S


644

Thought

Confirming edge count and optimization

The edge count of 322 matches the complete multipartite scenario exactly, which is interesting. This suggests we’ve likely hit the upper bound, given the constraints I’ve set. The approach of filling higher degrees first seems optimal, as the number of vertices aligns perfectly with the degree limits.

Examining degree class assignments

Since the sum of counts for max degrees up to d=21 totals exactly 28, filling according to this gives a degree sum of 644. If we lowered any degree below 21, we'd have to shift vertices, reducing S. I wonder if adjusting class sizes to exceed the caps would help, though the cap was derived from independence.

Validating upper bound limits

For degree 26 in a graph with n=28, it's clear that no more than 2 vertices can have a degree of 26 since they'd need to be nonadjacent to at least 2 vertices within their class. The strict capacity confirms that the upper bound of S is 644. To prove the upper bound, we need to show the degree distribution leads to a valid graphical construction.

Maximizing degree sum using constraints

To maximize the total degree sum, I need to show that the degree of each vertex, d_i, is less than or equal to 28 - i. This follows from the cap on multiplicities. By ordering the degrees in descending order and applying this constraint, I can solve the linear programming problem with optimal results.

Reasoning for maximum vertex degree and edge count

For a given degree d, the maximum number of vertices with that degree is 28 - d. This is because the vertices are nonadjacent, limiting their connections to vertices outside their set. To maximize the sum of degrees, we distribute as many vertices as possible to higher degrees. The total degree sum is 644, leading to 322 edges. Thus, the graph construction with 322 edges is possible.

Maximizing total edge number while respecting degree constraints

To maximize the total number of edges, I want to ensure that the number of vertices at each degree is chosen to saturate higher degrees. Since k_d ≤ 28 - d, I can calculate the maximum sum. For degrees 27, 26, etc., I carefully pick values for k_d to match these caps, ensuring that the sum of all k_d equals 28.

Maximizing degree sum and constructing optimal graph

To maximize the degree sum, I use a greedy approach to assign the largest possible degree to each vertex, respecting the constraints. By starting with the highest degree and working downward, I ensure that each degree appears as often as allowed, leading to the multiset that maximizes the sum at 644. The upper bound on edges is 322.

Thought for 3m 41s

Answer

Рассмотрим граф дружбы на n=28n=28 вершинах (ребро = дружба). Степень вершины = число друзей.

Условие: любые две вершины одинаковой степени не соединены ребром. Значит, все вершины одной и той же степени образуют независимое множество.

Пусть степень равна dd, и таких вершин kk. Тогда между ними нет рёбер, и каждая из этих kk вершин может дружить только с оставшимися 28−k28-k людьми. Поэтому

d≤28−k⇒k≤28−d.d \le 28-k \quad\Rightarrow\quad k \le 28-d.

То есть:

  • степень 2727 может быть максимум у 11 человека;
  • степень 2626 — максимум у 22 человек;
  • степень 2525 — максимум у 33 человек;
  • …
  • степень 2121 — максимум у 77 человек.

Заметим, что

1+2+3+4+5+6+7=28,1+2+3+4+5+6+7 = 28,

то есть можно “заполнить” всех 28 людей степенями 27,26,25,24,23,22,2127,26,25,24,23,22,21 в максимально допустимых количествах, и никакие степени ≤20\le 20 уже не понадобятся (любая замена одной из этих степеней на ≤20\le 20 только уменьшит суммарное число друзей).

Тогда максимальная возможная сумма степеней:

Smax⁡=27⋅1+26⋅2+25⋅3+24⋅4+23⋅5+22⋅6+21⋅7.S_{\max}=27\cdot1+26\cdot2+25\cdot3+24\cdot4+23\cdot5+22\cdot6+21\cdot7.

Посчитаем:

Smax⁡=27+52+75+96+115+132+147=644.S_{\max}=27+52+75+96+115+132+147=644.

Число рёбер (пар друзей) равно половине суммы степеней:

mmax⁡=6442=322.m_{\max}=\frac{644}{2}=322.

Достижимость. Разобьём 28 людей на 7 групп размеров 1,2,3,4,5,6,71,2,3,4,5,6,7. Дружат все люди из разных групп, а внутри каждой группы дружбы нет. Тогда человек из группы размера ss имеет 28−s28-s друзей, то есть степени ровно 27,26,25,24,23,22,2127,26,25,24,23,22,21, и люди одинаковой степени (внутри одной группы) не дружат — условие выполнено. Число рёбер:

(282)−∑s=17(s2)=378−(0+1+3+6+10+15+21)=378−56=322.\binom{28}{2}-\sum_{s=1}^7\binom{s}{2}=378-(0+1+3+6+10+15+21)=378-56=322.

Ответ: 322\boxed{322}.

Share this Q&A