A hidden bijection in the two-office incidence problem

sleepyVivi·Aug 16, 2025(edited)

The condition reminds me of a projective plane, but I don't want to assume a classification theorem. Can the degree of Amr be forced directly from the unique-common-neighbor condition? Problem: A Saudi company has two offices. One office is located in Riyadh and the other in Jeddah. To insure the connection between the two offices, the company has designated from each office a number of correspondents so that (a) each pair of correspondents from the same office share exactly one common correspondent from the other office. (b) there are at least 10 correspondents from Riyadh. (c) Zayd, one of the correspondents from Jeddah, is in contact with exactly 8 correspondents from Riyadh. What is the minimum number of correspondents from Jeddah who are in contact with the correspondent Amr from Riyadh? Source: IMO selection problems, 2013 · MNET-0D2J

Open MNET-0D2J in the question bank →

4 replies

parry_this·Aug 16, 2025(edited)

For a nonadjacent opposite-office pair R,J, map each neighbor J' of R to the unique common neighbor of J and J'. This is a bijection between their neighbor sets: two preimages would give R and another vertex two common neighbors, and the reverse map comes from the common neighbor of R and each neighbor of J.

sleepyVivi·Aug 17, 2025(edited)

So if Amr isn't connected to Zayd, his degree is immediately 8. The connected case is the part I couldn't handle.

parry_this·Aug 17, 2025(edited)

Choose two Riyadh vertices R1,R2 not connected to Zayd; at least two exist. Both have degree 8. Among R1's eight neighbors, at most one is also connected to Amr, and at most one to R2. Choose J outside those at most two.

eevee.zip·Aug 17, 2025(edited)

Now J is nonadjacent to R2, so J has degree 8. It is also nonadjacent to Amr, so Amr has degree 8. This forces the value in either case. To establish attainability independently of the problem's assumed configuration, the projective plane over the field with seven elements gives an example.

Join the discussion

A hint, a different approach, or a thoughtful question can help.

Loading discussion…