Combi Marathon
$\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$.
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$.
- Thanic Nur Samin
- Posts:176
- Joined:Sun Dec 01, 2013 11:02 am
Re: Combi Marathon
$\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.
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.
Because destroying everything mindlessly isn't cool enough.
- Thanic Nur Samin
- Posts:176
- Joined:Sun Dec 01, 2013 11:02 am
Re: Combi Marathon
$\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.
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.
Because destroying everything mindlessly isn't cool enough.
Re: Combi Marathon
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 >.>
- ahmedittihad
- Posts:181
- Joined:Mon Mar 28, 2016 6:21 pm
Re: Combi Marathon
The squares that share an edge with it.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 >.>
Frankly, my dear, I don't give a damn.
- Thanic Nur Samin
- Posts:176
- Joined:Sun Dec 01, 2013 11:02 am
Re: Combi Marathon
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]
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.
Because destroying everything mindlessly isn't cool enough.
- Thanic Nur Samin
- Posts:176
- Joined:Sun Dec 01, 2013 11:02 am
Re: Combi Marathon
$\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?
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.
Because destroying everything mindlessly isn't cool enough.
- ahmedittihad
- Posts:181
- Joined:Mon Mar 28, 2016 6:21 pm
Re: Combi Marathon
$\text{Solution:}$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?
Answer:
First, let's prove this for even $n$. Let $n=2m$.
Lower bound:
Lower bound:
"Questions we can't answer are far better than answers we can't question"
Re: Combi Marathon
$\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.
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"