Combi Solution Writing Threadie

For discussing Olympiad Level Combinatorics problems
User avatar
Zawadx
Posts:90
Joined:Fri Dec 28, 2012 8:35 pm
Combi Solution Writing Threadie

Unread post by Zawadx » Tue Sep 20, 2016 9:03 pm

Writing solutions is one of the worst parts of Olympiads - they just eat up your time and distract you from the interesting part, solving problems. But sadly, almost all your points will come from your written solution. So it is worth it to learn how to write solutions alongside learning problem solving.

Most of us hope to learn solution writing through contests themselves - but this is a recipe for disaster. Let me count the number of solutions I've written in true olympiad style exams in the past year. The count is Geometry: 9, NT: 8 (2 of these were wrong, but I didn't realize it fully while writing), Combi: 6, Algebra: 1! Most people can't really master something by doing so little of it, and so it should be no surprise that I still suck at solu writing.

This thread is my effort to fix that. I chose combi first, because the nature of combi makes solus harder to write rigorously. Ofco we'll have to start practicing solus for other subjects if only to save more time, but starting with combi seems correct.

So here we only post solutions, and criticism/comments/grades of other people's solutions. Please include the problem alongside your solution. Criticism of the solution should be constructive, and should include stuff like gaps in logic and stylistic choices which can be changed to make the solu more natural. This thread depends on active participation, so please come forth and help us out!

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

Re: Combi Solution Writing Threadie

Unread post by Zawadx » Tue Sep 20, 2016 10:18 pm

IMOSL 2007 C1
rah4927 wrote:Let $ n > 1$ be an integer. Find all sequences $ a_1, a_2, \ldots a_{n^2 + n}$ satisfying the following conditions:
\[ \text{ (a) } a_i \in \left\{0,1\right\} \text{ for all } 1 \leq i \leq n^2 + n;
\] \[ \text{ (b) } a_{i + 1} + a_{i + 2} + \ldots + a_{i + n} < a_{i + n + 1} + a_{i + n + 2} + \ldots + a_{i + 2n} \text{ for all } 0 \leq i \leq n^2 - n.
\]
Let,
\[ S_k = \sum_{i=k+1}^{k+n} a_i \text{ for } 0 \leq k \leq n^2 \]
\[ d_k = S_k - S_{k-n} \]

Putting in $ i = mn $ for $m = 0, 1, 2, \dots n$ in (b) we get:

\[ S_0 < S_n < S_{2n} < \dots < S_{n^2} \]

But each of the $S_{mn}$ can take a value from 0 to n and there are n+1 of them. So $S_{kn}$ and $S_{(k+1)n}$ differ by exactly $1$. Therefore:

\[ S_{kn} = k \]

Therefore, $a_k = 0$ for all $1 \leq k \leq n$ and $a_k=1$ for all $n^2 +1 \leq k \leq n^2 + n$

Now, let $c$ be the least positive integer for which $a_{cn} = 1$. Now, $ S_{(c-1)n} = S_{(c-2)n} + 1$. Subtracting $a_{cn} = a_{(c-1)n} +1$,

\[ \sum_{k = (c - 2)n + 1}^{(c-1)n} = \sum_{k= (c-1)n + 1}^{cn -1} \]

\[ \rightarrow S_{(c-2)n - 1} = S_{(c-1)n - 1} ( \text{ if } c > 2 ) \]

Therefore $c = 2$ $\rightarrow$ $a_k = 0$ for all $1 \leq k \leq 2n - 1 $

Now put in $i = mn + r$ for some fixed $1 \leq r \leq n-1$ and $m = 0, 1, 2, \dots n$ in (b). We get:

\[ S_r < S_{n+r} < \dots < S_{n^2 + r} \]

But each of the $S_{mn + r}$ can take a value from 0 to n and there are n of them. So $d_{mn+r}$ is $2$ for exactly one value of $m$, and $1$ for all others.

Suppose for some $1 \leq r \leq n-1$, $q$ is the least positive integer for which $a_{qn + r} = 1$. Thus $ r \leq n-1$ $\rightarrow$ $q > 2$.

It is easy to compute (even though I had to spend 15 min checking) that:

\[ d_{(q-1)n + r - 1} + 1 = d_{(q-1)n + r} \]
\[ d_{qn + r - 1} > d_{qn + r} \]

Since $ a_{(q+1)n + r} – a_{qn + r} = 0 or -1$ for $ ( a_{(q+1)n + r} , a_{qn + r} ) = (1, 1)$ or $(0, 1)$.

