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

References: 

• Invariants and Monovariants by James 
• Invariants by Dylan Yu

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. 

Problem8: Several positive integers are written on a blackboard. One can erase any two distinct integers and write their greatest common divisor and least common multiple instead. Prove that eventually the numbers will stop changing.

Proof: Well the product is invariant however the sum increase as $\gcd(a,b)+\text{lcm}(a,b) > a+b$. Say $\gcd(a,b)=d, a=dm,b=dn$. Then $\gcd(a,b)+\text{lcm}(a,b)=d+dmn, a+b=dm+dn$. And $mn+1>m+n$.

Problem9: Given a graph $G$ on $n$ vertices, show that we can color the vertices with the colors red and blue so that for every vertex, at least half of its neighbors are of opposite color.

Proof: Do any colouring. Now, if for any vertex, the number of neighbours of opposite colour are not at least half, then swap the colour of the vertex. Note that number of edges with distinct colour vertex endpoints increases. But there is only finite such edges. Hence this process must terminate. 

Problem10: On an $n\times n$ board, there are $n^2$ squares, $n-1$ of which are infected. Each second, any square that is adjacent to at least two infected squares becomes infected. Show that at least one square always remains uninfected.

Proof: Name the rows as $r_1,r_2,\dots,r_n$ and columns as $c_1,c_2,\dots,c_n$. Say these $n-1$ squares are in $i$ rows and $j$ columns. Note that even after $n$ seconds, these infections can not go to a new square row or column. Hence  at least one square always remains uninfected.

Problem11[ISL 2014]: We have $2^m$ sheets of paper, with the number $1$ written on each of them. We perform the following operation. In every step we choose two distinct sheets; if the numbers on the two sheets are $a$ and $b$, then we erase these numbers and write the number $a+ b$ on both sheets. Prove that after $m2^{m-1}$ steps, the sum of the numbers on all the sheets is at least $4^m$.

Proof: Well, consider the product. Note that after every minute, the product changes by $$\frac{P(a+b)^2}{ab}$$ and comparing it with $P$, we get by AM-GM $$\frac{P(a+b)^2}{ab}\ge 4P.$$ So the product multiplies by $4$ times, every minute. So after  $m2^{m-1}$ steps, the product should be atleast $4^{m2^{m-1}}$ and hence the sum of numbers should be atleast, by AM-GM, $$2^m\cdot \sqrt[2^m]{4^{m2^{m-1}}}=4^m.$$

A good thing is to consider weights. We want stuffs to either be constant or increase strictly or decrease strictly usually. 

Problem13[ISL 2012]: Several positive integers are written in a row. Alice chooses two adjacent numbers $x$ and $y$ such that $x > y$ and $x$ is to the left of $y$, and replaces the pair $(x, y)$ by either $(y + 1, x)$ or $(x - 1, x)$. Prove that she can perform only finitely many such iterations.

Proof: Here say we index rows $r_1,\dots,r_n$ and give weights $w_1<\dots<w_n$. Then we have $$w_1x+w_2y\rightarrow w_1(y+1)+w_2x, w_1(x-1)+w_2x$$

Taking weights such that $w_1<w_2$, we get that by reaarnegment inequality, $$w_1x+w_2y\le w_1(y+1)+w_2x, w_1x+w_2y\le w_1(x-1)+w_2x.$$ Hence the sum always increases. 

But this cannot go on forever as there is a maximum sum. Hence this has to stop. 

Taking $(w_1,\dots,w_n)=(1,2,\dots,n)$ works. 

Problem14[Russia 2022]: $200$ natural numbers are written in a row. For any two adjacent numbers of the row, the right one is either $9$ times greater than the left one, $2$ times smaller than the left one. Can the sum of all these 200 numbers be equal to $24^{2022}$?

Proof: So we sort of want $9x\equiv x/2\mod m$. Taking $m=17$ works. We get that 17 must divide the sum. But $17$ doesn't divide $24^{2022}$.

Problem 15[Russia 2008]: A natural number is written on the blackboard. Whenever number $ x$ is written, one can write any of the numbers $ 2x + 1$ and $ \frac {x}{x + 2}$. At some moment the number $ 2008$ appears on the blackboard. Show that it was there from the very beginning.

Proof: Note that the sum of numerator and denominator (not written in simplified form) after any move doubles. But here we have the sum as $2009$. 

