View topic - Renewal of an old problem • Art of Problem Solving

Page 1 of 1

[ 5 posts ]

Author

Message

mavropnevma

Posts: 1281
Location: Bucharest
Canada

Posted: Sep 04, 2009, 11:07 am • # 1

I chose to revive this old problem of mine, due to the interesting links between other topics on these fora.

Theorem 1. Let $X$ be a set. Let $n$ and $m\geq 1$ be two nonnegative integers such that $\left\vert X\right\vert\geq m\left( n - 1\right) + 1$ . Let $B_{1}, B_{2}, ..., B_{n}$ be $n$ subsets of $X$ such that $\left\vert B_{i}\right\vert \leq m$ for every $i\in\left\{1,2,...,n\right\}$ . Then, there exists a subset $Y$ of $X$ such that $\left\vert Y\right\vert = n$ and $\left\vert Y\cap B_{i}\right\vert \leq1$ for every $i\in\left\{ 1,2,...,n\right\}$ .

This is the statement of Theorem 1 in darij grinberg's http://www.cip.ifi.lmu.de/~grinberg/subsetcond.pdf as an answer to a generalization hinted at by tanlsth at http://www.mathlinks.ro/viewtopic.php?t=118091

The problem is mine, in all generality, as witnessed by the apparition in the Resources section at
http://www.mathlinks.ro/resources.php?c=142&cid=25&year=2004 with a solution by induction by grobber at http://www.mathlinks.ro/viewtopic.php?p=440858#440858

(That year $2004$ , the Romanian Mathematical Olympiad for grade IX was sat, among others, by Adi Zahariuc, Iurie Boreico and Sasha Zamorzayev. As far as I remember, no-one gave a full solution during the contest, although nowadays Iurie swears he did solve it! Andrei Negut was orally given the problem, and he came with an induction proof that was somehow needing ...).

As the original problem stated, and Darij noticed, if $\left\vert X\right\vert\leq m\left( n - 1\right)$ the result stands no more, since one can take the first $n - 1$ blocks $B_i$ covering $X$ , and an arbitrary $B_n$ ; then by pigeonhole principle, any subset $Y$ of $X$ with $\left\vert Y\right\vert = n$ elements will forcibly have at least $2$ of its elements in one of the first $n - 1$ blocks.

Let me now present to you my original solution to the hard part, somehow more insightful (I think) than an inductive solution, which relies on building the subset $Y$ in a way (inductively) that escapes the full grasp of understanding its structure.

A simple observation is that one may assume $\left\vert B_{i}\right\vert = m$ for every $i\in\left\{1,2,...,n\right\}$ , since this is only to one's disadvantage (one may arbitrarily enlarge the blocks to full $m$ cardinality and prove the existence of a set $Y$ ; then its intersections with the original blocks can only be of equal or lesser cardinality).
Another simple observation is that, for any fixed $j$ , one has $\displaystyle \left\vert \bigcup_{i \neq j} B_{i}\right\vert \leq m(n - 1) < \left\vert X\right\vert$ , hence there must exist some suitable $\displaystyle x_j \in X \setminus \bigcup_{i \neq j} B_{i}$ . Now, the set $Y = \{ x_j \; ; \; j \in\left\{1,2,...,n\right\} \}$ clearly intersects the blocks in at most one element each, but of course there is no guarantee that $\left\vert Y\right\vert = n$ , since some of the elements $x_j$ may coincide!

We will remedy to this with a neat trick. Start with $j = 1$ and find a suitable $x_j$ . If $x_j \in B_j$ proceed with the next value for $j$ ; if not, replace (like for a soccer team) an arbitrary element $y_j \in B_j$ with $x_j$ , i.e. have $B_j \to (B_j \setminus \{y_j \}) \cup \{ x_j \}$ (in order to keep notations simple, we will call this new block by the same name $B_j$ ), and then proceed with the next value for $j$ . This will ensure that any newly selected $x_j$ does not match any of the ones selected before, hence $\left\vert Y\right\vert = n$ and, moreover, $\left\vert Y\cap B_{j}\right\vert = 1$ for every $j\in\left\{ 1,2,...,n\right\}$ , with the blocks as they are at the end of the process. Now replace back the elements $x_j$ with $y_j$ (where the case), getting the initial blocks. The intersection of $Y$ with any block $B_j$ may only keep (if $y_j \in Y$ ) or decrease (if $y_j \not \in Y$ ) its cardinality, whence the suitability of this set $Y$ .

_________________
Listen to REMBETIKA for decoding the handle.