Just spam combo problems cause why not

This post is mainly for Rohan Bhaiya. He gave me/EGMO contestants a lot and lots of problems. Here are solutions to a very few of them. 

To Rohan Bhaiya: I just wrote the sketch/proofs here cause why not :P. I did a few more extra problems so yeah. 

I sort of sorted the problems into different sub-areas, but it’s just better to try all of them! I did try some more combo problems outside this but I tried them in my tablet and worked there itself. So latexing was tough.

Algorithms 

“Just find the algorithm” they said and they died. 

References: 

• Algorithms Pset by Abhay Bestrapalli
• Algorithms by Cody Johnson

Problem1: Suppose the positive integer $n$ is odd. First Al writes the numbers $1, 2,\dots, 2n$ on the blackboard.
Then he picks any two numbers $a, b$ erases them, and writes, instead, $|a – b|$. Prove that an
odd number will remain at the end. 

Proof: Well, we go $\mod 2$. Note that $$|a-b|\equiv a+b\mod 2\implies \text{ the final number is }1+2+\dots 2n\equiv n(2n+1)\equiv 1\mod 2.$$

Problem2[BAMO 1999]: A lock has $16$ keys arranged in a $4 \times 4$ array, each key oriented either horizontally or vertically.
In order to open it, all the keys must be vertically oriented. When a key is switched to another
position, all the other keys in the same row and column automatically switch their positions
too. Show that no matter what the starting positions are, it is always possible to open this lock.
(Only one key at a time can be switched.) 

Proof: Well, note that the in the $4\times 4$ array, whenever we change a cell ( say cell $a$), $6$ more cells are affected. ($3$ rows and $3$ columns). Well, applying this move on all these $6$ cells will give us the same $4\times 4$ array, every cell is the same except cell $a$ which has now changed. We can repeat this move and we are done. 

Problem3[BAMO 2006]: Suppose that n squares of an infinite square grid are colored grey, and the rest are colored white. At
each step, a new grid of squares is obtained based on the previous one, as follows. For each location in
the grid, examine that square, the square immediately above, and the square immediately to the right.
If there are two or three grey squares among these three, then in the next grid, color that location grey;
otherwise, color it white. Prove that after at most n steps all the squares in the grid will be white.

Proof: We take the smallest possible rectangle which includes all the grey cells. Now, note that the cells outside this rectangle would always be white. We will induct the size of the rectangle. Consider the rectangle ($R’$) which doesn’t have the leftmost column (column $l$) and bottommost row (row $r$). Note that the column $l$, row $r$, doesn’t affect cells inside $R’$. Applying induction, we get that after some finite moves, $R’$ will be all white cells. So now only a few cells of the column $l$ and a few cells of row $r$ are grey. But in the next step, all cells will go white except the leftmost cell (which might still be grey). Again, after another step, we get all cells white. Done!

Problem4[Cody Johnson]: Consider an ordered set $S$ of $6$ integers. A move is defined by the
following rule: for each element of $S$, add either $1$ or $-1$ to it. Show that there exists a finite sequence
of moves such that the elements of the resulting set, $S’ = (n_1, n_2, \dots , n_6)$, satisfy $n_1n_5n_6 = n_2n_4n_6 =
n_3n_4n_5$.

Solution: Well, clearly after a finite amount of moves, we can get all elements to be either $0$ or $1$. ( Say, once an element becomes $0$, we can then just add one and then subtract one to this element, while making sure other elements become $0$ or $1$.)

Now, after these moves, if we have $n_1n_5n_6 = n_2n_4n_6 = n_3n_4n_5=1$ or $n_1n_5n_6 = n_2n_4n_6 = n_3n_4n_5=0$ then we are done.

Else, we will have two cases.

Case1: $n_1n_5n_6 = n_2n_4n_6 =1, n_3n_4n_5=0$ (and it’s permutations). Then notes that $(n_1,n_2,n_3,n_4,n_5,n_6)=(1,1,0,1,1,1)$. Then simply do $(0,0,1,0,0,0)$ which works.

