For discussing Olympiad Level Combinatorics problems
Posts: 90
Joined: Fri Dec 28, 2012 8:35 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!

Posts: 90
Joined: Fri Dec 28, 2012 8:35 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.$
Time: 1:40 hours

Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

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

Posts: 90
Joined: Fri Dec 28, 2012 8:35 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.
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: 108
Joined: Sat Feb 07, 2015 9:47 pm

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.

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: 108
Joined: Sat Feb 07, 2015 9:47 pm

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.$
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: 108
Joined: Sat Feb 07, 2015 9:47 pm

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

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

Revive this?
Frankly, my dear, I don't give a damn.

tanmoy
Posts: 289
Joined: Fri Oct 18, 2013 11:56 pm

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

rah4927
Posts: 108
Joined: Sat Feb 07, 2015 9:47 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".