A function $f(S)$ assigns to each nine-element subset of $S$ of the set $\{1,2,\ldots, 20\}$ a whole number from $1$ to $20$. Prove that regardless of how the function $f$ is chosen, there will be a ten-element subset $T\subset\{1,2,\ldots, 20\}$ such that $f(T - \{k\})\neq k$ for all $k\in T$.
Problem
Source:
Tags: USA(J)MO, USAMO, pigeonhole principle, ceiling function, function, boolean lattice method
OhGreatCaesar21
29.07.2011 16:27
Moderator note: the wording of the problem now has been changed to what it used to be, due to the fact that when this problem was originally posted the wording was taken from the Kalva archive. Thus some variable names are different in the successive posts, but the overall flavor of the solution should be the same. ~dj There are $ \binom{20}{10} $ distinct $ 10 $-element subsets of set $ X $. Label these subsets as $ G_{1}, G_{2}, G_{3}, ..., G_{\binom{20}{10}} $. Assume for the sake of contradiction that there exists an instance for which we cannot find a 10-element subset $ Y $ of $ X $, such that $ f(Y-\{k\}) \ne k $. This assumption implies that there always exists a member $ m_{i} $ of the set $ G_{i} $ such that $ f(G_{i} - \{m_{i}\}) = m_{i} $ for integer $ i $, where $ 1 \le i \le \binom{20}{10} $. Note also that $ G_{j} \ne G_{k} $ if $ j \ne k $ for $ 1 \le j, k \le \binom{20}{10} $ since these sets are distinct. Notice that $ G_{i} - \{m_{i}\} $ is a $ 9 $-element subset of $ X $. There are $ \binom{20}{9} $ distinct members in the set $ P $. By the Pigeonhole Principle, there exists at least $ \lceil \frac{\binom{20}{10}}{\binom{20}{9}} \rceil $ sets of the form $ G_{i} - \{m_{i}\} $ that are equal to a single element of $ P $, which we shall call that element the set $ H $. I claim that $ \lceil \frac{\binom{20}{10}}{\binom{20}{9}}\rceil = 2 $. Proof: $ \lceil \frac{\frac{20!}{(10!)(10!)}}{\frac{20!}{(9!)(11!)}} \rceil = \lceil \frac{11}{10}\rceil = 2 $ Thus, there exists at least two sets and thus two sets $ G_{j} - \{m_{j}\} $ and $ G_{k} - \{m_{k}\} $ that are equal to $ H $, where $ 1 \le j, k \le \binom{20}{10} $ and $ j \ne k $. By our assumption, $ f(G_{j} - \{m_{j}\}) = m_{j} $ and $ f(G_{k} - \{m_{k}\}) = m_{k} $. Furthermore $ f(H) = f(G_{j} - \{m_{j}\}) = f(G_{k} - \{m_{k}\}) $. Thus, $ m_{k} = m_{j} $. Also, $ H = G_{j} - \{m_{j}\} = G_{k} - \{m_{k}\} $, thus $ G_{j} = G_{k} $. However, since $ j \ne k $, $ G_{j} \ne G_{k} $. There is a contradiction. Thus, our assumption is incorrect. This proves that for any map $ f:P\mapsto X $, we can find a $ 10 $-element subset $ Y $ of $ X $ such that $ f(Y-\{k\}) \ne k $ for any $ k $ in $ Y $.
McTeague
16.08.2014 19:45
Alternatively, for a given function $f$, consider the set of elements $Q \in P$ paired with elements $z \in X$ such that $f(Q) \ne z$. Call the set of pairs of elements $Q$ with elements $z$ as set $R$. To employ the Pigeonhole Principle, it would be useful to get a lower bound on the cardinality $r$ of $R$. There are $\dbinom{20}{9}$ elements $Q$ in $P$. If $f(Q) \in Q$, then there are $11$ choices for $z$ so that $f(Q) \ne z$. If $f(Q) \not\in Q$, then there are $10$ choices for $z$ so that $f(Q) \ne z$. So, $r \ge 10 \cdot \dbinom{20}{9}$. These pairs $(Q,z)$ must be dispersed over the $\dbinom{20}{10}$ many $10$-element subsets of $X$ so that by the Pigeonhole Principle, some $10$-element subset of $X$ must contain at least $\left\lceil\frac{r}{\dbinom{20}{10}}\right\rceil = \left\lceil\frac{10\cdot\dbinom{20}{9}}{\dbinom{20}{10}}\right\rceil = \left\lceil\frac{100}{11}\right\rceil = 10$ pairs of a $9$-element subset $Q$ with the tenth element $z$ of that subset such that $f(Q) \ne z$, in other words, this $10$-element set satisfies the conditions of the problem.
rafayaashary1
07.03.2017 03:22
The codeimport java.util.*;
import java.lang.*;
import java.io.*;
public class WhatInCombination {
public static void main(String[] args) {
HashSet<HashSet<Integer>> pre=comb(20,9);
HashSet<HashSet<Integer>> post=comb(20,10);
HashMap<HashSet<Integer>,Integer> fun=new HashMap<HashSet<Integer>,Integer>();
Iterator<HashSet<Integer>> it=pre.iterator();
while(it.hasNext()){
HashSet<Integer> temp=it.next();
int val=(int)(20*Math.random());
fun.put(temp,val);
if(!temp.contains(val)){
temp.add(val);
post.remove(temp);
temp.remove(val);
}
}
long countRight=post.size();
if(marathon(post,fun))
System.out.println(countRight+" vs "+16796+", pass");
else
System.out.println("logic fail");
}
public static HashSet<HashSet<Integer>> comb(int n, int r){
HashSet<HashSet<Integer>> combo=new HashSet<HashSet<Integer>>();
if(r==0){
HashSet<Integer> empt=new HashSet<Integer>();
combo.add(empt);
return combo;
}
else if(r==n){
HashSet<Integer> stuff=new HashSet<Integer>();
for(int x=0; x<n; x++)
stuff.add(x);
combo.add(stuff);
return combo;
}
else
combo=cup(join(comb(n-1,r-1),n-1),comb(n-1,r));
return combo;
}
public static HashSet<HashSet<Integer>> join(HashSet<HashSet<Integer>> h, int n){
HashSet<HashSet<Integer>> joined=new HashSet<HashSet<Integer>>();
Iterator<HashSet<Integer>> it=h.iterator();
while(it.hasNext()){
HashSet<Integer> temp=it.next();
temp.add(n);
joined.add(temp);
}
return joined;
}
public static HashSet<HashSet<Integer>> cup(HashSet<HashSet<Integer>> i, HashSet<HashSet<Integer>> j){
HashSet<HashSet<Integer>> cupped=new HashSet<HashSet<Integer>>();
Iterator<HashSet<Integer>> itOne=i.iterator();
while(itOne.hasNext()){
HashSet<Integer> temp=itOne.next();
cupped.add(temp);
}
Iterator<HashSet<Integer>> itTwo=j.iterator();
while(itTwo.hasNext()){
HashSet<Integer> temp=itTwo.next();
cupped.add(temp);
}
return cupped;
}
public static boolean test(HashSet<Integer> h, HashMap<HashSet<Integer>,Integer> m){
Boolean tester=true;
HashSet<Integer> copi=new HashSet<Integer>();
Iterator<Integer>pol=h.iterator();
while(pol.hasNext())
copi.add(pol.next());
Iterator<Integer> nums=h.iterator();
while(nums.hasNext()){
int temp=nums.next();
copi.remove(temp);
if(m.get(copi)==temp)
tester=false;
copi.add(temp);
}
return tester;
}
public static boolean marathon(HashSet<HashSet<Integer>> compost, HashMap<HashSet<Integer>,Integer> m){
Iterator<HashSet<Integer>> luck=compost.iterator();
while(luck.hasNext()){
if(!test(luck.next(), m))
return false;
}
return true;
}
} has a runtime of approximately 12 minutes using the Netbeans IDE. It first instantiates the sets $K_9$ and $K_{10}$. Then it produces a random map $f:K_9\mapsto X$. Subsequently, it removes the "ruined" elements (a.k.a. $R$) of $K_{10}$. Finally, it tests every remaining set in $K_{10}$ for violation of the problem statement. If no such set exists, which is a strong indication of the above working, it outputs the number of remaining elements (which should be at least $16796$) as well as the phrase "pass." In the case that it fails (which indicates that the solution is flawed), it outputs "logic fail." I received the former result for two out of the two runs I performed.
. In fact the following scenario gives the opposite result: Quote: Let $X$ be the set $ \{ 1, 2, \cdots, 2n+1 \} $ and let $P$ be the set of all $n$-element subsets of $X$. Show that there exists a map $ f: P \mapsto X $ such that for every $n+1$ element subset $Y$ of $X$, there exists $k\in Y$ such that $ f(Y - \{ k \}) = k$.
For convenience, let $K_i$ be the family of $i$-element subsets of $X$. Note that $f$ is a function $f:K_{n}\mapsto X$. Once again, we say that $p\in K_{n}$ ruins $q\in K_{n+1}$ iff $f(p)\not\in p$ and $q=p\cup \{f(p)\}$. In particular, we wish to exhibit a surjection $g:K_n\mapsto K_{n+1}$ so that $\forall p\in K_n,\ p\subseteq g(p)$. Once we have $g$, we can simply let $f(p)=g(p)\setminus p$. Now, consider the graph $G=(V,E)$ where $G=K_{n}\cup K_{10}$ and $(q,r)\in E\iff q\subseteq r\text{ and }|q\setminus r|=1$. It is not hard to see that this graph is bipartite with two equal components (who are $K_{n}$ and $K_{n+1}$), and that $g$ describes a perfect matching on $G$. We now apply Hall's Marriage Theorem and a special case of the Trickling Lemma (found here). Specifically, every vertex (on either side) is of degree $n+1$, so the size of the neighborhood of any set $S$ that lies completely in one of the bipartite components is $\geq \tfrac{n+1}{n+1}|S|=|S|$, which is exactly Hall's Condition. We conclude the result $\Box$