Problem 16[EGMO2023 TST India]:  Alice has an integer $N > 1$ on the blackboard. Each minute, she deletes the current number $x$ on the blackboard and writes $2x+1$ if $x$ is not the cube of an integer, or the cube root of $x$ otherwise. Prove that at some point of time, she writes a number larger than $10^{100}$.

Proof: Suppose not. Then in any case, add $1$ to all the terms of this sequence. Note that $$x+1\rightarrow 2(x+1) \text{ or } x^3+1\rightarrow z^3+1=(z+1)(z^2-z+1)\rightarrow z+1.$$

Note that $z^2-z+1$ is always odd. So after every move, the $v_2$ of the terms is non decreasing. Since the sequence is bounded. After good enough steps, $v-2$ stops increasing and then the cube root operation will be performed forever. Which is not possible.

Problem 17[Tuymaada 2018 P6]: The numbers $1, 2, 3, \dots, 1024$ are written on a blackboard. They are divided into pairs. Then each pair is wiped off the board and non-negative difference of its numbers is written on the board instead. $512$ numbers obtained in this way are divided into pairs and so on. One number remains on the blackboard after ten such operations. Determine all its possible values.

Proof: Note that the final number as $$1+2+\dots+2^{10}\equiv 0\mod 2.$$ 

And every even number is achievable. Say the number is $x$. Then here is the construction 

$$(1,2),\dots, (2^{10}-x-3,2^{10}-x-3,2^{10}-x-2), (2^{10}-x,2^{10}-x+1),\dots (2^{10}-2,2^10-1),(2^{10}-x-1,2^{10})\rightarrow (1,1,\dots,1,x+1)\rightarrow (1,\dots, 1,x).$$

Problem 18[USAMO 2003]: At the vertices of a regular hexagon are written six nonnegative integers whose sum is $2003^{2003}$. Bert is allowed to make moves of the following form: he may pick a vertex and replace the number written there by the absolute value of the difference between the numbers written at the two neighboring vertices. Prove that Bert can make a sequence of moves, after which the number $0$ appears at all six vertices.

Sketch: Well, note that the maximal element in every move is either same or decreased. So now consider the step when the sum of the vertices is the minimum. And then just bash it. Note that one vertex must be $0$ and then we get many inequalities. At the end it is force that of four element, two are equal to each other, and there is one $0$. 

Problem 19[TOT]:  On a blackboard, several polynomials of degree $37$ are written, each of them has the leading coefficient equal to $1$. Initially all coefficients of each polynomial are nonnegative. By one move it is allowed to erase any pair of polynomials $f, g$ and replace it by another pair of polynomials $f_1, g_1$ of degree $37$ with the leading coefficients equal to $1$ such that either $f_1 + g_1 = f + g$ or $f_1g_1 = fg$. Prove that it is impossible that after some move each polynomial on the blackboard has $37$ distinct positive roots.

Proof: Take $$f=x^{37}+a_1x^{36}+\dots+ a_{37}$$

$$g=x^{37}+b_1x^{36}+\dots+ b_{37}$$

$$f_1=x^{37}+c_1x^{36}+\dots+ c_{37}$$

$$g_1=x^{37}+d_1x^{36}+\dots+ d_{37}$$

Note comparing cfs of $fg=f_1g_1$ and $f+g=f_1+g_1$, we get that the sum $a_1+b_1=c_1+d_1$. So the sum of coefficients of $x^{36}$ is constant which we know is nonnegative. So for at least one polynomial, the cf would be positive and hence that polynomial (by viettas) cannot have all roots positive.

Graph Theory 

Problem1: A finite graph G is drawn on a blackboard. The following operation is permitted: pick any cycle of C of G, draw a new vertex v, connect it to all vertices of C, and finally erase all the edges of C. Prove that this operation can only be done a finite number of times.

Proof/Sketch: Split the graph into components( say there $k$ components). Note that the number of vertices is increasing while the number of edges is decreasing. Moreover, the connectedness is preserved. Now, for any component, eventually, after a good amount of time, we will just have a tree. And the move can't be done, ending the process.  

 

Problem2: Determine the minimum and maximum value of $\chi(G)+\chi(\bar{G})$ over all graphs $G$ on $100$ vertices.

