Discussing a Problem from the Moscow Olympiad

I recently posted the following problem from the Moscow Olympiad:

There were n people at a meeting. It appears that any two people at the meeting shared exactly two common acquaintances.

  • Prove that all the people have exactly the same number of acquaintances at this meeting.
  • Show that n can be greater than 4.

Here is the proof for the first bullet. Choose a person X. Take a pair of X‘s acquaintances. These two acquaintances have to share two acquaintances between themselves one of whom is X. In other words, we have described a function from all pairs of X‘s acquaintances to people who are not X. On the other hand, for every person who is not X, s/he and X share a pair of acquaintances. Hence, there is a bijection between people other than X and all pairs of X‘s acquaintances. If the number of X‘s acquaintances is a, and the total number of people is t, then we have shown that (a choose 2) = t−1. As this is true for any X, we see that everyone has the same number of acquaintances. Moreover, this situation can happen only if t−1 is a triangular number.

But wait. There is more work that needs to be done. The smallest triangular number is 1. That means that t might be 2. If there are two people at the meeting, then the condition holds: they have 0 common acquaintances. The next triangular number is 3. So we need to see what would happen if there are four people. In this case, if everyone knows each other, it works. This is why the second bullet asks us to find an example of the situation with more than four people, because four people is too easy.

Let’s look at larger triangular numbers. The situation described in the problem might also happen when there are:

  • 7 people total and everyone has 4 acquaintances,
  • 11 people total and everyone has 5 acquaintances,
  • 16 people total and everyone has 6 acquaintances,
  • and so on: a(a−1)/2 + 1 people total and everyone has a acquaintances.

The official Olympiad solution suggests the following example for 16 people total. Suppose we put 16 people in a square formation so that everyone knows people in the same row and column. I leave it to the reader to check that every two people share exactly two acquaintances.

Let me prove that there is no solution for a total of seven people. If there were a solution, then each person would have to know four people. My first claim is that the acquaintance graph can’t contain a four-clique. Suppose there is a four-clique. Then each person in the clique has to have another acquaintance outside of the clique to make it up to four. In addition, this extra acquaintance can’t be shared with anyone in the clique, because the clique contains all the acquaintances that they share. This means we need to have at least four more people.

Next, suppose two people a and b know each other and share an acquaintance c. Any two people in this group of three has to have another shared acquaintance, who is not shared with the third person. That is, there should be another person who is the acquaintance of a and b, a different person who is an acquaintance of a and c, and a third person who is acquainted with b and c. These three extra people are all the acquaintances of a, b, and c. Which means the last person who is not acquainted with a, b, or c, has less than for four acquaintances.

Let’s look at a more difficult problem that I offered at the same posting:

There were n people at a meeting. It appears that any k people at the meeting shared exactly k common acquaintances.

  • Prove that all the people have exactly the same number of acquaintances at this meeting.
  • Is it possible that n can be greater than 2k?

As in the previous solution, we see that a, the number of acquaintances of a person and t, the total number of people, satisfy the following equation: (a choose k) = (t−1 choose k−1).

For example, if k = 3, the equation becomes (a choose 3) = (t−1 choose 2). This is a question of finding numbers that are both tetrahedral and triangular. They are known and their sequence, A027568, is finite: 0, 1, 10, 120, 1540, 7140. The corresponding number of acquaintances is 3, 5, 10, 22, 36 and the total number of people is 3, 6, 17, 57, 121. The first trivial example involves 3 people who do not know each other. The next example is also simple: it has 6 people and everyone knows everyone else.

What about non-trivial examples? If there are 17 people in the group, then each person has to know 10 people. Does the acquaintance graph exist so that every group of three people share 3 acquaintances?

We see that the problem consists of two different parts. First, we have to solve the equation that equates two binomial coefficients. And second, we need to build the acquaintance graph. Both questions are difficult. We see that for k = 2 we have an infinite number of solutions to the equation with binomial coefficients. For k = 3, that number is finite. What happens with other k? If there are 2k people and they all know each other, then this works. But are there other non-trivial solutions? I am grateful to Henry Cohn for directing me to the works of Singmaster who studied non-trivial repetitions of numbers in Pascal’s triangle. In particular, Singmaster showed that the equation (n+1 choose k+1) = (n choose k+2) has infinitely many solutions given by n = F2i+2F2i+3−1 and k = F2iF2i+2−1.

This sequence generates the following non-trivial examples (15 choose 5) = (14 choose 6), (104 choose 39) = (103 choose 40), and so on. That means it might be possible that there is a group of 16 people so that every 6 people share 6 acquaintances. In this situation every person must know everyone else except for one other person. That leads us to the structure of the acquaintance graph: it is a complement to the perfect matching graph. I leave it to my readers to check that the corresponding acquaintance graph doesn’t exist. Are there examples of two binomial coefficients that equal each other and that lead to an acquaintance graph that can be built?

