Let $P$ be the set of all $2012$ tuples $(x_1, x_2, \dots, x_{2012})$, where $x_i \in \{1,2,\dots 20\}$ for each $1\leq i \leq 2012$. The set $A \subset P$ is said to be decreasing if for each $(x_1,x_2,\dots ,x_{2012} ) \in A$ any $(y_1,y_2,\dots, y_{2012})$ satisfying $y_i \leq x_i (1\leq i \leq 2012)$ also belongs to $A$. The set $B \subset P$ is said to be increasing if for each $(x_1,x_2,\dots ,x_{2012} ) \in B$ any $(y_1,y_2,\dots, y_{2012})$ satisfying $y_i \geq x_i (1\leq i \leq 2012)$ also belongs to $B$. Find the maximum possible value of $f(A,B)= \dfrac {|A\cap B|}{|A|\cdot |B|}$, where $A$ and $B$ are nonempty decreasing and increasing sets ($\mid \cdot \mid$ denotes the number of elements of the set).
Problem
Source: Turkish NMO 2nd Round 2012 - P5
Tags: induction, inequalities, combinatorics proposed, combinatorics
paul1703
01.12.2012 11:43
Answer: $\frac{1}{20^{2012}}$ Corolary of kleitman theorem http://books.google.ro/books?id=RjDd4RaqrIwC&pg=PA87&lpg=PA87&dq=kleitman+lemma+divisors&source=bl&ots=tjaVz-OyZf&sig=zB6WxhI6ULwopJ2A3WZeHNwHnYg&hl=ro&sa=X&ei=HM-5UOvhGMq1tAaez4DgBQ&ved=0CCcQ6AEwAA#v=onepage&q=kleitman%20lemma%20divisors&f=false
xeroxia
14.09.2013 20:51
Let $A_1 = \{x_1 \colon x_1 \in \mathbb {N}, 1 \leq x_1 \leq a_1 \leq 20\}$ and $B_1 = \{x_1 \colon x_1 \in \mathbb {N}, 1 \leq b_1 \leq x_1 \leq 20\}$. Lemma: $|A_1|\cdot |B_1| \geq 20\cdot |A_1 \cap B_1|$ Proof: \[\begin{array}{rcl} |A_1|\cdot |B_1| &\geq& 20\cdot |A_1 \cap B_1| \\ a_1(20-b_1+1) &\geq& 20(a_1-b_1+1) \\ 20a_1 - a_1b_1 + a_1 &\geq& 20a_1 - 20b_1 + 20 \\ 20b_1 - 20 - a_1b_1 + a_1 &\geq& 0 \\ (20-a_1)(b_1 - 1) &\geq& 0. \end{array}\]
Now, let $A_2 = \{x_2 \colon x_2 \in \mathbb {N}, 1 \leq x_2 \leq a_2 \leq 20\}$ ve $B_2 = \{x_2 \colon x_2 \in \mathbb {N}, 1 \leq b_2 \leq x_2 \leq 20\}$.
We've just proved: $|A_2|\cdot |B_2| \geq 20\cdot |A_2 \cap B_2|$.
Let $A_{1,2} = \{(x_1, x_2) \colon x_1 \in A_1, x_2 \in A_2\}$ and $B_{1,2} = \{(x_1, x_2) \colon x_1 \in B_1, x_2 \in B_2\}$. \[ \begin{array}{rcl}
|A_{1,2}| &=& |A_1|\cdot |A_2| \\
|B_{1,2}| &=& |B_1|\cdot |B_2| \\
|A_{1,2} \cap B_{1,2}| &=& |A_1 \cap B_1| \cdot |A_2 \cap B_2| \\
|A_{1,2}|\cdot |B_{1,2}| &=& |A_1| \cdot |A_2| \cdot |B_1| \cdot |B_2| \\
|A_{1,2}|\cdot |B_{1,2}| &\geq & 20^2\cdot |A_1 \cap B_1| \cdot |A_2 \cap B_2| \\
|A_{1,2}|\cdot |B_{1,2}| &\geq & 20^2\cdot |A_{1,2} \cap B_{1,2}|
\end{array}\]
Let $A_{1,2,3} = \{(x_1, x_2, x_3) \colon (x_1, x_2) \in A_{1,2} \text{ and } x_3 \in A_3\}$ and $B_{1,2,3} = \{(x_1, x_2, x_3) \colon (x_1, x_2) \in B_{1,2} \text{ and } x_3 \in B_3\}$. It's easy to see \[|A_{1,2,3}|\cdot |B_{1,2,3}| \geq 20^3\cdot |A_{1,2,3} \cap B_{1,2,3}|\] In fact, by induction, \[|A_{1,2,3, \dots, 2012}|\cdot |B_{1,2,3, \dots, 2012}| \geq 20^{2012}\cdot |A_{1,2,3, \dots, 2012} \cap B_{1,2,3, \dots, 2012}|\] \[|A|\cdot |B| \geq 20^{2012} \cdot |A\cap B|\]
So \[\dfrac{1}{20^{2012}} \geq \dfrac{|A\cap B|}{|A|\cdot |B|}\] Equality holds when $A=P$ or $B=P$. In conclusion, maximum value of $|A \cap B|/\left (|A|.|B| \right )$ is $\dfrac{1}{20^{2012}}$.
dddd
13.11.2013 19:02
we can focus only one x_i . look x_1. for A x_1 changes a to 1, and for B x_1 changes b to 20. if b>a $ |A\cap B| $=0 if a>b $ |A\cap B| $=b-a+1 $ |A\cap B|/(|A|.|B|) $=(b-a+1)/(21-b).a is less then 1/20
dddd
19.11.2013 16:04
But this isn't our question. This is very different.
typhlosion
20.11.2013 19:02
@xeroxia your solution doesn't work, for example; for $ A =\{(1,2),(2,1),(1,1)\} $ then $ A=A_{i,j} $ ?? also if $b_1\geq a_1 +1$ then $|A\cap B|=0$ ?? in real exam only one competitor solved this problem I will write solution soon
matematikolimpiyati
22.06.2014 23:05
This is the official solution: The answer is $\dfrac {1}{20^{2012}}$. Let us treat more general case when $P$ is the set of all $n$ tuples. If $A=B=P$ then $f(A,B) = \dfrac{1}{20^n}$. We prove that $f(A,B) \leq \dfrac{1}{20^n}$ by induction over $n$. $n=1$. Suppose that $A=\{1,2, \dots, a+c \}$, $B=\{20-b-c+1, \dots, 20\}$. Then $|A\cap B| = c$, $|A|=a+c$, $|B|=b+c$ and $f(A,B) = \dfrac{c}{(a+c)(b+c)} = \dfrac{1}{20+ab/c} \leq \dfrac {1}{20}$. Suppose that the statement is correct for $n-1$. Let $A= \bigcup \limits_{i=1}^{20} A_i$, where elements of the set $A_i$ are obtained from elements of $A$ having last entry $i$ by removing this last entry (I think this notation is wrong. $A_i$ is a $n-1$-tuple. If we append $i$ to each tuples, that may be true.). By definitions $|A|= \sum \limits_{i=1}^{20} |A_i|$ and $A_1 \subset A_2 \subset \cdots \subset A_{20}$ (I think it should be $\supset$). Let $B= \bigcup \limits_{i=1}^{20} B_i$, where elements of the set $B_i$ are obtained from elements of $B$ having last entry $i$ by removing this last entry (Same thoughts...). By definitions $|B|= \sum \limits_{i=1}^{20} |B_i|$ and $B_1 \supset B_2 \supset \cdots \supset B_{20}$ (I think it should be $\subset$). Now \[|A\cap B| = \sum \limits_{i=1}^{20} |A_i \cap B_i| \leq \dfrac{1}{20^{n-1}} \sum \limits_{i=1}^{20} |A_i| \cdot |B_i| \leq \dfrac{1}{20^{n-1}} \cdot \dfrac {1}{20}( \sum \limits_{i=1}^{20} |A_i|)(\sum \limits_{i=1}^{20} |B_i|) = \dfrac{1}{20^n} |A| \cdot |B|\] (The first inequality is valid due to inductive hypothesis, the second inequality is the Chebyshev's rearrangement inequality). Done.
aviateurpilot
05.12.2015 00:59
Hello for each $A$ we can find $(a_1,a_2,......,a_{2012})$ such that for $\forall$ $x_i\le a_i$ <=> $( x_1,x_2,....,x_{2012})$ belongs to $A$ in this case $|A|= a_1.a_2.a_3......a_{2012}$ for each $B$ we can find $(b_1,b_2,......,b_{2012})$ such that for $\forall$ $x_i\ge b_i$ <=> $( x_1,x_2,....,x_{2012})$ belongs to $B$ in this case $|B|= (21-b_1).(21-b_2).(21-b_3)......(21-b_{2012})$ and $|A\cap B|=(a_1-b_1+1).(a_2-b_2+1).(a_3-b_3+1)......(a_{2012}-b_{2012}+1)$ where we must have $b_i\le a_i$ to have $A\cap B$ no empty $f(A,B)$ is maximal where all $(a_i-b_i+1)/a_i(21-b_i)$ is maximal. and it easy to prove that it's maximal when $a_i=20$ and $b_i=1$ so $f(A,B)= (1/20).(1/20).(1/20)........(1/20)$
bin_sherlo
20.11.2024 00:23
Answer is $\frac{1}{20^{2012}}$. Construction: Let $(a_1,...,a_{2012})\subset A$ with the largest sum and $(b_1,...,b_{2012})\subset B$ with the smallest sum. Pick $a_i=20$ and $b_i=1$. Proof:We must have $a_i\geq b_i$ in order to get $|A\cap B|>0$. \[f(A,B)=\frac{(a_1-b_1+1)...(a_{2012}-b_{2012}+1)}{a_1...a_{2012}(21-b_1)...(21-b_{2012})}=\Pi{(\frac{a_i-b_i+1}{a_i(21-b_i)})}\]Consider $\{a_i\},\{b_i\}$ where $f_{max}$ is achieved. \[g(x,y)=\frac{x-y+1}{x(21-y)}\implies f(A,B)=g(a_1,b_1)...g(a_{2012},b_{2012})\]If $x+y\geq 20$, then \[g(x,y)-g(x+1,y+1)=\frac{x-y+1}{x(21-y)}-\frac{x-y+1}{(x+1)(20-y)}=(x-y+1)(\frac{20x+20-xy-y-21x+xy}{x(21-y)(x+1)(22-y)})\leq 0\]If $x+y<20$, then \[g(x,y)-g(x-1,y-1)=\frac{x-y+1}{x(21-y)}-\frac{x-y+1}{(x-1)(22-y)}=(x-y+1)(\frac{22x-22+y-xy-21x+xy}{x(21-y)(x-1)(22-y)})<0\]Also note that $x\geq y$. Thus, $f_{max}$ is achieved when $a_i=20$ or $b_i=1$. WLOG $a_1,...,a_l=20$ and $b_{l+1}=...=b_{2012}=1$. \[f(A,B)\leq \Pi{(\frac{21-b_i}{20(21-b_i)})}\Pi{(\frac{a_i}{20a_i})}=\frac{1}{20^{2012}}\]As desired.$\blacksquare$