Skip to main content

Combinatorial Games and Processes

Heya!!! I am Debayu, just got into 10th grade, have been doing olympiad math for a year now, and have really enjoyed it so far!! I also play a lot of football and am in my school football team also recently I have been learning about machine learning and stuff and it's really fun!! In this blog post, I am gonna walk you through some nice and instructive problems involving combinatorial processes and games which I personally really like so hope you enjoy it!!

One common theme among problems involving processes and games is looking for some invariant or monovariant but often people end up blatantly chasing for invariants and monovariants only to realize that there doesn't exist one and even if it does its not natural. In this blog post we will emphasize more on understanding the process well in general and then make some observations to do stuff, sometimes looking at equality cases will help too. 

Problem 1(USAMO 1997 P4): To clip a convex $n$-gon means to choose a pair of consecutive sides $AB, BC$ and to replace them by the three segments, and $NC$, where $M$ is the midpoint of $AB$ and $N$ is the midpoint of $BC$. In other words, one cuts off the triangle $MBN$ to obtain a convex $(n+1)$-gon. A regular hexagon ${\cal P}_6$ of area 1 is clipped to obtain a heptagon ${\cal P}_7$. Then ${\cal P}_7$ is clipped (in one of the seven possible ways) to obtain an octagon ${\cal P}_8$, and so on. Prove that no matter how the clippings are done, the area of ${\cal P}_n$ is greater than $\frac 13$, for all $n \geq 6$.

Walkthrough: The result is quite surprising! Its basically saying that the area never 
gets smaller than one-third of the original area of the hexagon!! Infact the bound can be improved till $\frac{2}{3}$!

    (a) Play with the problem for a while, do you observe something? Does someparticular area of the hexagon never get removed?

    (b) Try to formally define the region whose area never gets deleted.

    (c) Does the fact that we have midpoints suggest something? Finish the proof with this.

Solution: Let ABCDEF be our hexagon and let  $\mathcal H$ be the hexagon formed by the points $AC \cap BF, AE \cap BF, DF \cap AE, CE \cap DF, BD \cap CE$ and $AC \cap BD$. We claim that the area of $\mathcal H$ is always preserved. Now take the triangle $ABC$, recursively keep drawing edges in the following way:
 
(i) First draw the midpoints $M$ and $N$ of $AB$ and $BC$ respectively, and join them.

(ii) Then draw the midpoints $K$ and $L$ of $AM$ and $MN$ respectively, and join them and keep doing this. 

Notice that none of the edges go past $AC$ because otherwise, one point of the segments that are being recursively formed would go past $AC$ too which is a contradiction since they must be inside triangle $ABC$. $\blacksquare$


Remark: The motivation behind defining the hexagon is pretty clear from the walkthrough, often in such combo geo problems, it's nice to divide shapes in some way to restrict the activity. Here, after playing with the problem for a while, one shall notice that an inner chunk never gets deleted so it is natural to introduce some diagonals to see if they help. For the stronger $\frac{2}{3}$ bound, one can prove that the area of the hexagon formed by the centroids of $\bigtriangleup  ABF, \bigtriangleup AFE, \bigtriangleup FED, \bigtriangleup EDC, \bigtriangleup BCD$ never gets deleted. The proof is slightly trickier but not too hard if you know the proof for the weaker bound and also it turns out to have appeared in 2010 Cono Sur Olympiad.

Problem 2(USAMO 2021 P2): The Planar National Park is a subset of the Euclidean plane consisting of several trails which meet at junctions. Every trail has its two endpoints at two different junctions whereas each junction is the endpoint of exactly three trails. Trails only intersect at junctions (in particular, trails only meet at endpoints). Finally, no trails begin and end at the same two junctions. (An example of one possible layout of the park is shown to the left below, in which there are six junctions and nine trails.)
https://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvZS9mLzc1YmNjN2YxMWZhZTNhMTVkZTQ4NWE1ZDIyMDNhN2I5NzY0NTBlLnBuZw==&rn=Z3JhcGguUE5H
A visitor walks through the park as follows: she begins at a junction and starts walking along a trail. At the end of that first trail, she enters a junction and turns left. On the next junction she turns right, and so on, alternating left and right turns at each junction. She does this until she gets back to the junction where she started. What is the largest possible number of times she could have entered any junction during her walk, over all possible layouts of the park?

