BdMO National 2013: Higher Secondary 10

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
BdMO
Posts:134
Joined:Tue Jan 18, 2011 1:31 pm
BdMO National 2013: Higher Secondary 10

Unread post by BdMO » Fri Jan 10, 2014 1:45 am

$X$ is a set of $n$ elements. $P_m(X)$ is the set of all $m$ element subsets (i.e. subsets that contain exactly $m$ elements) of $X$. Suppose $P_m(X)$ has $k$ elements. Prove that the elements of $P_m(X)$ can be ordered in a sequence $A_1, A_2,...A_i,...A_k$ such that it satisfies the two conditions:
(A) each element of $P_m(X)$ occurs exactly once in the sequence,
(B) for any $i$ such that $0<i<k$, the size of the set $A_i \cap A_{i+1}$ is $m-1$.

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: BdMO National 2013: Higher Secondary 10

Unread post by *Mahi* » Mon Jan 20, 2014 4:03 pm

First, we will prove a lemma.

$\color{DarkGreen}{ \text{Lemma :}}$ For any sequence of subsets ${A_i}$, if we swap all the occurrences of some element with another one, then if the sequence satisfied the property asked in the question before, it will satisfy the property in the question after swapping too.

The proof is quite straightforward, i.e $|A_i \cap A_j|$ doesn't change if we swap some two integers $x, y$ in range $1$ to $n$.

This lemma enables us to "rename"(or swap) some of the elements in a sequence while reserving the required property (A) and (B).

Now, we will approach the proof with induction on $n$, number of elements of $X$.

$\color{DarkGreen}{ \text{Induction step:}}$ After proving the statement for $1,2,3$, let us assume the statement is true for $n = k-1$, which is, for every $i \leq k$ such that $P_i(X)$ can be ordered according to the two rules stated in the problem. We will now prove it for $n = k$.

For some $m \leq k$, we will prove that we can order $P_m(X)$ in this way.
Set aside an element, let that be called the $k^{th}$ element. By our induction hypothesis we know that there is a way to order the $m$ element subsets of the $k-1$ element set and $m-1$ element subsets of the $k-1$ element set abiding by the rules. Let these sequences be $S_1$ and $S_2$. By our induction hypothesis, every consecutive sets of both $S_1$ and $S_2$ has $1$ element uncommon.
Now, rename the elements in $S_2$ such that all of the element of the first set of $S_2$ appears in the last set of $S_1$ (which is possible by our lemma), so now the intersection of those two sets has cardinality $m-1$. Now, add the $k^{th}$ element in every set of $S_2$. So now, from $\binom {k-1}{m-1}$ sets in $S_2$, every consecutive set has $1$ element uncommon, and they all have $m$ elements. Also, between the last set of $S_1$ and first set of $S_2$, one element is uncommon, and finally, in $S_1$ we have total $\binom {k-1}{m}$ sets with one uncommon element in every pair of consecutive sets.

So, by joining $S_1$ and $S_2$ end to end now, we have a sequence of $\binom {k-1}{m} + \binom {k-1}{m-1} = \binom {k}{m}$ sets. In this sequence-
(A) Every set in $P_m(X)$ appears (as in the first $\binom {k-1}m$ sets all the subsets without the $k^{th}$ element appears, and in the rest of the sets, all the subsets with $k^{th}$ element appears.)
(B) Every consecutive set has one element uncommon (or $m-1$ elements common.)

So, this is a valid ordering for $P_m(X)$, and thus we can use this proof to all $m \leq k$ to prove our induction hypothesis for $n=k$.

So, by induction, this is proved for all $n \in \mathbb N$, i.e. the problem statement is proved for any set $X$ with $n$ element.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

Post Reply