Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

For each balanced sequence a = (a1; a2; : : : ; a2n) let f(a) be the sum of the positions of the 1’s in a. For example, f(01101001) = 2+3+5+8 = 18. Partition the ¡2n n ¢balanced sequences into n+1 classes according to the residue of f (mod n+1), and let S be a class of minimum size. Then jSj · 1 n+1¡2n n ¢, and we claim that every balanced sequence is either a member of S or is a neighbor of at least one member of S. Let a = (a1; a2; : : : ; a2n) be a given balanced sequence. We consider two cases. Case (i): a1 = 1. The balanced sequence b = (b1; b2; : : : ; b2n) obtained from a by moving the leftmost 1 just to the right of the kth 0 satisfies f(b) = f(a)+k. (If am+1 is the kth 0 of a, then in going from a to b, the leftmost 1 is moved up m places and m¡k 1’s are moved back one place each.) Thus we find n neighbors of a so that the values of f for a and these neighbors fill an interval of n + 1 consecutive integers. In particular, one of these n + 1 balanced sequences belongs to S. Case (ii): a1 = 0. This case is similar. Movement of the initial 0 just to the right of the kth 1 yields a neighbor b satisfying f(b) = f(a) ¡ k. Hence every balanced sequence is either equal to or is a neighbor of at least one member of S.

mohammad-mahmoodi wrote: For each balanced sequence a = (a1; a2; : : : ; a2n) let f(a) be the sum of the positions of the 1’s in a. For example, f(01101001) = 2+3+5+8 = 18. Partition the ¡2n n ¢balanced sequences into n+1 classes according to the residue of f (mod n+1), and let S be a class of minimum size. Then jSj · 1 n+1¡2n n ¢, and we claim that every balanced sequence is either a member of S or is a neighbor of at least one member of S. Let a = (a1; a2; : : : ; a2n) be a given balanced sequence. We consider two cases. Case (i): a1 = 1. The balanced sequence b = (b1; b2; : : : ; b2n) obtained from a by moving the leftmost 1 just to the right of the kth 0 satisfies f(b) = f(a)+k. (If am+1 is the kth 0 of a, then in going from a to b, the leftmost 1 is moved up m places and m¡k 1’s are moved back one place each.) Thus we find n neighbors of a so that the values of f for a and these neighbors fill an interval of n + 1 consecutive integers. In particular, one of these n + 1 balanced sequences belongs to S. Case (ii): a1 = 0. This case is similar. Movement of the initial 0 just to the right of the kth 1 yields a neighbor b satisfying f(b) = f(a) ¡ k. Hence every balanced sequence is either equal to or is a neighbor of at least one member of S. If you copy a solution from somewhere else, then please (1) tell your source (in this case: the IMO Shortlist 2001 official solutions), (2) convert it into LaTeX. darij

Quote: If you copy a solution from somewhere else, then please (1) tell your source (in this case: the IMO Shortlist 2001 official solutions), (2) convert it into LaTeX. darij _________________ lift this prayer to heaven's heights, feed my mind with the most glorious thoughts, sacrificing all my dreams... for this i will serve and honour to death... or do i just fear the tyrant's wrath? HOW TO convert it into LaTeX ?

mohammad-mahmoodi wrote: HOW TO convert it into LaTeX ? Learn LaTeX here: Best: http://www.mathlinks.ro/Forum/viewtopic.php?search_id=1602648475&t=188533 Q & A: http://www.mathlinks.ro/Forum/viewtopic.php?search_id=1602648475&t=12230 Official: http://www.mathlinks.ro/Forum/viewtopic.php?search_id=1602648475&t=5261 My personal tip(This is how I learnt.): Try to search for posts written in LaTeX in the various brunches of this forum (You will find plenty). Then click on "quote" button on the bottom-right corner of the post and see how it looks(You need to be logged on first). You might modify a bit and see the preview yourself. You needn't really post. Just cancel the post when you are done.

For each balanced sequence $ a = (a_1, a_2, \dots , a_{2n})$ let $ f(a)$ be the sum of the positions of the $ 1$’s in $ a$. For example, $ f(01101001) = 2+3+5+8 = 18$. Partition the $ \binom{2n}{n}$ balanced sequences into $ n+1$ classes according to the residue of $ f\pmod{n+1}$, and let $ S$ be a class of minimum size. Then $ (n+1)|S|\leq \binom{2n}{n}$, and we claim that every balanced sequence is either a member of $ S$ or is a neighbor of at least one member of $ S$. Let $ a = (a_1, a_2, \dots , a_{2n})$ be a given balanced sequence. We consider two cases. Case (i): $ a_1 = 1$. The balanced sequence $ b = (b_1, b_2, \dots , b_{2n})$ obtained from $ a$ by moving the leftmost $ 1$ just to the right of the $ k$-th $ 0$ satisfies $ f(b) = f(a)+k$. (If $ a_{m+1}$ is the $ k$-th $ 0$ of $ a$, then in going from $ a$ to $ b$, the leftmost $ 1$ is moved up $ m$ places and $ m-k$ $ 1$’s are moved back one place each.) Thus we find $ n$ neighbors of $ a$ so that the values of $ f$ for $ a$ and these neighbors fill an interval of $ n + 1$ consecutive integers. In particular, one of these $ n + 1$ balanced sequences belongs to $ S$. Case (ii): $ a_1 = 0$. This case is similar. Movement of the initial $ 0$ just to the right of the $ k$th $ 1$ yields a neighbor $ b$ satisfying $ f(b) = f(a) - k$. Hence every balanced sequence is either equal to or is a neighbor of at least one member of $ S$.

Let $a_1,a_2,\cdots a_{2n}$ be the sequence of $0$s and $1$s. For some sequence $s$, let $f(s)=\sum_{k=1}^{2n} ka_k$. We claim that for any $m$, the set \[ S=\{s : f(s)\equiv m\pmod{n+1}\} \]is sufficient (and since there are $n+1$ such sets and $\binom{2n}{n}$ total sequences, at least one must have appropriate size). Let $s_k$ be the sequence where $a_1$ is put in position $k$, so $s_k=s$ in particular. If $a_1=0$, then $f(s_{2n})=f(s_1)+n$. Note that $f(s_1),f(s_2),\cdots f(s_{2n})$ is a sequence of integers increasing by $0$ or $1$ each time, so by discrete IVT there must be $k$ with $f(s_k)\equiv m\pmod{n+1}$. If $a_1=1$, then $f(s_{2n})=f(s_1)-n$. Note that $f(s_1),f(s_2)\cdots f(s_{2n})$ is a sequence of integers decreasing by $0$ or $1$ each time, so again by discrete IVT there must be $k$ with $f(s_k)\equiv m\pmod{n+1}$.

Wait is that the formula for the Catalan numbers?

Yes it is. It's also a bit of a red herring. In fact mathocean97 and myself did not solve this problem when we tried it some time ago.

mihirb wrote: Wait is that the formula for the Catalan numbers? I think it isn't related to Catalan numbers, is it?

<pi37> wrote: $f(s)=\sum_{k=1}^{2n} ka_k$ How could you think of $f(s)$?

For a balanced sequence $s$, let $f(s)$ denote the sum of the positions of the $1$s. It is easy to see that by removing a $1$ and placing it in at all possible $2n$ locations, we get $f$-values from $a,a+1,\ldots,a+n$, where $a$ is the sum of the positions after removing the $1$. Thus, if we fix $0\le k\le n$, then there is some $s'$ adjacent to $s$ such that $f(s')\equiv k\pmod{n+1}$. This implies that the set \[S_k = \{s : f(s)\equiv k\pmod{n+1}\}\]works. To finish, note that \[|S_0|+\cdots+|S_n|=\binom{2n}{n},\]so we can pick some $k$ such that $|S_k|\le\frac{1}{n+1}\binom{2n}{n}$. This completes the solution. Remark: I was originally spending most of my time trying to modify Catalan sequences in various ways to no avail. I think it's pretty clear after trying this approach for a while that it will inevitably bunch up too many sequences close together, thus missing many sequences. The key for this problem is to step away from that approach and look for simpler things.

We hope to find a function $f:\{\text{balanced sequence}\}\to [n+1],$ such that for any balanced sequence $\alpha,$ let $N(\alpha )$ be the set of neighbors of $\alpha,$ we always have $\text{Im}(f(N(\alpha)))=[n+1].$ If so by Pigeonhole principle there exists $j\in [n+1]$ such that $|\text{ker}(j)|\le\frac {\binom{2n}n}{n+1},$ take the set $\text{ker}(j)$ and we are done. Here let $\alpha =(\varepsilon_1,\ldots ,\varepsilon_{2n}),f(\alpha)=\sum i\varepsilon_i\mod{n+1}.$ Define $\alpha _t=(\varepsilon_2,\ldots ,\varepsilon_t,\varepsilon_1,\varepsilon_{t+1},\ldots ,\varepsilon_{2n})\in N(\alpha).$ Then $$f(\alpha)-f(\alpha_t)=(t-1)\varepsilon_1-\sum_{i=2}^t\varepsilon_i=\sum_{i=2}^t(\varepsilon_1-\varepsilon_t).$$Because $\# \{\varepsilon_i=1\} =\# \{\varepsilon_i=0\}=n, $ $\# \{\varepsilon_i\neq\varepsilon_1\}=n.$ Therefore from $\alpha_1$ to $\alpha_{2n},$ $f(\alpha)-f(\alpha_t)$ add(minus) 1 for $n$ times, so $[n+1]\subseteq\{f(\alpha_1),\ldots ,f(\alpha_{2n})\},$ done.$\Box$