For any three natural numbers p, r, n there exists a number N with the following property: If X is an arbitrary set with at least N elements and if $\binom{X}{p} = A_1 \cup A_2 \cup · · · \cup A_r$ is an arbitrary partition of the set of all p-tuples of elements of X, then there exists an n-element set Y ⊆ X such that $\binom{Y}{p}$ is completely contained in a single class $A_i$. (Hint: proceed by induction on p.)
I only need a slight nudge or hint. I've been stuck on this problem for three days now.
I have already proved the statement for $p=2$. So if I am not asking a lot let's assume it is true. Just as a hint, I proved it using induction on $r$. Additionally, it is trivially true for the case of $p=1$.
Here are some of my attempts.
In all of my attempts, I assume that $N$ is large enough.
Attempt number 1:
Take $a \in Y$ and consider the partition of the set $\binom{X - a}{p-1} = A^{'}_1 \cup A^{'}_2 \cup \cdots \cup A^{'}_r$. From the inductive hypothesis, for some $j$, $\binom{ Y -a}{p-1} \subset A^{'}_j$. Then I try to add $a$ back to $X$ and $Y$ but then I hit a wall.
Attempt number 2:
Consider the partition of the set $\binom{X}{p-1} = A^{'}_1 \cup A^{'}_2 \cup \cdots \cup A^{'}_r$. From the inductive hypothesis, for some $j$, $\binom{Y}{p-1} \subset A^{'}_{j}$. Although I am thinking of unionizing sets in $A^{'}_{j}$ which only intersect on one element to get $\binom{Y}{p}$ but that doesn't necessarily mean that $\binom{Y}{p}$ is completely contained in one of the classes of the partitions of $\binom{X}{p}$.
Attempt 3:
This is more of an extension of Attempt 1. I'll partition $\binom{X-a}{p-1}$ for all the elements of $Y$, i.e for all $a \in Y$. Let $m = |Y|$, then I get $A^{1}, A^{2}, ... , A^{m}$ sets which contain $\binom{Y - a_1}{p-1}, \binom{Y - a_2}{p-1}, ... , \binom{Y - a_m}{p-1}$. Then I was thinking of doing some diagonalization but I am not sure how to proceed. This method is the one that I investigated the least.
Throughout my attempts, I only assumed $N$ to be large but I didn't specify it nor give it a bound. There were moments, that I thought if only $N$ was large enough but it'd lead to a convincing argument because that's extent $N$ being large enough is investigated in my proofs.
Hope that gives you some idea what I am thinking in regards to this problem and my attempts so far. Any help would be appreciated!
Thank you for your time and feel free to suggest edits to make this more readable.
Here is a summary of steps of how I would do it. It is not unlike your "attempt number 1".
As suggested, we argue by induction on $p$, and suppose that $N$ is large enough. We suppose that the result holds for $p-1$, and show it for $p$. So consider $f$, an $r$-coloring of $\binom{X}{p}$. Since $X$ is finite, we can put a total order on it.
Let $z_1$ be the smallest element in $X$. Then $g_1(T)=f(\lbrace z_1 \rbrace\cup T)$ defines a $r$- coloring of $\binom{X-z_1}{p-1}$, so by the induction hypothesis there is a large $X_1\subseteq X-z_1$ such that all the $p$-sets of $\lbrace z_1 \rbrace \cup X_1$ containing $z_1$ have the same color, which we call $c_1$.
Let $z_2$ be the smallest element in $X_1$. Then $g_2(T)=f(\lbrace z_2 \rbrace\cup T)$ defines a $r$- coloring of $\binom{X_1-z_2}{p-1}$, so by the induction hypothesis there is a large $X_2\subseteq X_1-z_2$ such that all the $p$-sets of $\lbrace z_2 \rbrace \cup X_2$ containing $z_2$ have the same color, which we call $c_2$.
Continuing in this way by induction, we find a a large subset $Z$ such that the coloring induced on $\binom{Z}{p}$ only depends on the smallest element ; in other words it reduces to a coloring of $\binom{Z}{1}$ (the color of the $p$-set is the "color" of its smallest element) and then we can use the $p=1$ case (which is the pigeonhole principle).