Walkthrough: Throughout the problem, we will refer to the junctions as vertices and the trails as edges. Notice that we have $3$- regular planar graph(it just means that every vertex has degree 3 and no two edges physically intersect each other) here. First of all, I will just clarify how we are defining left and right. Suppose the visitor walks from $v_1 \mapsto v_2$ at the beginning and now she has two options, either she goes to $v_3$ or $v_4$(the one which is on the left). Fix the vertex $v_2$ and rotate the edge $v_2v_1$ in a clockwise manner around it, the first edge that is hit out of $v_2v_3$ and $v_2v_4$ is left and the other one is right.  Also, we are ignoring graphs with infinite loops, you will soon realize what I mean by this.

    (i) Do you think the answer is dependent upon the number of edges or vertices?

    (ii) Play with it for some time and think what's the answer, and try out all kinds of $3$-regular planar graphs. If you are stuck on some certain number and think you can't improve it then try to find(probably just intuitively and not rigorously) why(also note the construction you get). Also, the construction is not easy so don't feel bad about it if you don't find it.

    (iii) Find a nice way to interpret the problem in terms of how many times the visitor is repeating vertices.(This step is probably not very important but it kind of simplifies things, you can obviously solve the problem with the original thing)

    (iv) Prove that the visitor can't visit two vertices $v_i \mapsto v_j$ twice in the same orientation i.e. if she can't travel to $v_j$ both the times with a left turn/right turn.

    (v) Find another observation that will kill the problem and finish it (Hint: Look at what happens when both the walks $v_i \mapsto v_j$ and $v_j \mapsto v_i$ take place.)

Solution: We claim that the maximum number of times a vertex can be repeated is 3. We draw arrows on the edges every time the visitor passes through it. We will prove that a single edge in its neighborhood cant have more than $4$ arrows on it. First, notice that she can't walk her way from $v_i \mapsto v_i$ twice taking the same turn. Now,
Claim: She can't walk $a \mapsto b \mapsto c$ and $c\mapsto b \mapsto a$  in the same direction.
Proof: FTSOC, suppose she can do this, then the path wlog looks like this,
$$a(L) \mapsto b(R) \mapsto c(L) \mapsto v_1(R) \mapsto \cdots \mapsto v_1(R) \mapsto c(L)  \mapsto b(R) \mapsto a(L)$$
where $\alpha(R)$ basically means that the visitor takes a right turn from some vertex $\alpha$, the same follows for $\alpha(L)$ and we get a clear contradiction when these two chains meet in the middle because it forces $X \mapsto X$ or $X \mapsto Y \mapsto X$ for some two vertices. $\blacksquare$
This clearly restricts the number of arrows to be less than $8$, so the maximum number of repeated vertices possible is $3$. Now for the construction, we take the figure below and start from any vertex of the inner pentagon. $\blacksquare$



Remark: I really feel that the construction of the problem is harder than the bound so don't be demotivated if it took you a lot of time to find it. People had loads of different kinds of constructions, some of which were very complex and some were really sus, and by that I mean literally.

  Credits: Mira74 on AoPS
The proof for the bound is imo more natural and not too hard after one really understands what's going on, this is the main spirit of these problems! A problem of similar taste is probably USA TSTST 2017 P2, that's an exercise for you to do!!

Problem 3(2015 C4): Let $n$ be a positive integer. Two players $A$ and $B$ play a game in which they take turns choosing positive integers $k \le n$. The rules of the game are:

(i) A player cannot choose a number that has been chosen by either player on any previous turn.
(ii) A player cannot choose a number consecutive to any of those the player has already chosen on any previous turn.
(iii) The game is a draw if all numbers have been chosen; otherwise, the player who cannot choose a number anymore loses the game.

The player $A$ takes the first turn. Determine the outcome of the game, assuming that both players use optimal strategies.

Walkthrough: Lol actually I blatantly misread the problem and since I am nice and don't like seeing other people smacking their heads, I will just emphasize on the fact that here "consecutive" means both the successor and predecessor of the number i,e if you have 7 then both 6 and 8 are accounted. Also, we will denote $A$ and $B$ as Frisk and Sans because why not :P

    (i) Try small cases and figure out what the answer is? Did you get that Sans wins for all odd $n$ except $1$ and the rest are draws? Yayy!! or wait ermm

    (ii) Try big numbers now, yes I am not kidding.

    (iii) Prove that Sans can't lose.

    (iv) It seems hard to prove that Sans has a winning strategy so instead what can we do? Think what happens to the other player when Sans wins.

Solution: We claim that the game is a draw for $n=1, 2, 4 \text{ and } 6$ and Sans wins every other time. The drawing cases can be checked by hand. We begin with the following claim:
Claim: Sans can never lose.
Proof: WLOG, we assume that Frisk picks a number $\leq \frac{n+1}{2}$. On the very first move of Sans, he just picks $n$. Now, Sans can just always pick a number between two numbers picked by Frisk which is always possible, and therefore Sans always has a number to pick. $\blacksquare$.

