Consider the set $A=\{1,2,3,4,5,6,7,8,9\}$.A partition $\Pi $ of $A$ is collection of disjoint sets whose union is $A$

Question

Consider the set $A=\{1,2,3,4,5,6,7,8,9\}$.A partition $\Pi $ of $A$ is collection of disjoint sets whose union is $A$. For example, $\Pi_1=\{\{1,2\},\{3,4,5\},\{6,7,8,9\}\}$ and $\Pi _2 =\{\{1\},\{2,5\},\{3,7\},\{4,6,8,9\}\}$ can be considered as partitions of $A$. For, each $\Pi$ partition ,we consider the function $\pi$ defined on the elements of$A$. $\pi (x)$ denotes the cardinality of the subset in $\Pi$ which contains $x$. For, example in case of $\Pi_1$ , $\pi_1(1)=\pi_1(2)=2$, $\pi_1(3)=\pi_1(4)=\pi_1 (5)=3$, and $\pi_1(6)=\pi_1(7)=\pi_1(8)=\pi_1(9)=4$. For $\Pi_2$ we have $\pi_2(1)=1$, $\pi_2(2)=\pi_2(5)=2$, $\pi_2(3)=\pi_2(7)=2$ and $\pi_2(4) = \pi_2(6) = \pi_2(8) = \pi_2(9) = 4$ Given any two partitions $\Pi$ and $\Pi '$, show that there are two numbers $x$ and $y$ in $A$, such that $\pi(x)=\pi(y)$ and $\pi′(x)=\pi′(y)$.

Source: Mathematical Talent Reward Programme 2016

First of all in this question i haven't understood about the function. What are $\Pi_1$, $\Pi_2$, $\pi_1$ and $\pi_2$ ? What are the difference between them ? The given conditions are making the functions more complicated ? And also how to apprach the problem ?

I spent hours to understand in exam hall as well as in home for this but got nothing?

Answer 1

As pointed out in the comments, the likely correct condition is $ \pi (x) = \pi (y), \pi'(x) = \pi'(y)$.

---

Crux: Let $ \pi^l$ denote the elements whose subset in $ \Pi$ have exactly $l$ elements.

Show that

1. $\pi^l \neq \emptyset$ for at most 3 values of $l$.
2. $|\pi ^l|$ is a multiple of $l$.

This was hinted at in the partitions $\Pi_1, \Pi_2$.
Using the example in the problem, we have $\pi_2^1 = \{1\}, \pi_2^2 = \{2, 3, 5, 7 \}, \pi_2^4 =\{4, 6, 8, 9 \}$.

Suppose there are 4 sets with a distinct number of elements. Then $ 1 + 2 + 3 + 4 > 9$, hence a contradiction.

$|\pi^l| = $ number of subsets of size $l \times l$.

---

Suppose that such $ \Pi_1, \Pi_2$ exist where $ \left( \pi_1 (n), \pi_2(n) \right)$ are all distinct.

Let the image of $ \pi_2$ be $ \subset \{ i, j, k \}$. (From above, it has at most 3 elements.)

If $ | \pi_2^l |> 3$, then consider $\pi_1 (n) $ where $ n \in \pi_2^l$.
Since $\pi_1(n)$ takes on 3 values, by the pigeonhole principle, 2 of these are the same value, which is a contradiction.

Otherwise, we have $ |\pi^l | \leq 3$.
Since $ \sum |\pi^l| = 9$, hence we must have $ |\pi^i| = |\pi ^j | = |\pi^k| = 3$.
However, this is only possible if $\{ i, j, k \} \in \{ 1, 3 \}$, which is a contradiction.

Thus, such partitions do not exist.

---

Note: There is another approach that uses $ | \left\{ ( \pi_1 (n), \pi_2(n) )\right\}| \leq 3 \times 3 = 9$.
If it is 8 or fewer, pigeonhole works directly to give us the 2 elements with identical values.
If it is exactly 9, start doing casework, which ends up being very similar to the above. This was how I first did the problem, before rewriting the solution.