Pigeonhole in 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, c∩q. All these are distinct. For, if a = c∩q₁ = c∩q₂, then q₁ and q₂ contain both a and p. Thus, as c has 45 members, and c∩q_i are all distinct, |Q| ≤ 45.

2. Let c be a club, p₁, ..., p₄₅ its members, and C₁, ...., C_k be the list of clubs (not including c) to which at least one of p_i 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.

|Contact| |Front page| |Contents| |Up|