Now, we prove that Frisk can never draw the game for $n \geq 8$. Like in the previous claim, WLOG, we assume that Frisk picks a number $\leq \frac{n+1}{2}$ and Sans picks $n$. Now if $n$ is odd and $>1$, notice that Frisk has to pick all the odd numbers since he needs to pick at least $\frac{n+1}{2}$ numbers which is impossible since Sans picked $n$ already. If $n$ is even and $\geq 8$, say Frisk picks some odd number,, then Sans picks $n$ and then since Frisk has to pick at least $\frac{n}{2}$ numbers, he must pick another odd, and after that Sans can just pick another odd to spoil his strategy, a similar reasoning follows when Sans picks an even. $\blacksquare$

Remark: This problem makes you realize how important it is to work with a sufficient number of small cases and not just be lazy and do the first few small numbers. I personally check a lot of small cases in general and for some reason when I was gsolving with Himadri I just thought mehh the answer must be that evens make up for a draw, and then I ended up chasing for the wrong answer for some hours. After that, I thought I should check a few more cases to understand what's happening better and I realize Sans wins for big $n$!! The original proof I found was actually very long and tedious which is kind of similar to the one I provided here which is really clever. The motivation for proving Frisk can't draw instead of finding a winning strategy for Sans is just realizing that it's very hard to get a direct strategy for Sans to win because a lot of very random things seem to work.

Problem 4(Canada 2019 P5): Let G be an empty graph (i.e. no edges) on n \geq 3 vertices. David and Jacob alternate adding edges to the graph G, with David first; a player who creates a cycle of odd length in G loses. For each n, determine which player has a winning strategy.

Walkthrough: You need to know a little graph theory for this problem, a quick reading from Otis Excerpts should do the job. This walkthrough will be rather short because this problem is extremely nice and I don't want to spoil it a bit, I recommend you to try it yourself first.

    (i) As always, play with the problem for a while, get a feel of what's happening and determine who is winning for which $n$.
    
    (ii) So we don't want odd cycles, what kind of graphs don't have any odd cycles? Try to use this fact.

    (iii) Before making the move that makes the odd cycle, notice that the graph is always bipartite, and look at the two vertex sets of the partitions.

Solution: We claim that David wins when $n \equiv 2 \pmod{4}$ else Jacob wins. When $n$ is odd, notice that before creating an odd cycle, the graph must be bipartite. Let the vertex sets of the two partitions be $A$ and $B$. Now, one of them of $|A|$ and $|B|$ must be even so optimally, $|A||B|$ turns can be made which forces David to make an odd cycle. Now we deal with the case when $4|n$. We perform a $2$-coloring on the graph. Note that we might switch the coloring while in play according to the edges drawn as it doesn't matter. Now, we claim that at any point, Jacob can force $|A|=|B|$. There are two cases possible, either David had disrupted the equilibrium of the two partitions or he had retained the equilibrium in the previous move. In the first case, Jacob can just connect the isolated vertex which was connected by David to another isolated vertex and this is clearly possible since $n$ is even, otherwise David couldn't have made his move in the first place. In the second case, David connects two isolated vertices or two previously connected vertices.
This forces a bipartite graph with $|A|=|B|=\frac{n}{2}=\text{ even}$ which forces David to make an odd cycle. David does the same when $n \equiv 2 \pmod{4}$ and forces a bipartite graph with $|A|=|B|=\frac{n}{2}=\text{ odd}$ which forces Jacob to make an odd cycle. $\blacksquare$

Here are some problems for you to try!!

Problem 1(2005 C1): A house has an even number of lamps distributed among its rooms in such a way that there are at least three lamps in every room. Each lamp shares a switch with exactly one other lamp, not necessarily from the same room. Each change in the switch shared by two lamps changes their states simultaneously. Prove that for every initial state of the lamps there exists a sequence of changes in some of the switches at the end of which each room contains lamps which are on as well as lamps which are off.

Problem 2(2016 A2): Find the smallest constant $C > 0$ for which the following statement holds: among any five positive real numbers $a_1,a_2,a_3,a_4,a_5$ (not necessarily distinct), one can always choose distinct subscripts $i,j,k,l$ such that
\[ \left| \frac{a_i}{a_j} - \frac {a_k}{a_l} \right| \le C. \]

Problem 3(China TST 2003): There is a frog in every vertex of a regular 2n-gon with circumcircle($n \geq 2$). At certain time, all frogs jump to the neighborhood vertices simultaneously (There can be more than one frog in one vertex). We call it as $\textsl{a way of jump}$. It turns out that there is $\textsl{a way of jump}$ with respect to 2n-gon, such that the line connecting any two distinct vertice having frogs on it after the jump, does not pass through the circumcentre of the 2n-gon. Find all possible values of $n$.

