Maximal Value of n n

Level pending

Let A = { a 1 , … , a n } A= \left \{a_1, \dots , a_n \right \} and S ( A ) S(A) be a set of some subsets D ⊂ A D \subset A such that

  • each subset D ∈ S ( A ) D \in S(A) contains at most n − 1 n-1 elements
  • each element of A A belongs to exactly 4 4 distinct subsets
  • any unordered pair of distinct elements a i , a j ∈ A a_i, a_j \in A belongs to exactly one subset D D .

Determine the maximal possible value of n n .


The answer is 13.

Atul Anand Sinha by Atul Anand Sinha , 23, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Atul Anand Sinha
Feb 8, 2014

Suppose that some subset D 0 ∈ S ( A ) D_0 \in S(A) contains more than 4 4 elements: D + 0 = { a 1 , … , a k } D+0=\left \{a_1,\dots ,a_k \right \} where k > 4 k > 4 .

Take any a k + 1 ∉ D 0 a_{k+1} \notin D_0 . Since any unordered pair of distinct elements belongs to exactly one subset, for each i = 1 , … , k i=1,\dots ,k , pairs ( a i , a k + 1 ) (a_i, a_{k+1}) belong to distinct subsets, and consequently a k + 1 a_{k+1} belongs to more than 4 4 subsets.

Contradiction shows that each subset D ∈ S ( A ) D \in S(A) contains at most 4 4 elements. Since a 1 a_1 belongs to exactly 4 4 subsets, the total number of elements of A A can not exceed 1 + 4 ⋅ 3 = 13 1+4\cdot 3=\boxed{13} .

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...