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 common acquaintances 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.

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 common acquaintances at this meeting.
  • Is it possible that n can be greater than 2k?
Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

8 Comments

  1. Vladimir:

    >Prove that all the people have exactly the same number of common acquaintances at this meeting.
    Isn’t “common” superfluous?

  2. Tanya Khovanova:

    Thank you, Vladimir, “common” should be removed.

  3. Anon:

    Can you please post a solution?

  4. Tanya Khovanova:

    Anon,

    I will write a solution in a separate post.

  5. Aditya:

    Where can I find the solution?

  6. Reila:

    I don’t think it’s possible for graphs with odd vertices

  7. Vincent:

    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?

  8. Tanya 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 […]