Let $k$ be a positive integer. Show that for all $n>k$ there exist convex figures $F_{1},\ldots, F_{n}$ and $F$ such that there doesn't exist a subset of $k$ elements from $F_{1},..., F_{n}$ and $F$ is covered for this elements, but $F$ is covered for every subset of $k+1$ elements from $F_{1}, F_{2},....., F_{n}$.
Problem
Source:
Tags: integration, combinatorics unsolved, combinatorics
03.09.2006 20:39
Maybe this works. Take a convex poligon $P$ with $\binom{n}{k}$ vertices and consider a set $T$ of $\binom{n}{k}$ pairwise disjoint triangles each of which has a vertex in common with $P$, the 2 sides adjacent to it being contained in the two sides of $P$ it belongs to. Make a correspondence between each $S\subset\{1,2...n\}$, $|S|=k$ and a triangle $t_{S}\in T$ so that no triangle is assigned to two different sets. Now define the sets $T_{i}\subset T$, $1\leq i\leq n$, in the following way $t_{S}\in T_{i}\leftrightarrow i\in S$. Notice that for each set $X\subset\{1,2...n\}$ with $|X|=k$, ${\bigcap \{ T_{i}| i\in X \}=\{t_{X}}\}$, since $\forall i\in X ( t_{S}\in T_{i}) \leftrightarrow \forall i\in X(i \in S)$. For the same reason, for each $Y\subseteq \{1,2...n\}$ with $|Y|=k+1$, $\bigcap \{ T_{i}| i \in X \}=\emptyset$. Now consider the sets of points (indeed, polygons) in the plane $Q_{i}=P-\bigcup T_{i}$, $1\leq i\leq n$. Clearly each of them is convex, because of the way we chose the elements of $T$. On the other hand, $\forall X\subset \{ 1,2...n\}$ with $|X|=k$ $\bigcup\{T_{i}|i\in X\}=P-\bigcup (\bigcap \{ T_{i}|i \in X \}) \}= P-\bigcup \{ t_{X}\}\subset P$, while $\forall Y \subset \{ 1,2...n \}$ with $|Y|=k+1$, $\bigcup\{T_{i}|i \in Y \}=P-\bigcup (\bigcap \{ T_{i}|i\in Y \}) \}= P-\bigcup\emptyset=P$. And we are done. Sorry for my english.
07.02.2012 23:13
I can't understand how is taken the set $ T $. can you be more clear or give an example,please?