Proof: The minimum is $20$ and the maximum is $100+1=101$.

For the minimality, assume, we have a graph $Y$ and say $\chi(Y)+\chi(\bar{Y})$ for this graph $Y$ is the minimum. Note that if we have two vertices in $Y$ which is not addjacent and are of different colour, we can simply make an edge between them and $\chi(Y)$ is not changed, whereas $\chi(\bar{Y})$ is not increased. And we can keep doing this till we get cliques.

So say $v_1\le v_2\le \dots v_k$ be the $k-$cliques partition of graph $Y$. Here we have $v_1+\dots+v_k=100$. So we need to minimize, $k+v_k$. Note that $v_k\ge 100/k$. And by AM-GM. We are done. 

For the maximality, we use induction. For $n=1$ it is true. For $n=2$ it is true.

Say it's true from $k$ vertices

we wish to show for n+1 vertices 

Well, add for any graph $G$ with $n$ vertices, say $v_1,\dots,v_n$, we will add a new vertex $v$. Now we know that $\chi(G+v)+\chi(G'+v)\le n+2$. So we need to show, that adding a new vertex would not affect in atleast one graph, and by induction we will be done. 

Suppose not, then, $\chi(G+v)=\chi(G)+1$, and $\chi(G'+v)=\chi(G)+1$ and $\chi(G+v)+\chi(G'+v)=n+3\implies \chi(G)+\chi(G')=n+1$.

Well for the vertice $v$, we consider the adjacents vertices. Let $d$ be the degree of $v$ in $G$, then degree of $v$ in $G'$ is $n-d$. Now, note that either $d\le \chi(G)$ or $n-d\le \chi(G')$, then we are done. But this must be true.

Extremal Problems/Greedy Algorithms

References:

• Algorithms Pset by Abhay Bestrapalli
• Algorithms by Cody Johnson
• Rushil Mathur's Greed is good OMC lecture

Here I noticed taking the maximum possible set/minimum possible set satisfying the particular property and then we do bounds. 

Problem1: Suppose $4951$ distinct points in the plane are given such that no four points are collinear. Show that it is possible to select $100$ of the points for which no three points are collinear.

Proof: Consider the maximal set $S$ satisfying this property. If $|S|>100$, they yey we are done. If not, note that since it is the maximal set, any point outside this set is collinear to the two points from set $S$. But no $4$ points are collinear. So every point outside set $S$ is determined by a unique line from set $S$. That is $$4951-n\le \binom{n}{2}\implies n+\binom{n}{2}\ge 4951\implies n\ge 100.$$ Done.

Process

Problem1[Putnam 1979]: Let $A$ be a set of $2n$ points in the plane, no three of which are collinear. Suppose that $n$ of them are colored red and the remaining $n$ blue. Prove or disprove: there are $n$ closed straight line segments, no two with a point in common, such that the endpoints of each segment are points of $A$ having different colors.

Proof: Well, consider a random colouring. Now, whenever there is a problem, just swap it. Note that by this the total number of distances decreases. Assume that there are two segments $R_1B_1$ and $R_2 B_2$  and $R_1B_2\cap B_1R_2=P$.Then by the triangle inequality,

$$R_1B_2 + R_2 B_1 < R_1P + PB_2 + R_2P + PB_1 = R_1P + PB_1 + R_2P+PB_2 = R_1B_1 + R_2 B_2.$$ So swapping decreases the sum of segments. This cannot go on forever.  (why?)

Problem2: Let $p_1, p_2, ..., p_{1997}$ be distinct points in the plane. Connect the points with the line segments $p_1p_2, p_2p_3, p_3p_4\dots, p_{1996}p_{1997}, p_{1997}p_1$ . Can one draw a line that passes through the interior of every one of these segments?

Proof: The answer is obviously no. Suppose not. Then there exist such a line. Then note that the line would divide the plane into two parts. And for every segment, one endpoint will be in one plane and the other endpoint in the other plane. But since there is odd number of points, this is not possible. 

Theorem[Sylvester Gallai]: There are $n$ points in the plane, not all collinear. Prove that there exists a line passing through exactly $2$ points.

Proof: https://en.wikipedia.org/wiki/Sylvester%E2%80%93Gallai_theorem

P.S. The introduction of perpendicular lengths is just so so so brilliant!