Now, $d_k$ can either be $1$ or $2$. So checking the various cases for $d_{(q-1)n + r – 1}$ and $d_{qn + r – 1}$, we obtain the only possible values:

[*] $d_{(q-1)n + r - 1} = 1$
[*]$d_{qn + r - 1} = 2$
[*] $ d_{(q-1)n + r} = 2$
[*] $d_{qn + r} = 1$

The second and third equations imply that $ ( a_{mn + r} , a_{(m-1)n + r} ) = ( 1, 0 ) $ cannot be true for any $ m > q $, as that would require either $d_{qn + r - 1} = 2$ or $ d_{(q-1)n + r} = 2$ which is impossible.

Thus $ d_{(q-1)n + r} = 2$ if and only if $q$ is the least positive integer for which $a_{qn + r} = 1$. Let this value of $q$ for some $r$ be $q_r$. Also, for all positive integers $t$ not equal to $q_r$, $a_t = a_{t-1}$.

Then, $d_{(q_r)n + r - 1} = 2$ implies $q_{r-1}$ = $ q_r + 1$.

Now, note that $S_n = 1$, $a_{2n} = 1$ and $S_{2n} = 2$ implies that $d_{2n-1} = 2$. Thus $q_{n-1} = 3$.

Thus we can inductively find all $q_r$, and hence all $a_i$. So there exists exactly one sequence which satisfies the conditions.
Time: 1:40 hours :(

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: Combi Solution Writing Threadie

Unread post by Phlembac Adib Hasan » Fri Sep 23, 2016 12:54 pm

Nice initiative. Go on!
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

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

Re: Combi Solution Writing Threadie

Unread post by Zawadx » Sat Oct 08, 2016 4:24 pm

The problem is due to Rahul Saha, from an unknown source.
2016 nonnegative integers are written on a board. In each step, you can erase two of the numbers and replace them with their sum and their difference. For any given set of 2016 nonnegative integers on the blackboard, is it possible, in a finite number of steps, to reach a state having at least 2015 zeroes?
The ideas of the solution are due to Nayeemul Islam Swad. I simply wanted to write them up into a formal solution.
Notation:

The problem is not altered if we suppose that the numbers have to be written on 2016 fixed spaces $s_1, s_2, \dots s_{2016}$. Let $n_i$ denote the number currently on $s_i$ Then, for $n_i > n_j$, applying the operation on $s_i, s_j$ would involving placing $n_i + n_j$ on $s_i$, and $n_i - n_j$ on $s_j$.

We define two functions:
$f(x) =$ the greatest odd divisor of $x$
$t(x) = $the exponent of $2$ in the prime-power factorization of $x$

Lemma 1: We can double $n_i$ and $n_j$ in two moves for any $i,j$


Proof:
Apply the operation twice on $s_i, s_j$.
Note that if we have $n_z = 0$ for some $z$, we can multiply $n_i$ by any power of $2$ for any $i$ in a finite number of moves.

Lemma 2: If $t(n_i) = t(n_j)$, applying the operation on $s_i, s_j$ will decrease max$( f(n_i), f(n_j) )$.

Proof:
Note that $f(n_i + n_j) \leq \frac{f(n_i) + f(n_j)}{2}$, since $f(n_i) + f(n_j$ is odd. And, $f(n_i - n_j) \leq \frac{f(n_i) - f(n_j)}{2}$, since $f(n_i) - f(n_j$ is odd. Note that since all of the $n_i$ are integers, this decrease can only have the lower bound to $1$.

Algorithm: We devise a process to turn one of $n_i, n_j$ into $0$ for arbitrary choices of $i,j$.
  1. Fix $i, j$. Also find the minimum value of $n_k$ for $k =/= i, j$.
  2. We use the operation multiple times on $s_i, s_k$ or $s_j, s_k$ until $t(n_i) = t(n_j)$. By lemma 1, this is possible in a finite number of steps. Note that this doesn't change $f(n_i), f(n_j)$.
  3. Apply the operation once on $s_i, s_j$, thus decreasing max$( f(n_i), f(n_j) )$ by lemma 2.
  4. Repeat steps 2 & 3. Thus max$( f(n_i), f(n_j) )$ monotonically decreases, so the process must terminate. Then WLOG we must have undefined $f(n_i)$, which is possible if and only if $n_i = 0$.
Since after the first application of this algorithm we have $n_i = 0$ for some $i$, the minimum value of $n_k$ is 0. Thus repeating the algorithm will not change the values of numbers on any spaces other than the chosen. $s_i, s_j$.

So we apply the algorithm first on $(i,j) = (1,2)$. Then, after $n_i = 0$ for some $i$, we replace $i$ with the smallest value $l$ such that $n_l > 0$. Thus eventually we'll reach a state having 2015 or 2016 zeroes.
Time = 25 minutes. Getting faster! (Tho the ideas were pretty well constructed here, need to test on a problem I've personally solved)

rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: Combi Solution Writing Threadie

Unread post by rah4927 » Tue Oct 11, 2016 3:56 am

There is a handout by Evan Chen used at MOP this year to teach students about solution writing. Should be relevant to this thread. You can find it in the first section titled "English" in the following link.

http://www.mit.edu/~evanchen/olympiad.html

I guess the big takeaways from the note that are important for this thread are :
  1. Rather than writing up each step of a proof in a messy paragraph, divide the whole thing neatly into several claims.
  2. Try to mention the main idea of your proof in a separate paragraph, preferably at the beginning. Letting the grader know that your idea is correct at the beginning of a proof can often make him more enticed in your writing.
  3. If a combi problem asks you to optimize a value (which is like half of all combi probs), first write "We show the bound is X" , then proceed to give the construction (do NOT forget this part - as E Chen says, let the grader know you understand the difference between bounds and optimality), and then write down the proof of the bound.
  4. This should go without saying, but please don't include bad math in your solutions (especially when you are desperate). This frustrates the grader and you only lose your chances of scoring points.

rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: Combi Solution Writing Threadie

Unread post by rah4927 » Tue Oct 11, 2016 4:01 am

Zawadx wrote:IMOSL 2007 C1
rah4927 wrote:Let $ n > 1$ be an integer. Find all sequences $ a_1, a_2, \ldots a_{n^2 + n}$ satisfying the following conditions:
\[ \text{ (a) } a_i \in \left\{0,1\right\} \text{ for all } 1 \leq i \leq n^2 + n;
\] \[ \text{ (b) } a_{i + 1} + a_{i + 2} + \ldots + a_{i + n} < a_{i + n + 1} + a_{i + n + 2} + \ldots + a_{i + 2n} \text{ for all } 0 \leq i \leq n^2 - n.
\]
Let,
\[ S_k = \sum_{i=k+1}^{k+n} a_i \text{ for } 0 \leq k \leq n^2 \]
\[ d_k = S_k - S_{k-n} \]

Putting in $ i = mn $ for $m = 0, 1, 2, \dots n$ in (b) we get:

\[ S_0 < S_n < S_{2n} < \dots < S_{n^2} \]

But each of the $S_{mn}$ can take a value from 0 to n and there are n+1 of them. So $S_{kn}$ and $S_{(k+1)n}$ differ by exactly $1$. Therefore:

\[ S_{kn} = k \]

Therefore, $a_k = 0$ for all $1 \leq k \leq n$ and $a_k=1$ for all $n^2 +1 \leq k \leq n^2 + n$

Now, let $c$ be the least positive integer for which $a_{cn} = 1$. Now, $ S_{(c-1)n} = S_{(c-2)n} + 1$. Subtracting $a_{cn} = a_{(c-1)n} +1$,

\[ \sum_{k = (c - 2)n + 1}^{(c-1)n} = \sum_{k= (c-1)n + 1}^{cn -1} \]

\[ \rightarrow S_{(c-2)n - 1} = S_{(c-1)n - 1} ( \text{ if } c > 2 ) \]

Therefore $c = 2$ $\rightarrow$ $a_k = 0$ for all $1 \leq k \leq 2n - 1 $

Now put in $i = mn + r$ for some fixed $1 \leq r \leq n-1$ and $m = 0, 1, 2, \dots n$ in (b). We get:

\[ S_r < S_{n+r} < \dots < S_{n^2 + r} \]

But each of the $S_{mn + r}$ can take a value from 0 to n and there are n of them. So $d_{mn+r}$ is $2$ for exactly one value of $m$, and $1$ for all others.

Suppose for some $1 \leq r \leq n-1$, $q$ is the least positive integer for which $a_{qn + r} = 1$. Thus $ r \leq n-1$ $\rightarrow$ $q > 2$.

It is easy to compute (even though I had to spend 15 min checking) that:

\[ d_{(q-1)n + r - 1} + 1 = d_{(q-1)n + r} \]
\[ d_{qn + r - 1} > d_{qn + r} \]

Since $ a_{(q+1)n + r} – a_{qn + r} = 0 or -1$ for $ ( a_{(q+1)n + r} , a_{qn + r} ) = (1, 1)$ or $(0, 1)$.

Now, $d_k$ can either be $1$ or $2$. So checking the various cases for $d_{(q-1)n + r – 1}$ and $d_{qn + r – 1}$, we obtain the only possible values:

[*] $d_{(q-1)n + r - 1} = 1$
[*]$d_{qn + r - 1} = 2$
[*] $ d_{(q-1)n + r} = 2$
[*] $d_{qn + r} = 1$

The second and third equations imply that $ ( a_{mn + r} , a_{(m-1)n + r} ) = ( 1, 0 ) $ cannot be true for any $ m > q $, as that would require either $d_{qn + r - 1} = 2$ or $ d_{(q-1)n + r} = 2$ which is impossible.

Thus $ d_{(q-1)n + r} = 2$ if and only if $q$ is the least positive integer for which $a_{qn + r} = 1$. Let this value of $q$ for some $r$ be $q_r$. Also, for all positive integers $t$ not equal to $q_r$, $a_t = a_{t-1}$.

Then, $d_{(q_r)n + r - 1} = 2$ implies $q_{r-1}$ = $ q_r + 1$.

Now, note that $S_n = 1$, $a_{2n} = 1$ and $S_{2n} = 2$ implies that $d_{2n-1} = 2$. Thus $q_{n-1} = 3$.

Thus we can inductively find all $q_r$, and hence all $a_i$. So there exists exactly one sequence which satisfies the conditions.
Time: 1:40 hours :(
Deviates from a lot of important rules, i would say. You should definitely include the answer in your first line, i.e. "We prove that only one such sequence exists" , and then proceed to construct that sequence.

Further mention induction after that, and perhaps a rough description of your inductive method. Your calculations seem a bit purposeless to a reader until you finally explain what you are doing, but maybe that's just me being sleepy again.

rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: Combi Solution Writing Threadie

Unread post by rah4927 » Tue Oct 11, 2016 4:04 am

Zawadx wrote:The problem is due to Rahul Saha, from an unknown source.
2016 nonnegative integers are written on a board. In each step, you can erase two of the numbers and replace them with their sum and their difference. For any given set of 2016 nonnegative integers on the blackboard, is it possible, in a finite number of steps, to reach a state having at least 2015 zeroes?
The ideas of the solution are due to Nayeemul Islam Swad. I simply wanted to write them up into a formal solution.
Notation:

The problem is not altered if we suppose that the numbers have to be written on 2016 fixed spaces $s_1, s_2, \dots s_{2016}$. Let $n_i$ denote the number currently on $s_i$ Then, for $n_i > n_j$, applying the operation on $s_i, s_j$ would involving placing $n_i + n_j$ on $s_i$, and $n_i - n_j$ on $s_j$.

We define two functions:
$f(x) =$ the greatest odd divisor of $x$
$t(x) = $the exponent of $2$ in the prime-power factorization of $x$

Lemma 1: We can double $n_i$ and $n_j$ in two moves for any $i,j$


Proof:
Apply the operation twice on $s_i, s_j$.
Note that if we have $n_z = 0$ for some $z$, we can multiply $n_i$ by any power of $2$ for any $i$ in a finite number of moves.

Lemma 2: If $t(n_i) = t(n_j)$, applying the operation on $s_i, s_j$ will decrease max$( f(n_i), f(n_j) )$.

Proof:
Note that $f(n_i + n_j) \leq \frac{f(n_i) + f(n_j)}{2}$, since $f(n_i) + f(n_j$ is odd. And, $f(n_i - n_j) \leq \frac{f(n_i) - f(n_j)}{2}$, since $f(n_i) - f(n_j$ is odd. Note that since all of the $n_i$ are integers, this decrease can only have the lower bound to $1$.

Algorithm: We devise a process to turn one of $n_i, n_j$ into $0$ for arbitrary choices of $i,j$.
  1. Fix $i, j$. Also find the minimum value of $n_k$ for $k =/= i, j$.
  2. We use the operation multiple times on $s_i, s_k$ or $s_j, s_k$ until $t(n_i) = t(n_j)$. By lemma 1, this is possible in a finite number of steps. Note that this doesn't change $f(n_i), f(n_j)$.
  3. Apply the operation once on $s_i, s_j$, thus decreasing max$( f(n_i), f(n_j) )$ by lemma 2.
  4. Repeat steps 2 & 3. Thus max$( f(n_i), f(n_j) )$ monotonically decreases, so the process must terminate. Then WLOG we must have undefined $f(n_i)$, which is possible if and only if $n_i = 0$.
Since after the first application of this algorithm we have $n_i = 0$ for some $i$, the minimum value of $n_k$ is 0. Thus repeating the algorithm will not change the values of numbers on any spaces other than the chosen. $s_i, s_j$.

So we apply the algorithm first on $(i,j) = (1,2)$. Then, after $n_i = 0$ for some $i$, we replace $i$ with the smallest value $l$ such that $n_l > 0$. Thus eventually we'll reach a state having 2015 or 2016 zeroes.
Time = 25 minutes. Getting faster! (Tho the ideas were pretty well constructed here, need to test on a problem I've personally solved)
This is a very good write-up of the solution. Perhaps adding "Our main idea is to turn the integers $0$ one by one" may help, but that is probably just personal taste (or criticism for the mere sake of it).

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

Re: Combi Solution Writing Threadie

Unread post by ahmedittihad » Thu Jan 12, 2017 12:48 am

Revive this?
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 Solution Writing Threadie

Unread post by tanmoy » Mon Feb 20, 2017 12:05 am

rah4927 wrote:Problem 1

Let $n > 3$ be a fixed positive integer. Given a set $S$ of $n$ points $P_1, P_2,\cdots, P_n$ in the plane such that no three are collinear and no four concyclic, let $a_t$ be the number of circles $P_i P_j P_k$ that contain $P_t$ in their interior, and let $m(S) = a_1 + a_2 +\cdots + a_n$. Prove that there exists a positive integer $f(n)$ depending only on $n$ such that the points of $S$ are the vertices of a convex polygon if and only if $m(S) = f(n)$.
Nice double counting problem. Here is my solution:
We will show that $\ f(n)=2\binom{n}{4}$ satisfies the problem's condition.

Let's define $m(S)$ in another way, let $m(S)$ be the number of pairs $(P_{t}, \ P_{i}P_{j}P_{k})$ so that $\ P_{t} \ $ lies interior of $(P_{i}P_{j}P_{k})$.

Let's take a $4-element$ subset $S_{a}=\{ P_{i}, \ P_{j}, \ P_{k}, \ P_{l} \}$ of the set $S$. $a_{x}$ is the number of circles among these $4$ points that contain $x$ in their interior. Take the convex hull of $S_{a}$. There are two cases:

Case (i):
The convex hull is a triangle. WLOG it is $\ P_{i}P_{j}P_{k}$. Then $a_{i}=a_{j}=a_{k}=0$ and $a_{l}=1$. In this case, $m(S)=1$.

Case (ii):
The convex hull is the quadrilateral $\ P_{i}P_{j}P_{k}P_{l}$. Now, from the problem's condition, $P_{i}P_{j}P_{k}P_{l}$ is not cyclic. Then WLOG, we may assume that $\angle P_{i}P_{j}P_{k}+\angle P_{k}P_{l}P_{i} < 180^{\circ} < \angle P_{j}P_{k}P_{l}+\angle P_{l}P_{i}P_{j}$. Then $a_{j}=a_{l}=0$ and $a_{i}=a_{k}=1$. In this case, $m(S)=2$.

From above, we see that for any $4-element$ subset of the set $S$, the maximum sum of $m(S)$ is $2$. There are $\binom{n}{4}$ such subsets. So, $m(S) \leq 2\binom{n}{4}$.

Now,$m(S) = 2\binom{n}{4}$ if and only if every four points of $S$ makes a convex quadrilateral, i.e. the points of $S$ determine a convex polygon. So, $\ f(n)=2\binom{n}{4}$ satisfies the problem's condition.
"Questions we can't answer are far better than answers we can't question"

rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: Combi Solution Writing Threadie

Unread post by rah4927 » Mon Feb 20, 2017 2:26 pm

Nice solu Tanmoy. However, the things that you are doing seem magic until we get to the end. Perhaps you should add a brief summary at the beginning. Something like "We will show that every set of four points can contribute at most $2$ to the original sum".

Post Reply