Pigeonhole in Clubs

There are 2009 clubs, each with 45 members, any two of which have exactly one person in common. Show that there is one person who is a member of all the clubs.

(The problem and the first solution have been communicated to me by Prof. W. McWorter.)

Solution 1

(This solution is by Tadeusz Januszkiewicz in collaboration with Alexander Liebman.)

Suppose the assertion false.

  1. Each person belongs to at most 45 clubs.

    Take a person p and a club c to which p does not belong. Let Q be the set of clubs to which p does belong. c and every q in Q have exactly one member in common, cq. All these are distinct. For, if a = cq1 = cq2, then q1 and q2 contain both a and p. Thus, as c has 45 members, and cqi are all distinct, |Q| ≤ 45.

  2. Let c be a club, p1, ..., p45 its members, and C1, ...., Ck be the list of clubs (not including c) to which at least one of pi belongs.

    Step 1 shows that k ≤ 44 × 45 = 1980 < 2008.

    Thus there is a club which has no members in common with c, a contradiction.

Solution 2

Let's call a flower a configuration of clubs with a common member. Each club in a flower (less the common member) is a petal. Each petal contains 44 members and all members in all petals of a flower are different. The operation of forming a club by collecting a member per a petal of a flower is called deflowering.

If there exists a flower with 2009 petals we are done.

  1. Else, pick a club and consider its membership. 45 members of the club belong to 2008 other clubs, meaning (by pigeonhole) that there is a member that belongs to at least 2008/45 other clubs. Since the number of clubs one may belong to is an integer, there is (in fact in any club) a fellow who belongs to at least ⌈2008/45⌉ + 1 = 46 clubs. In other words, there exists a flower with at least 46 petals (and at most 2008 petals - by the assumption, meaning there is a club which is not a petal of the flower).

  2. Since all pairs of clubs have exactly one common member, all unaccounted for clubs are obtained by deflowering the given flower. Since the number of petals is greater than 45, deflowering leaves the petals whose members are not included in the so constructed club. To repeat, such petals have no common members with the club. A contradiction.

Solution 3

As one can see, the estimates obtained on step 1 in the two first solutions contradict each other. Thus combining the two steps yields another solution.

Related material

  • Pigeonhole Principle and Extensions
  • Twenty five boys and twenty five girls
  • Pigeonhole in Chess Training
  • Married Couples at a Party
  • Jumping Isn't Everything
  • Zeros and Nines
  • Teams In a Tournament
  • Divisibility of a Repunit
  • |Contact| |Front page| |Contents| |Up| |Store|

    Copyright © 1996-2017 Alexander Bogomolny


    Search by google: