Let $m, n$ be positive integers with $m > 1$. Anastasia partitions the integers $1, 2, \dots , 2m$ into $m$ pairs. Boris then chooses one integer from each pair and finds the sum of these chosen integers.
Prove that Anastasia can select the pairs so that Boris cannot make his sum equal to $n$.
Re: Combi Marathon
Posted: Tue Feb 21, 2017 10:54 am
by Thanic Nur Samin
$\text{Solution to problem 5:}$
We denote the $n^{th}$ triangular number by $T_n$.
Now, consider the pairs: $(1,m+1),(2,m+2),(3,m+3)\cdots (m,2m)$.
If we take $k$ of the second elements, we see that this pairing can only achieve the values of form $T_m+km$ where $k$ is an integer so that $0\le k\le m$.
Now, consider the pairs: $(m,m+1),(1,m+2),(2,m+3),(3,m+4)\cdots (m-1,m+1)$.
Note that, we can take either $m$ or $m+1$ from the first part. If we take $s$ of the second elements of the remaining pairings, this can only achieve the values of the form $T_m+s(m+1)$ and $T_m+s(m+1)+1$, where $s$ is an integer so that $0\le s\le m-1$.
Now, $T_m+km=T_m+s(m+1)\Rightarrow km=s(m+1)$, so $m+1|k$. But $k\le m$, so $k=0$. Therefore $s=0$.
Again, $T_m+km=T_m+s(m+1)+1\Rightarrow km=s(m+1)+1\Rightarrow (k-s)m=s+1$. So $m|s+1$. Again, $s\le m-1$, so $s=m-1$. Thus $k=m$.
So, the only values that can be achieved by both of the previous pairings are $T_m$ and $T_m+m^2$.
Now, take the pairing $(1,2),(3,4),(5,6)\cdots (2m-1,2m)$.
If we take $t$ of the second ones, then the values covered are of the form $m^2+t$ where $t$ is an integer with $0\le t\le m$. So it covers all integers from $m^2$ to $m^2+m$. But for $m>1$, $T_m<m^2$ and $T_m+m^2>m^2+m$.
So, Anastasia can partition the integers so that Boris can't make the sum equal to $n$ by selecting the appropiate one from the previous $3$ constructions.
Re: Combi Marathon
Posted: Tue Feb 21, 2017 10:58 am
by Thanic Nur Samin
$\text{Problem 6:}$
Each square of a $2^n - 1 \times 2^n - 1$ square board contains either $+1$ or $−1$. Such an arrangement is deemed successful if each number is the product of its neighbours. Find the number of successful arrangements.
Re: Combi Marathon
Posted: Wed Feb 22, 2017 9:04 pm
by Zawadx
Thanic Nur Samin wrote:$\text{Problem 6:}$
Each square of a $2^n - 1 \times 2^n - 1$ square board contains either $+1$ or $−1$. Such an arrangement is deemed successful if each number is the product of its neighbours. Find the number of successful arrangements.
Which type of neighbourhood? There are over 5 kinds >.>
Re: Combi Marathon
Posted: Wed Feb 22, 2017 9:09 pm
by ahmedittihad
Zawadx wrote:
Thanic Nur Samin wrote:$\text{Problem 6:}$
Each square of a $2^n - 1 \times 2^n - 1$ square board contains either $+1$ or $−1$. Such an arrangement is deemed successful if each number is the product of its neighbours. Find the number of successful arrangements.
Which type of neighbourhood? There are over 5 kinds >.>
The squares that share an edge with it.
Re: Combi Marathon
Posted: Thu Feb 23, 2017 2:58 pm
by Thanic Nur Samin
Solution to problem 6
First, lets define some terms.
1. A arrangement with at least one $-1$ will be called a nontrivial arrangement.
2. A arrangement that remains unchanged when its reflected by its middle column will be called vertically symmetric. Similarly, horizontally symmetric is defined.
3. A arrangement that is both vertically and horizontally symmetric will be called bisymmetric.
Now, we have to prove some lemmas.
Lemma 1: A nontrivial bisymmetric arrangement has all $1$'s on its middle row and middle column.
Proof: We prove for rows. Due to symmetry and the problem statement, the center cell must contain $1$.
Now, if the cell directly next to the center cell has a $1$, then its clear that the whole row must contain $1$ and we are done.
Now, assume that the cell directly next to the center cell has a $-1$. Some speculation and simple logic tells us that then it would go like $1,-1,-1,1,-1,-1\ldots 1,-1,-1$. But that would imply that $3|2^{n-1}$. Impossible. So we are done.
Lemma 2: If there exists a nontrivial vertically assymetric arrangement, there exists a nontrivial vertically symmetric arrangement.
Proof: Reflect the arrangement wrt the middle column, and multiply the overlapping numbers. We are done.
Lemma 3: If there exists a nontrivial arrangement, then there exists a nontrivial bisymmetric arrangement.
Proof: Its an obvious consequence of lemma 2.
Now we are ready to solve the problem. We claim that there exists $2$ arrangements for $n=1$ and only one arrangement, namely the trivial arrangement for $n>1$. We use induction. The $n=2$ case is easy to prove. Now, assume that its true for $n-1$.
If there exists a nontrivial arrangement for $n$, then there exists a nontrivial bisymmetric arrangement for $n$. But the middle row and middle column divides the board into four parts of size $2^{n-1}-1\times 2^{n-1}-1$. Because the middle row and column only contains $1$s, There exists a nontrivial arrangement for $n-1$. But thats not true. So, by induction, for all $n>1$, there exists only one successful arrangement. [Proved]
Re: Combi Marathon
Posted: Thu Feb 23, 2017 3:19 pm
by Thanic Nur Samin
$\text{Problem 7}$
Elmo is drawing with colored chalk on a sidewalk outside. He first marks a set $S$ of $n>1$ collinear points. Then, for every unordered pair of points $\{X,Y\}$ in $S$, Elmo draws the circle with diameter $XY$ so that each pair of circles which intersect at two distinct points are drawn in different colors. Count von Count then wishes to count the number of colors Elmo used. In terms of $n$, what is the minimum number of colors Elmo could have used?
Re: Combi Marathon
Posted: Thu Feb 23, 2017 11:09 pm
by ahmedittihad
Wrong solu :p
Re: Combi Marathon
Posted: Fri Feb 24, 2017 4:27 pm
by tanmoy
Thanic Nur Samin wrote:$\text{Problem 7}$
Elmo is drawing with colored chalk on a sidewalk outside. He first marks a set $S$ of $n>1$ collinear points. Then, for every unordered pair of points $\{X,Y\}$ in $S$, Elmo draws the circle with diameter $XY$ so that each pair of circles which intersect at two distinct points are drawn in different colors. Count von Count then wishes to count the number of colors Elmo used. In terms of $n$, what is the minimum number of colors Elmo could have used?
$\text{Solution:}$ Answer:
The answer is $\left \lceil \frac{n} {2} \right \rceil$ for all $n \neq 3$ and $1$ for $n=3$.
Definitions:At first, definitions of some notations used in this proof:
(i)$f(C)$ is the minimum number of colors Elmo could have used;
(ii)$D(x, y)$ denotes the circle with diameter $xy$. Here $x$ is the left endpoint of $xy$ and $y$ is the right endpoint of $xy$;
(iii)$C(x,y)$ denote the color of $D(x, y)$.
First, let's prove this for even $n$. Let $n=2m$. Lower bound:
Let's number the points $1, 2, ....., 2m$ from left to right. Denote by . The circles $D(1, m+1)$, $D(2, m+2)$,.......$D(m,2m)$ intersect each other at two different points. So, $m$ distinct colors are needed to color these $m$ circles. Then $f(C) \geq m$.
Construction:
We will show that $m$ colors are enough. Let there are $m$ colors called $c_{1}, c_{2},........,c_{m}$. First color the $2m$ points like $c_{1}, c_{2},........,c_{m}$, $c_{1}, c_{2},........,c_{m}$.
Now, to color the circles, follow the following algorithm: $C(x, x+m)=c_{x}$.
Color the circle $D(x, y)$ with the color of point $x$ for $(y-x) < m$ and color the circle $D(x, y)$ with the color of point $y$ for $(y-x) > m$. Clearly, this construction works.
Now, for odd $n>3$. Let $n=2m+1$. Lower bound:
As above, label the points $1, 2,..........,2m+1$ from left to right. Same as above, we need $m$ colors to color the circles $D(1, m+2)$, $D(2, m+3)$,.......$D(m,2m+1)$. Color these $m$ circles as above.
Then consider the circle $D(1, m+1)$, it intersects all the circles $D(2, m+3)$, $D(3, m+4)$.......$D(m,2m+1)$, so, is of color different from them and tangent to $D(1, m+2)$. So, of course $C(1, m+1)=c_{1}$.
Similarly, we can show that $C(x, x+m)=c_{x}$. So, $C(m+1, 2m+1)=m+1$ and $f(C) \geq m+1$.
Construction:
For $n=3$, all circles are tangent to each other. So, $1$ color would be enough.
Now, we will show that $m+1$ colors are enough for $n=2m+1>3$. Using the above construction for even $n$, color the circles which doesn't contain point $2m+1$ with the $m$ colors, $c_{1}, c_{2},........,c_{m}$.
Now color the circles which contain point $2m+1$ with color $c_{m+1}$, since all these circles are tangent to each other, this coloring is okay.
Re: Combi Marathon
Posted: Fri Feb 24, 2017 9:21 pm
by tanmoy
$\text {Problem 8}$
We have $\dfrac {n(n+1)} {2}$ stones in $k$ piles. In each move we take one stone from each pile and form a new pile with these stones (if a pile has only one stone, after that stone is removed the pile vanishes). Show that regardless of the initial configuration, we always end up with $n$ piles, having $1, 2,............., n$ stones, respectively.