Case2: $n_1n_5n_6 = n_2n_4n_6 = 0, n_3n_4n_5=1$ ( then we have $n_3=n_4=n_5=1$, then just make $n_3,n_4,n_5=0$. And we are done. 

Problem5: Let $\Delta$ be the maximum degree of the vertices of a given graph. Devise a method to color this graph using at most $\Delta + 1$ colors such that no two neighboring vertices are of the same color.

Proof: Well, this sounds very obvious, but here is an algorithm which def works

• We give consider the following $\Delta+1$ colours: $C_1,\dots, C_{\Delta+1}$.
• Give preference to colours as $C_1>\dots> C_{\Delta+1}$.
• Now consider with any vertex and give it colour $C_1$ (since preference to $C_1$)
• And continue colouring.
• Now, at any stage, to colour the vertices, first see the adjacent vertices, and then colour the vertex with the colour which has not been used in the adjacent vertices ( and colour by preference).
• There can not be any problem as there are $\Delta+1$ colours.

Problem6: We have $n^2$ balls of $n$ colors. Show that we can place into n bins so that every bin has almost $2$ colors of balls. Each bin gets $n$ balls.

Proof: The following algorithm works for any $mn$.

• Well consider the sequence $a_1\le \dots\le a_n$ denote 

Problem7[CAMP Application]: Given $n$ points on a plane, prove that you can label them $P_1, \dots, P_n$ such that $\angle P_iP_{i+1}P_{i+2} < 90^{\circ}$ for $1 \le i \le n-2.$

Proof: Well, here is the algorithm which works.

• Choose a random point. Name it $P_1.$
• Choose the farthest point from $P_1$ and name it $P_2.$ 
• Choose the farthest point from $P_2$ ( a point not chosen yet), and name it $P_3.$
•  Continue the process till it terminates.

Invariance/Monovariance

“How do you know when to use invariance in a problem?”~Atul

“When it’s a combinatorics problem.”~Sunaina 

P.S. Thankyou Atul for the class <3

Problem1: The integers from $1$ through $2015$, inclusive, are written on a blackboard. Every second, someone
erases four numbers of the form $a, b, c, a+b+c$ and replaces them with the numbers $a+b, b+c, c+a$.
Prove that this process can continue for at most $9$ minutes.

Proof: Well, if the problem is true then there should be at least $1475$ before we can not further any move. 

Note that $$a+b+c+a+b+c=a+b+b+c+c+a, a^2+b^2+c^2+(a+b+c)^2=(a+b)^2+(b+c)^2+(c+a)^2.$$

Hence the sum of the numbers and the sum of the squares is invariant during the process.

So say, if there are $k$ numbers in the board then we have $$ x_1^2+x_2^2+\dots+x_k^2=\frac{2015\cdot 2016\cdot (2015\cdot 2+1)}{2}$$ and $$x_1+x_2+\dots x_k=\frac{2015\cdot 2016}{2}.$$

Using CS ineq, we get that $$(x_1^2+x_2^2+\dots+x_k^2)k\ge (x_1+x_2+\dots x_k)^2\implies \frac{k2015\cdot 2016\cdot (2015\cdot 2+1)}{2}\ge [\frac{2015\cdot 2016}{2}]^2$$ $$\implies k\ge \frac{6093360}{4031}\text{ which is approx }1512.$$

And hence we get that the process can go for atmost $2015-1512=503$ secs.

Problem2: The numbers $1, 2, \dots , n$ are written in a row, in that order. On each move, we
can select two numbers and swap their positions. Can this list of numbers return to its initial ordering
after exactly $2023$ moves?

Proof: Well, note that taking two numbers and swapping them is just equivalent to making many moves but swapping two consecutive numbers. 

Say I have $1,2,3$ and I want to swap $1,3$, instead of directly swapping, I can simply perform a series of moves where I swap two consecutive numbers. 

$$1,2,3\rightarrow 1,3,2 \rightarrow 3,1,2,\rightarrow 3,2,1$$.

And now for each pair $(i,j), i<j$ consider the number of times, they have been swapped. It must be even. And now, sum it all over such pairs. We get that there should be even number of moves. 

Problem3: Can an $8\times8$ board with opposite corners removed be tiled with $1\times2$ and $2\times1$ dominoes?

Proof: Well $8\times8$ board with opposite corners  contains $32$ white squares and $30$ black. While both $1\times2$ and $2\times1$ dominoes cover equal number of black and white cells. 

Problem4: The numbers $1$ through $2023$, inclusive, are written on a blackboard. A move consists of taking two written numbers $a$ and $b$, erasing them, and writing $ab+ a +b$ on the board. Continue
this until only one number is left on the board. What is this number?

Proof: The number is $(1+1)(2+1)\dots(2023+1)-1$. Just note that $ab+a+b=(a+1)(b+1)$. So in every move the product $(a_1+1)\dots(a_i+1)$ is preserved.

Problem5[Rearrangement Inquality]: Given sequences $x_1\le x_2\le \dots x_n$ and $y_1\le y_2\le\dots y_n$ and an arbitrary permutation $\sigma$ of $1,\dots , n$, show that $x_1y_n+\dots x_ny_1\le x_1y_{\sigma(1)}+\dots+x_ny_{\sigma(n)}$ .

Proof: Well note that for $a_1\le a_2, b_1\le b_2$ we get $a_1b_2+a_2b_1\le a_1b_1+a_2b_2$. 

Now consider, $x_1y_{\sigma(1)}+\dots+x_ny_{\sigma(n)}$, if we have $x_i<x_j$ and $y_l<y_k$ and we have $x_iy_k+ x_jy_l$. Then considering, $x_iy_l+x_jy_k$, we get a smaller sum. 

Now, this sum $x_1y_{\sigma(1)}+\dots+x_ny_{\sigma(n)}$ can always be reduced to sum $x_1y_{\sigma(1)’}+\dots+x_ny_{\sigma(n)’}$ whenever we have $x_i<x_j$ and $y_l<y_k$ and we have $x_iy_k+ x_jy_l$. This process can stop only when $x_1y_n+\dots x_ny_1$.

And then no sequence can be smaller than this. 

Problem6: Consider a rectangular table with a real number
written in each cell. A move consists of selecting a row or column of the table, and multiplying all
numbers in this row/column by 1. Show that we can make all rows and columns in the table have a
non-negative sum.

Proof: Well, consider the row sums and columns sums. Let the rows be $r_1,\dots,r_m$ and columns be $c_1,\dots,c_n$. If any of row sum / column sum is negative then just multiply it by $-1$. Note that the total sum of elements increase when we do this. And this process can not go on forever. But this process terminates when all rows and columns had sum non negative.

Problem7: Sydney the squirrel is at $(0,0)$ and can move by reflecting her current
position over a line segment connecting two lattice points, provided that this reflection puts her on another lattice point. Find all points in the plane that Sydney can reach in finitely many moves.

Proof: For a point, define it’s neighbour to be the set of points such that distance between them is $\sqrt{2}$ or $1$ ( there are eight such points).

Sydney can achieve all points. We can star with induction. Clearly Sydney can attain all points which are from distance $\sqrt{2}$ and $2$ units far, so it can achieve all points which are from distance $\sqrt{2}$ and $1$ units far. And from these points, we do the same and attain all it’s neighbours and go on.