Combi Marathon

For discussing Olympiad Level Combinatorics problems
rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm
Re: Combi Marathon

Unread post by rah4927 » Tue Feb 21, 2017 12:35 am

$\text{Problem } 5$

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$.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: Combi Marathon

Unread post by Thanic Nur Samin » Tue Feb 21, 2017 10:54 am

$\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.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: Combi Marathon

Unread post by Thanic Nur Samin » Tue Feb 21, 2017 10:58 am

$\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.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

User avatar
Zawadx
Posts:90
Joined:Fri Dec 28, 2012 8:35 pm

Re: Combi Marathon

Unread post by Zawadx » Wed Feb 22, 2017 9:04 pm

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 >.>

User avatar
ahmedittihad
Posts:181
Joined:Mon Mar 28, 2016 6:21 pm

Re: Combi Marathon

Unread post by ahmedittihad » Wed Feb 22, 2017 9:09 pm

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.
Frankly, my dear, I don't give a damn.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: Combi Marathon

Unread post by Thanic Nur Samin » Thu Feb 23, 2017 2:58 pm

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]
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: Combi Marathon

Unread post by Thanic Nur Samin » Thu Feb 23, 2017 3:19 pm

$\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?
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

User avatar
ahmedittihad
Posts:181
Joined:Mon Mar 28, 2016 6:21 pm

Re: Combi Marathon

Unread post by ahmedittihad » Thu Feb 23, 2017 11:09 pm

Wrong solu :p
Frankly, my dear, I don't give a damn.

tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh

Re: Combi Marathon

Unread post by tanmoy » Fri Feb 24, 2017 4:27 pm

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.
"Questions we can't answer are far better than answers we can't question"

tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh

Re: Combi Marathon

Unread post by tanmoy » Fri Feb 24, 2017 9:21 pm

$\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.
"Questions we can't answer are far better than answers we can't question"

Post Reply