Problem 4(USAMTS 4/1/32): Two beasts, Rosencrans and Gildenstern, play a game. They have a circle with $n$ points ($n \ge 5$) on it. On their turn, each beast (starting with Rosencrans) draws a chord between a pair of points in such a way that any two chords have a shared point. (The chords either intersect or have a common endpoint.) For example, two potential legal moves for the second player are drawn below with dotted lines.
[asy]
unitsize(0.7cm);
draw(circle((0,0),1));
dot((0,-1));
pair A = (-1/2,-(sqrt(3))/2);
dot(A);
pair B = ((sqrt(2))/2,-(sqrt(2))/2);
dot(B);
pair C = ((sqrt(3))/2,1/2);
dot(C);
draw(A--C);
pair D = (-(sqrt(0.05)),sqrt(0.95));
dot(D);
pair E = (-(sqrt(0.2)),sqrt(0.8));
dot(E);
draw(B--E,dotted);
draw(C--D,dotted);
[/asy]
The game ends when a player cannot draw a chord. The last beast to draw a chord wins. For which $n$ does Rosencrans win? Note: You can assume optimal from both of them.

Problem 5(2011 C5): Let $m$ be a positive integer, and consider a $m\times m$ checkerboard consisting of unit squares. At the centre of some of these unit squares there is an ant. At time $0$, each ant starts moving with speed $1$ parallel to some edge of the checkerboard. When two ants moving in the opposite directions meet, they both turn $90^{\circ}$ clockwise and continue moving with speed $1$. When more than $2$ ants meet, or when two ants moving in perpendicular directions meet, the ants continue moving in the same direction as before they met. When an ant reaches one of the edges of the checkerboard, it falls off and will not re-appear.

Considering all possible starting positions, determine the latest possible moment at which the last ant falls off the checkerboard, or prove that such a moment does not necessarily exist.

Problem 6(ToT Fall-2015 S-A7): $N$ children no two of the same height stand in a line. The following two-step procedure is applied: first, the line is split into the least possible number of groups so that in each group all children are arranged from the left to the right in ascending order of their heights (a group may consist of a single child). Second, the order of children in each group is reversed, so now in each group the children stand in descending order of their heights. Prove that in result of applying this procedure $N - 1$ times the children in the line would stand from the left to the right in descending order of their heights.


I really hope you enjoyed this, this was actually my first blogpost ever and I thoroughly enjoyed it myself, and do tell me if you find any errors or typo. Thank you!!!!!
       

Comments

Post a Comment

Popular posts from this blog

The importance of "intuition" in geometry

Hii everyone! Today I will be discussing a few geometry problems in which once you "guess" or "claim" the important things, then the problem can easily be finished using not-so-fancy techniques (e.g. angle chasing, power-of-point etc. Sometimes you would want to use inversion or projective geometry but once you have figured out that some particular synthetic property should hold, the finish shouldn't be that non trivial) This post stresses more about intuition rather than being rigorous. When I did these problems myself, I used freehand diagrams (not geogebra or ruler/compass) because I feel that gives a lot more freedom to you. By freedom, I mean, the power to guess. To elaborate on this - Suppose you drew a perfect  diagram on paper using ruler and compass, then you would be too rigid on what is true in the diagram which you drew. But sometimes that might just be a coincidence. e.g. Let's say a question says $D$ is a random point on segment $BC$, so maybe

LMAO Revenge

Continuing the tradition of past years, our seniors at the Indian IMO camp(an unofficial one happened this year) once again conducted LMAO, essentially ELMO but Indian. Sadly, only those who were in the unofficial IMOTC conducted by Pranav, Atul, Sunaina, Gunjan and others could participate in that. We all were super excited for the problems but I ended up not really trying the problems because of school things and stuff yet I solved problem 1 or so did I think. Problem 1:  There is a   grid of real numbers. In a move, you can pick any real number  ,  and any row or column and replace every entry   in it with  .  Is it possible to reach any grid from any other by a finite sequence of such moves? It turned out that I fakesolved and oh my god I was so disgusted, no way this proof could be false and then when I was asked Atul, it turns out that even my answer was wrong and he didn't even read the proof, this made me even more angry and guess what? I was not alone, Krutarth too fakesol

Edge querying in graph theory

In this post, I will present three graph theory problems in increasing difficulty, each with a common theme that one would determine a property of an edge in a complete graph through repeated iterations, and seek to achieve a greater objective. ESPR Summer Program Application: Alice and Bob play the following game on a $K_n$ ($n\ge 3$): initially all edges are uncolored, and each turn, Alice chooses an uncolored edge then Bob chooses to color it red or blue. The game ends when any vertex is adjacent to $n-1$ red edges, or when every edge is colored; Bob wins if and only if both condition holds at that time. Devise a winning strategy for Bob. This is more of a warm-up to the post, since it has a different flavor from the other two problems, and isn't as demanding in terms of experience with combinatorics. However, do note that when this problem was first presented, applicants did not know the winner ahead of time; it would be difficult to believe that Bob can hold such a strong