Now that I’ve tackled the solution to this Olympiad problem, I see that I generated more questions than I answered.

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

5 Comments

  1. Konstantin:

    Таня, можно, я по-русски, а Вы переведёте? “Нетривиальный” случай с 17 людьми и 10 знакомствами невозможен вот почему.
    Пусть люди – это строчки и столбцы в симметричной таблице 17×17, где в каждой строке ровно 10 единиц, а остальные – нули. Рассмотрим любую пару людей (например, строки 1 и 2) и попытаемся понять, сколько у них общих знакомых (т.е. сколько единиц, стоящих в их строках, у них ОБЩИЕ). Если в каком-то столбце для каждой из двух строк стоит 1, то в этом столбце еще 8 других единиц, и каждая такая единица должна быть сосчитана как общий знакомый для соответствующей тройки строк (иначе баланс не сойдётся). Итого если у 1 и 2 строк есть k общих единиц, то подсчеты по общим знакомым для этих двух строк должны дать в сумме 8k. С другой стороны, в компанию к 1 и 2 людям можно добавить любого из 15 остальных, и для каждого по условию мы должны выбрать ровно три “сосчитанных” столбца. Итого подсчёт столбцов для 1 и 2 строк должен дать в сумме 45. Поскольку 45 не кратно 8, то это невозможно.

    Общую теорему можно найти, например, здесь:
    http://en.wikipedia.org/wiki/Block_design#CITEREFCameronvan_Lint1991

  2. David Speyer:

    I decided to think about this problem (the original one) the other day, and I got a nice result: The only possible orders for such a graph are 4 and 16.

    Proof: Let A be the adjacency matrix of the graph. So $latex A^2$ is $latex a$ on the diagonal and 2 off the diagonal. So the eigenvalues of $latex A^2$ are $latex a-2$, with multiplicity $latex a(a-1)/2$, and $latex a^2$ with multiplicity 1. This means that the eigenvalues of $latex A$ are $latex pm sqrt{a-2}$ and $latex pm a$. In the latter case, only one of $latex a$ and $latex -a$ occurs, and it must be $latex a$ because the vector $latex (1,1,1,ldots,1)$ has eigenvalue $latex a$. In the former case, let $latex sqrt{a-2}$ have multiplicity $latex k_{+}$ and let $latex -sqrt{a-2}$ have multiplicity $latex k_{-}$.

    Since the diagonal entries of A are all zero, we have Tr(A)=0 and so $latex a + (k_{+}-k_{-}) sqrt{a-2}=0$. This shows that $latex sqrt{a-2}$ is rational, so let $latex a=m^2+2$. Then $latex m^2+2 + (k_{+} – k_{-}) m=0$. So $latex m$ divides $latex 2$ and is either $latex 1$ or $latex 2$. This corresponds to $latex a=3$ or $latex 6$, so a graph of order $latex 4$ or $latex 16$.

    There is a second solution for $latex 16$, other than the one you give. Let $latex omega$ be a primitive cube root of unity. Let $latex Lambda$ be lattice $latex mathbb{Z} oplus mathbb{Z} omega$. Make $latex Lambda$ into an infinite graph, where the neighbors of $latex z$ are $latex z pm 1$, $latex z pm omega$ and $latex z pm omega^2$. Quotient by the sublattice $latex 4 Lambda$. The quotient is a graph of order 16 with the required property. To see that it is not isomorphic to the official solution, take any vertex of G and look at the induced graph on the 6 vertices neighboring this vertex. In the official solution, the induced graph is the union of two triangles; here it is a hexagon.

    I have a case-bashing proof that these are the only two solutions, but it isn’t worth writing out.

  3. Tanya Khovanova:

    Konstantin provided a solution in Russian that 17 people do not work. The solution uses the counting of acquaintances of two people and three people. I will not translate it, as David’s explanation covers bigger territory.

  4. Vincent:

    The very elegant argument in your post showing that every person has the same number of acquaintances can be easlily extended to show that for every j smaller than k every set of j people have the same number of common acquaintances thus giving more equations. For k = 3 let b be the number of common acquaintances of two people. It seems to me that b choose 3 should be equal to t – 2 thus giving the following possible values for t: 3, 6, 12, 22, 37, 58, 86, 122, 167, … so there are some very near misses with the sequence from your post but we can conclude that there is only one solution for k = 3, the obvious case with 6 people.

  5. Tanya Khovanova:

    Vincent,

    Brilliant.