A Problem from the Moscow Olympiad
Here is a problem from the 2012 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
commonacquaintances at this meeting.- Show that n can be greater than 4.
My question is: Why 4? I can answer that myself. If in a group of four people any two people share exactly two common acquaintances, then all four people know each other. So in this Olympiad problem, the author wanted students to invent a more intricate example.
Let’s take this up a notch and work on a more difficult problem.
Share: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
commonacquaintances at this meeting.- Is it possible that n can be greater than 2k?
Vladimir:
>Prove that all the people have exactly the same number of common acquaintances at this meeting.
12 May 2013, 11:54 amIsn’t “common” superfluous?
Tanya Khovanova:
Thank you, Vladimir, “common” should be removed.
12 May 2013, 4:07 pmAnon:
Can you please post a solution?
21 May 2013, 11:33 amTanya Khovanova:
Anon,
I will write a solution in a separate post.
28 May 2013, 12:40 pmAditya:
Where can I find the solution?
31 May 2013, 6:59 pmReila:
I don’t think it’s possible for graphs with odd vertices
30 June 2013, 9:12 pmVincent:
Hmmm an answer to part 2 of the origional question can be obtained by taking a piece of triangular grid paper, cutting out a parallellogram consisting of four rows of four dots, the lines between them and the closest half of every edge sticking out of it, and gluing the half edges together in the classic way to fold and glue a torus out of a parallellogram.
Now I wonder if we can solve part 2 of the general problem by replacing the A_2 lattice by an A_k lattice and rolling it into a k-torus. However I have a LOT of trouble visualizing this. Can anyone see if this works/why it doen’t work?
11 July 2013, 2:52 pmTanya Khovanova’s Math Blog » Blog Archive » Discussing a Problem from the Moscow Olympiad:
[…] 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 […]
28 July 2013, 8:09 am