IMO Shortlist 2013, Combinatorics #3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

127 posts

#1 h Jul 9, 2014, 5:16 PM • 19 Y

Y by anantmudgal09, Davi-8191, tenplusten, Amir Hossein, MathPassionForever, RudraRockstar, 554183, centslordm, CaptainLevi16, megarnie, lneis1, mathleticguyyy, Aopamy, Adventure10, thdnder, and 4 other users

A crazy physicist discovered a new kind of particle wich he called an imon, after some of them mysteriously appeared in his lab. Some pairs of imons in the lab can be entangled, and each imon can participate in many entanglement relations. The physicist has found a way to perform the following two kinds of operations with these particles, one operation at a time.
(i) If some imon is entangled with an odd number of other imons in the lab, then the physicist can destroy it.
(ii) At any moment, he may double the whole family of imons in the lab by creating a copy $I'$ of each imon $I$ . During this procedure, the two copies $I'$ and $J'$ become entangled if and only if the original imons $I$ and $J$ are entangled, and each copy $I'$ becomes entangled with its original imon $I$ ; no other entanglements occur or disappear at this moment.

Prove that the physicist may apply a sequence of such operations resulting in a family of imons, no two of which are entangled.

This post has been edited 1 time. Last edited by elitza, Jun 16, 2022, 7:49 AM
Reason: Fixed typo.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IvanS

5 posts

IvanS

#2 h Jul 9, 2014, 7:29 PM • 25 Y

Y by Uagu, plwseven, msinghal, toto1234567890, Dark-hero, MathbugAOPS, sa2001, rmtf1111, Kobayashi, asv, qubatae, Siddharth03, mathleticguyyy, test20, FishHeadTail, Aopamy, Adventure10, Mango247, and 7 other users

Consider the graph $G$ with imons as vertices and an edge between two vertices if the imons are entangled.

We will show that using operations (i) and (ii) we can transform $G$ into a graph with strictly smaller chromatic number. The problem follows from this, since a graph with chromatic number $1$ has no edges.

Let $k$ be the chromatic number of $G$ . First we remove vertices of odd degree using operation (i) until there are no vertices of odd degree, to get a graph $H$ . Since $H$ is a subgraph of $G$ , the chromatic number of $H$ is at most $k$ . So there is a partition $S_1,\ldots, S_k$ of the vertex set of $H$ into independent sets (we say that a $S\subset H$ is independent if, for every pair of vertices $v,w\in S$ , $v$ and $w$ are not neighbours. Some of the $S_i$ may be empty).

Now we use operation (ii). We identify the vertex set of the resulting graph $K$ with $H\times \{0,1\}$ in the obvious way ( $I$ is $(I,0)$ and $I'$ is $(I,1)$ ) . Since every vertex of $H$ has even degree, every vertex of $K$ has odd degree. Now if $1\leq i\leq k$ we define $T_i= (S_i\times \{0\}) \cup (S_{i+1}\times \{1\})$ . It is easy to check that $T_1,\ldots, T_k$ gives a coloring of $K$ with $k$ colors. But now we notice that since $T_k$ is independent and every vertex of $T_k$ has odd degree, we may remove every vertex of $T_k$ , one by one, using operation (i). Now the resulting graph $L$ has a $(k-1)$ -coloring, so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AnonymousBunny

339 posts

AnonymousBunny

#3 h Jul 10, 2014, 6:17 AM • 8 Y

Y by Adventure10, Mango247, and 6 other users

Let $n$ be the number of imons in the lab.

We induct on $n.$ The base case is trivial. Suppose our assumption holds for $1, 2, \cdots , n-1, n.$ We need to show that if the particle accelerator of the crazy physicist produces a new imon, he will still be able to get an arrangement where no two imons are entangled. If the new imon is entangled with an odd number of imons, we can delete it and the result follows by the induction hypothesis. In fact if any of the imons is entangled with an odd number of imons, it can be deleted. Also, if any of the imons is entangled with no other imon, the desired result follows from applying the induction hypothesis on the remaining $n$ imons. So we assume all the imons are entangled with an even number of imons and no imon is isolated.

Consider a graph with $n+1$ vertices $\{i_1, i_2, \cdots , i_n, i_{n+1}\}$ where each $i_m$ stands for an imon. Two vertices are connected iff their corresponding imons are entangled. By our assumption, all vertices of this graph have an even number of vertices and no vertex is isolated. By this well known result we can partition $\{i_1, i_2, \cdots , i_n\}$ into (not necessarily non-empty) sets $\mathcal{S}_1, \mathcal{S}_2, \cdots , \mathcal{S}_{n}, \mathcal{S}_{n+1}$ such that no two vertices of $\mathcal{S}_m$ are connected.

Now, suppose the crazy physicist duplicates the imons. For all $m\leq n+1$ , a $m$ -clique is defined as the set formed by joining the vertices of $\mathcal{S}_m$ and the duplicate vertices of $\mathcal{S}_{m-1}$ (the indices are taken modulo $n+1$ ). Note that all cliques are mutually disjoint. Since all vertices in $\mathcal{S}_m$ are included in the $m$ -clique and all duplicate vertices of $\mathcal{S}_m$ are included in the $m+1$ -clique, these cliques partition the graph. Consider any imon $i$ in a $m$ -clique. It is connected to its duplicate, which is not in the $m$ -clique, and an even number of other imons, none of which are in the $m$ -clique. We can remove this imon. This keeps the degree of all other imons in the $m$ -clique unchanged. We can remove an entire non-empty clique by this process, so there are $n$ cliques remaining now. The result follows from the induction hypothesis. $\blacksquare$

EDIT: Oops as pointed out by chaotic_iak below the last line makes no sense at all. Gotta think about this more.

This post has been edited 1 time. Last edited by AnonymousBunny, Jul 10, 2014, 3:46 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

chaotic_iak

2932 posts

chaotic_iak

#4 h Jul 10, 2014, 8:42 AM • 5 Y

Y by AnonymousBunny, Adventure10, and 3 other users

Your induction inducts on the number of imons, but you invoke the induction hypothesis on the number of "cliques" at the end. I don't see how it is valid. (Also, what you call a clique is effectively a coloring of the vertices, which becomes pretty much identical with IvanS' solution above.)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MellowMelon

5850 posts

MellowMelon

#5 h Jul 10, 2014, 8:01 PM • 23 Y

Y by TheStrangeCharm, Particle, Eray, Dukejukem, Delray, Dark-hero, Wizard_32, anantmudgal09, sa2001, qubatae, mueller.25, mathleticguyyy, karitoshi, Modesti, CaptainLevi16, FishHeadTail, Leo890, Adventure10, and 5 other users

We'll go by strong induction on the number of vertices $n$ . Base case $n = 1$ is obvious. Suppose we have an $n$ -vertex graph. If any vertices have odd degree, remove it and use the inductive hypothesis. If all vertices have degree 0, we're already done.

Otherwise, all vertices have even degree, and we have to double the graph. Let the copy of a vertex $v$ in the original be $v'$ . All vertices of our doubled graph have odd degree. Start by arbitrarily deleting vertices from the original graph until we can't delete anymore. Let $S$ be the set of the remaining vertices of the original graph.

Case 1: $S$ is empty (we got rid of the entire original). Undo the last delete of a vertex, $v$ . Delete $v$ 's copy $v'$ instead. $v$ is now an isolated vertex, so we can effectively ignore it and apply the inductive hypothesis to the $n-1$ vertices that remain.

Case 2: $S$ is nonempty. Each $v \in S$ currently has even degree, while the paired vertex $v'$ still has odd degree. We'll say $v \in S$ is strange if its degree plus the degree of its copy is odd. Initially, $S$ has all strange vertices. Now perform the following algorithm.
1. Choose a strange vertex $v \in S$ not yet deleted.
2a. If $v$ has odd degree, then $v'$ has even degree. Remove $v$ , then remove $v'$ .
2b. If $v$ has even degree, then $v'$ has odd degree. Remove $v'$ , then remove $v$ .
3. Notice that the degrees of all remaining vertices in $S$ have changed by the same amount as their copies, so any strange vertices are still strange.
4. Go back to step 1.
It's easy to see that all vertices of $S$ will be strange each time we get to step 1, so we'll in fact be able to delete all of them and their copies by this procedure. The end result is that we've removed $n + |S|$ vertices. Since $S$ is nonempty, the inductive hypothesis finishes the problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math_explorer

583 posts

math_explorer

#6 h Jul 12, 2014, 1:13 AM • 4 Y

Y by Adventure10, Mango247, and 2 other users

Call a configuration of imons solvable if there is a sequence of operations that results in a family of imons, no two of which are entangled. Here's another way to induct, first with a

Lemma. If configuration $A$ is solvable, then the configuration $B$ obtained from doubling $A$ twice is also solvable.

Proof. First map the sequence of operations on $A$ to a sequence of operations on $B$ as follows:

Each doubling of $A$ becomes a doubling of $B$ .
Each deletion of imon $v$ in $A$ becomes a deletion of the four imons that $v$ was doubled into, in the order $v_{11}, v_{22}, v_{12}, v_{21}$ .

Note that after each step, we maintain the relationship that $B$ is obtained from doubling $A$ twice. In the second item, we assume these doublings turned $v$ into $v_1, v_2$ and $v_i$ into $v_{i1}, v_{i2}$ , so that $v_{ij}$ and $v_{k\ell}$ are entangled iff $i = k$ or $j = \ell$ . As a result, one can verify that $v_{11}$ and $v_{22}$ had 2 more entanglement relations in $B$ than $v$ did in $A$ , and that after their deletions $v_{12}$ and $v_{21}$ had the same number of entanglement relations in $B$ as $v$ did in $A$ , so if $v$ can be destroyed then the above deletions can be carried out as well.

At the end, $A$ is a bunch of unentangled imons, which means $B$ is a bunch of 4-cycles. ~~Now just delete two non-adjacent imons from each 4-cycle.~~ edit: Wait, that's not how you delete 4-cycles =_= Double $B$ one last time to get a bunch of cubes, then delete a set of 4 vertices, no two adjacent, in each cube.

-- end lemma --

With the lemma, it's an easy induction on the number of vertices.

Consider a configuration $A$ . If any vertex has an odd number of entanglement relations, delete it and induct. Otherwise, if we're not done, choose two imons $v$ and $w$ which are entangled; both have an even number of entanglement relations. Double $A$ once so $v \to v_{1,2}, w \to w_{1,2}$ , delete $v_1, w_2, v_2, w_1$ in that order, and double again; this is doable because $v_1, w_2$ would have 1 more entanglement than $v, w$ had, and $v_2, w_1$ would have 1 less, so all of these deletions are of imons with an odd number of entanglement relations. Furthermore, it produces a configuration $B$ that is the result of doubling { $A$ sans imons $v, w$ } twice. By induction, the configuration { $A$ sans imons $v, w$ } is solvable, so by the lemma, $B$ is solvable, so $A$ is solvable.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

superpi83

1416 posts

superpi83

#7 h Jul 12, 2014, 11:00 PM • 6 Y

Y by Adventure10, Mango247, and 4 other users

Represent the imons and entanglements by a graph, in which imons are vertices and entanglements are edges.

Call operation (ii) "stacking." For a graph $G$ and a nonnegative integer $k$ , define the " $k^\text{th}$ stack of $G$ " to be the graph consisting of $2^k$ copies of $G$ , labeled $G_s$ as $s$ ranges over all binary strings of length $k$ such that corresponding vertices in two copies $G_s$ and $G_{s'}$ are adjacent if and only if $s$ and $s'$ differ in exactly one bit. It is clear that stacking $G$ $k$ times produces the $k^\text{th}$ stack of $G$ .

We claim: for all graphs $G$ , the $k^\text{th}$ stack of $G$ , for any nonnegative integers $k$ , can be reduced by a sequence of operations to an edgeless graph. We use strong induction on the number of edges in $G$ .

Base case: no edges in $G$ . Then all edges in the $k^\text{th}$ stack of $G$ are between different copies of $G$ . If $k$ is even, we can stack the graph once, so assume $k$ odd. Destroy all vertices in all $G_s$ where $s$ has an odd number of 1s. This destroys all edges.

Inductive step: We consider two cases.
Case 1: There is a vertex $i\in G$ with odd degree. If $k$ is odd, we can stack the graph once, so assume $k$ even. Destroy all copies of $i$ in all $G_s$ where $s$ has an odd number of 1s. Then destroy all remaining copies of $i$ . This produces a stack of the graph $G\setminus i$ , which, by the inductive hypothesis, can be reduced to an edgeless graph.
Case 2: All vertices in $G$ have even degree. If $k$ is even, we can stack the graph once, so assume $k$ odd. Let $ij$ be an edge in $G$ . Destroy all copies of $i$ in all $G_s$ where $s$ has an odd number of 1s and all copies of $j$ in all $G_s$ where $s$ has an even number of 1s. Then destroy all remaining copies of $i$ and $j$ . This produces a stack of the graph $G\setminus i, j$ , which, by the inductive hypothesis, can be reduced to an edgeless graph.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

fclvbfm934

759 posts

fclvbfm934

#8 h Aug 2, 2014, 1:39 AM • 4 Y

Y by Delray, Adventure10, Mango247, and 1 other user

Let each imon be a vertex and each entanglement be an edge.

I will use induction on the number of verticies. We can just delete any vertices with an odd degree, so assume that we have a graph $G$ with vertices of all even degree. Suppose there are $n$ vertices. We now use (ii), so now all vertices have odd degree, and we have $G$ and a graph $G'$ , with each vertex in $G$ corresponding to a vertex in $G'$ . Now just remove as many vertices as possible from $G$ , to the point where all the vertices in $G$ are of even degree. Notice that $G'$ at this point is still intact. Suppose the number of vertices in $G$ is still positive, and let vertex $v \in G$ , and let $v'$ be its copy in $G'$ . Clearly, $v'$ still has odd degree. Remove $v'$ , then $v$ . Let $S$ be the set of vertices $v$ was connected to, $S'$ be the set of vertices $v'$ was connected to. Take any vertex $u' \in G'$ ; if $u' \not\in S'$ , then $\deg{(u')}$ is still odd, $\deg{(u)}$ still even. If $u' \in S'$ , then $\deg{(u')}$ is even, and $\deg{(u)}$ is odd. Therefore, for every vertex in $G$ , we can remove. Hence, we end up with the remainder of $G'$ which has less vertices than $G$ .

Now assume that $G$ is empty by the time we cleanse out the odd vertices after we make the copy $G'$ . Then undo last delete, and delete the corresponding vertex in $G'$ instead. Hence, we get a graph of $n-1$ vertices to worry about, completing the induction.

EDIT: this is just basically MellowMelon's solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

randomusername

1059 posts

randomusername

#9 h Sep 11, 2014, 3:49 PM • 1 Y

Y by Adventure10

Click to reveal hidden text

EDIT: this is just superpi's solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathPanda1

1135 posts

MathPanda1

#10 h Oct 9, 2015, 7:27 PM • 2 Y

Y by Adventure10, Mango247

IvanS wrote:

Consider the graph $G$ with imons as vertices and an edge between two vertices if the imons are entangled.

We will show that using operations (i) and (ii) we can transform $G$ into a graph with strictly smaller chromatic number. The problem follows from this, since a graph with chromatic number $1$ has no edges.

MellowMelon wrote:

We'll go by strong induction on the number of vertices $n$ . Base case $n = 1$ is obvious. Suppose we have an $n$ -vertex graph. If any vertices have odd degree, remove it and use the inductive hypothesis. If all vertices have degree 0, we're already done.

Otherwise, all vertices have even degree, and we have to double the graph. Let the copy of a vertex $v$ in the original be $v'$ . All vertices of our doubled graph have odd degree. Start by arbitrarily deleting vertices from the original graph until we can't delete anymore. Let $S$ be the set of the remaining vertices of the original graph.

Case 1: $S$ is empty (we got rid of the entire original). Undo the last delete of a vertex, $v$ . Delete $v$ 's copy $v'$ instead. $v$ is now an isolated vertex, so we can effectively ignore it and apply the inductive hypothesis to the $n-1$ vertices that remain.

Case 2: $S$ is nonempty. Each $v \in S$ currently has even degree, while the paired vertex $v'$ still has odd degree. We'll say $v \in S$ is strange if its degree plus the degree of its copy is odd. Initially, $S$ has all strange vertices. Now perform the following algorithm.
1. Choose a strange vertex $v \in S$ not yet deleted.
2a. If $v$ has odd degree, then $v'$ has even degree. Remove $v$ , then remove $v'$ .
2b. If $v$ has even degree, then $v'$ has odd degree. Remove $v'$ , then remove $v$ .
3. Notice that the degrees of all remaining vertices in $S$ have changed by the same amount as their copies, so any strange vertices are still strange.
4. Go back to step 1.
It's easy to see that all vertices of $S$ will be strange each time we get to step 1, so we'll in fact be able to delete all of them and their copies by this procedure. The end result is that we've removed $n + |S|$ vertices. Since $S$ is nonempty, the inductive hypothesis finishes the problem.

What is the inspiration for choosing the invariant? Is it known to choose the chromatic number?
What is the inspiration for using induction that way?
What is the difficulty of this problem? It looks pretty simple, but looks can be deceiving...
Thank you in advance and look forward to your replies!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathadventurer

54 posts

mathadventurer

#14 h Jan 9, 2018, 12:34 AM • 2 Y

Y by Adventure10, Mango247

Let $T_k$ be the configuration where $(ii)$ is performed $k$ times starting with a single imon particle. Also use a graph to represent imons and their relations.

Lemma For $T_k$ where $k$ is odd, we can find a set $S$ such that we can remove a set $S$ or complement of vertices by $(ii)$ to remove all edges and in $S$ no two of them are entangled; for $k$ even we can perform a series of operations where each time we only remove vertices with even number of entanglement relations to get to an empty graph.
induction
Now start with our graph $L$ . We can think of our graph as a single vertex that's very "big" and then apply the lemma to this really big vertex. In particular, we will show that we can use the lemma so that even though we are duplicating the number of these really big vertices of copies of $L$ , we can make sure that at each time for a vertex/vertices we can delete it/them in all of these copies of $L$ .

Specifically:
Let $N$ be the number of operations $(ii)$ that we made. Note that we'll just speak of $L$ instead of all copies of $L$ since each time all these copies of $L$ are the same by our operation.

$(P):$ If $L$ still has two imons with even entanglements who are entangled with each other, say $I$ and $J$ . Then we continue to perform $(ii)$ until $N$ is odd, we can take the set $S$ as in the lemma and remove copies of $I$ 's in those graphs(copies of $L$ corresponding with vertices in set $S$ ) and copies of $J$ 's in other copies of $L$ . But then after this, all other copies of $I$ 's and $J$ 's have odd degrees and aren't related and we can just remove them.

$(Q):$ On the other hand, if there is a vertex with odd number of entanglements, then do $(ii)$ until $N$ is even. By lemma, we can remove all copies of this vertex in each $L$ (each copy of vertex has an even number of entanglement relations with once vertex from each other copy of $L$ ).

Now we see that inside each of these "very big" vertices, if there is a vertex of odd number of entanglements, we can apply $Q$ and delete this vertex; if there is a vertex of even number of entanglements with at least one neighbor, either some of its neighbors have even entanglements and we can apply $P$ or there is a neighbor with odd number of entanglements and we can again use $Q$ . In the end, we are left with at most one vertex in each of these copies of $L$ . Then we can again apply lemma and be done.

EDIT: oops just realized that I have basically the same sol as superpi83, but superpi's use of binary number made so many things much easier

This post has been edited 1 time. Last edited by mathadventurer, Jan 9, 2018, 1:18 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

conker23

98 posts

conker23

#15 h Jan 24, 2018, 11:45 PM • 1 Y

Y by Adventure10

I know there's already many solutions, but i have one quite different in presentation using two monovariants so I post it.

Call M the maximum degree among all vertices. We'll proceed in two steps :
We remove vertices in any order thanks to (i). Clearly, the number M can only decrease and the algorithm must stop.
When the algorithm stops, all points have an even degree..

Assume all points are not disconnected.
Call G the graph. At this moment, we use (ii) to double the graph. Call G' the copy. The quantity M has of course increased by one. Moreover, the degre of each vertex is odd by now.

We'll show that we can bring back the quantity M+1 to its previous value M and that in the end the number of vertices of degree M we'll have strictly decreased (the second monovariant). Then, the algorithm we'll have to stop with all points disconnected.

To do so, remove vertices of degree M+1 in G in some order until you can't do it anymore. For each vertex removed, the copy in G' has a degree turned to M.
Two cases appear :
First case : You didn't remove all vertex of degree M+1 in G (some just turned to a lower degree). Call $V_1, V_2, ..., V_k$ vertices which are still of degree M in G and $V_1', V_2', ..., V_k'$ their copy in G'. Note that $V_i'$ are all of degre M' (then odd).
In G', remove in some order the $V_i'$ until you can't do it anymore. Save the order in which you've removed these $V_i'$ . Once more, note that for each $V_i'$ removed, the original $V_i$ has a degree exactly M-1, and then is odd.

So in G', the maximum degree of a vertex is M. If you weren't able to remove all $V_i'$ , it means that by removing these $V_i'$ you've reduced the degree of the other $V_i'$ .
In G, once more, remove in the same order the $V_i$ . In the end, every $V_i$ which are left are of degree at most M-1.

Therefore, there's no more vertex in G of degree M and we have removed at least one vertex in G' of degree M, so the quantity of vertices of degree M is strictly lower than before.

2nd case : You've removed all vertices of degree M+1 in G. Then the maximum degree in G is M-1. Then they were pairwise independent. It means that there was other vertices in G (otherwise, they would not have been independent...). Call V a vertex in G which is not of degree M+1 and which shared an edge with a vertex of degree M+1. We remove its copy V' in G' (it's odd, as we didn't remove V in G...). Then we remove as many vertex as possible in G'. As there no more vertex of degree M in G and we have removed at least one vertex of degree M in G', the number of such vertices is strictly less than before and we're done.

This post has been edited 2 times. Last edited by conker23, Jan 24, 2018, 11:46 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

anantmudgal09

1980 posts

anantmudgal09

#16 h Jun 27, 2018, 11:01 AM • 7 Y

Y by Amir Hossein, MathbugAOPS, e_plus_pi, rashah76, RudraRockstar, 554183, Adventure10

lyukhson wrote:

A crazy physicist discovered a new kind of particle wich he called an imon, after some of them mysteriously appeared in his lab. Some pairs of imons in the lab can be entangled, and each imon can participate in many entanglement relations. The physicist has found a way to perform the following two kinds of operations with these particles, one operation at a time.
(i) If some imon is entangled with an odd number of other imons in the lab, then the physicist can destroy it.
(ii) At any moment, he may double the whole family of imons in the lab by creating a copy $I'$ of each imon $I$ . During this procedure, the two copies $I'$ and $J'$ become entangled if and only if the original imons $I$ and $J$ are entangled, and each copy $I'$ becomes entangled with its original imon $I$ ; no other entanglements occur or disappear at this moment.

Prove that the physicist may apply a sequence of much operations resulting in a family of imons, no two of which are entangled.

Apply (i) for as long as possible. If no entanglements remain; we're done. Thus, we reach a stage where each vertex in graph $G$ has an even degree. Copy the graph to get $G'$ so now each vertex in $G \cup G'$ has odd degree. Colour vertices of $G$ with colours $1, 2, \dots, k$ so that originally, no two adjacent vertices shared an edge. The same applies to $G'$ but instead we colour its vertices with $i+1$ whenever corresponding vertex was coloured $i$ (indices mod $k$ ). Suppose $k \ge 2$ (else we're done). Then in $G \cup G'$ ; we remove each vertex with the label $k$ . Notice that now two of these are adjacent so there actions don't affect each other. Thus, the resulting graph can be coloured with $k-1$ colours. Applying this idea repeatedly; we eventually obtain a graph $H$ with chromatic number $k=1$ . Then $H$ has no entanglements as desired. $\blacksquare$

This post has been edited 1 time. Last edited by anantmudgal09, Jun 27, 2018, 11:02 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math_pi_rate

1218 posts

math_pi_rate

#17 h Apr 22, 2019, 6:38 PM • 1 Y

Y by Adventure10

Wow! Nice problem!! Here's my solution: Obviously consider the problem in graph theoretic terms. We call a graph $\mathcal{H}$ to be an even sub-graph of $\mathcal{G}$ if it is formed by deleting vertices with odd degree (for as long as we can) in $\mathcal{G}$ , i.e. an even sub-graph has only vertices with even degree. We show that we can get to the edge-less graph using operation $(ii)$ at most $\chi(G)$ times (where $\chi(G)$ represents the chromatic number of $G$ ). Using operation $(i)$ on the given graph $\mathcal{G}$ , get to its even sub-graph. Since it's a sub-graph, so its chromatic number cannot exceed that of $\mathcal{G}$ . Now apply operation $(ii)$ on this even sub-graph (call it $\mathcal{H}$ ) to get a copy $\mathcal{H'}$ . Color the graph $\mathcal(H)$ using $C_1,C_2, \dots ,C_r$ , where $2 \leq r \leq \chi(G)$ (when $r=1$ , we are done). Also color corresponding vertex in $\mathcal{H'}$ of a vertex with color $C_i$ (in $\mathcal{H}$ ) with the color $C_{n+1-i}$ . Then the graph $\mathcal{H} \cup \mathcal{H'}$ , with each vertex having an odd degree, has been colored using colors $C_1,C_2, \dots ,C_r$ such that no two vertices of same color are adjacent.

Now consider the graph $\mathcal{H}$ , and delete all vertices of color $C_1$ in this graph. We can do so since no two such vertices are adjacent, and so deletion of any vertex of this color does not affect the state (i.e. whether its degree is odd or even) of another vertex of this color. We can do the same thing in the graph $\mathcal{H'}$ , and delete all vertices of color $C_1$ , since no vertex of same color are common in $\mathcal{H}$ and $\mathcal{H'}$ (which means that deletion of one doesn't affect the degree of another). In the end, we're left with a graph with chromatic number $r-1$ , and so we have succeeded in decreasing the chromatic number of the graph $\mathcal{G}$ using the stated operation. Applying this process again and again, we get to a graph with chromatic number $1$ , which is nothing but an edge-less graph. Hence, done. $\blacksquare$

REMARKS: The main difficulty of the problem lies in characterizing the end state, since the problem makes it pretty clear that either an inductive proof can be done, or some mono-variant can be used. Fortunately I didn't go along the first route this time (as I usually do

). Anyway, the only characterization of the edge-less graphs, that I was aware of, was that it's chromatic number is one. Then the proof seemed pretty obvious, and I was able to complete it quite early as compared to the usual time I take for a combi problem

.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yayups

1614 posts

yayups

#18 h Dec 23, 2019, 4:51 AM • 5 Y

Y by aops29, parola, Adventure10, Mango247, winniep008hfi

We use the obvious graph theory interpretation. Let $f(G)$ be the new graph we get after applying operation (ii). We have the following key lemma.

Lemma: If $G$ has an edge, we have $\chi(f(G))=\chi(G)$ where $\chi(H)$ is the chromatic number of $H$ .

Proof: Clearly $\chi(f(G))\ge\chi(G)$ as $G$ is a subgraph of $f(G)$ . It suffices to present a coloring on $f(G)$ with $\chi(G)$ colors. The way we do this is we color $G$ with $\chi(G)$ colors, and color the copy of $G$ with those same colors, but permuted in such a way that the permutation has no fixed points. This works, and completes the proof of the lemma. $\blacksquare$

We solve the original problem by induction on $\chi(G)$ . When $\chi(G)=1$ , then there are no edges, so we are done. So suppose that $\chi(G)\ge 2$ . Apply operation (i) repeatedly until either the chromatic number has decreased, in which case we're done, or all the degrees of $G$ are even but the chromatic number is the same. So WLOG, suppose $G$ has all even degrees. Now, $f(G)$ is a graph with all odd degrees, and chromatic number $\chi(G)$ . We can simply apply operation (i) to all vertices of a particular color (this works since they form an independent set), and we now have a graph with a lower chromatic number. This completes the induction, and thus the solution.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SnowPanda

186 posts

SnowPanda

#19 h Nov 25, 2020, 5:38 AM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GeronimoStilton

1521 posts

GeronimoStilton

#21 h Mar 28, 2021, 12:07 AM • 2 Y

Y by Mango247, Mango247

This isn't too bad because I memorized the approach. The idea is to monotonically decrease the chromatic number at each step of the algorithm below.

Delete vertices with odd degree until no such vertices remain: this can only decrease the chromatic number.
Remark we are done if the chromatic number is at most $1$ , otherwise the chromatic number is $k\ge 2$ . Hence we can partition the graph into exactly $k\ge2$ independent sets.
Apply the second operation, then delete one of the independent sets in one copy of the graph $G$ and another of the independent sets in a different copy of $G$ . We can choose the colorings of the independent sets in such a way that this deletion ends up coloring $G$ with just $k-1$ colors.

This algorithm suffices, yay.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ali3085

214 posts

Ali3085

#22 h Aug 11, 2021, 1:44 PM • 2 Y

Y by Muaaz.SY, FishHeadTail

a beautiful problem..
I'll use the obvious graph rephrasing.
Now if we can disconnect the graph via these two operations we'll call it weak.
we'll prove that all simple graphs are weak. induct on $n$ the number of vertices in $G$
denote $G'$ the clone of $G$ after doubling
the main claim: if $G$ is weak then so is $G^*$ (the graph obtained from doubling ou $G$ )
proof:
double $G^*$ to get $G^{**}$ . now destroy $G$ and $G^{*'}$ then destroy $G^*,G'$
$\blacksquare$
suppose it's true for $1,2,\dots n$
and take a graph with $n+1$ vertices. if one of its vertices has an odd degree we're done,
suppose not. then just double it and take two adjacent vertices $v_1,v_2$ and their clones $v_1',v_2'$
firstly, delete $v_1,v_2'$ and then $v_1',v_2$ and to get doubled graph with $2n-4$ vertices but from the main claim
as we can destroy any graph of $n-2$ vertices we can destroy any doubled graph with $2n-4$ vertices

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sprites

478 posts

Sprites

#23 h Oct 22, 2021, 10:21 AM

Y by

lyukhson wrote:

A crazy physicist discovered a new kind of particle wich he called an imon, after some of them mysteriously appeared in his lab. Some pairs of imons in the lab can be entangled, and each imon can participate in many entanglement relations. The physicist has found a way to perform the following two kinds of operations with these particles, one operation at a time.
(i) If some imon is entangled with an odd number of other imons in the lab, then the physicist can destroy it.
(ii) At any moment, he may double the whole family of imons in the lab by creating a copy $I'$ of each imon $I$ . During this procedure, the two copies $I'$ and $J'$ become entangled if and only if the original imons $I$ and $J$ are entangled, and each copy $I'$ becomes entangled with its original imon $I$ ; no other entanglements occur or disappear at this moment.

Prove that the physicist may apply a sequence of much operations resulting in a family of imons, no two of which are entangled.

Algorithm:-
$\;\;\; \bullet$ Keep applying operation $1$ as long as it is possible.
$\;\;\; \bullet$ Assume that $\chi(G)=k>1$ (consider the graph theoretic rephrasation.)
$\;\;\; \bullet$ Apply the second operation, then delete one of the independent sets in one copy of the graph $G$ and another of the independent sets in a different copy of $G$ . We can choose the colorings of the independent sets in such a way that this deletion ends up coloring $G$ with just $k-1$ colors i.e $\chi(G)$ decreases monotonically. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1711 posts

awesomeming327.

#24 h Jun 16, 2022, 3:10 AM

Y by

Overkill.

We proceed with induction on the number of imons at the start.

Base Case:
If there is one imon there cannot be any entanglement relations.

Induction Hypothesis
Suppose that for any amount of imons less than $n$ we can always remove all the entanglements.

Induction Step
Let there be $n$ imons. If there is any imon involved in an odd number of entanglements then we remove this imon, thus reducing the problem to having $n-1$ imons. By the induction hypothesis, we are done.

Suppose that each imon is involved in an even number of entanglements. Then, we duplicate the imons, so that each imon is involved with an odd number of entanglements. Call the original imons Gen $0$ and the duplicated imons Gen $1.$

We start by destroying imons in Gen $0$ until it is impossible to destroy any more. If we can destroy all the imons in Gen $0$ , then leave one imon alive. Delete the copy of this imon. Since the only imon in Gen $0$ will have no entanglements, we don't need to consider this one. There are $n-1$ imons left so we are done by the hypothesis.

Now, suppose there are at least two imons left in Gen $0$ , all of them with even number of entanglements. Consider the pair of imons $I$ in Gen $0$ and its copy $I'$ in Gen $1.$ We claim that we can delete all of the pairs.

First, pick any of the pairs, and we may delete $I'$ , because no imons entangled to $I'$ was removed. Then, $I$ has odd number of entanglments so we may delete $I$ as well. We do this to pairs until we can't. Note that each pair we remove, every pair $I,I'$ has either $I,I'$ unaffected or $I,I'$ both affected once. Thus, the parity of the number of entanglements of $I$ and $I'$ are always opposite, so as long as $I$ has an even number of entanglements, $I'$ has an odd number.

Now, we delete the pairs as describe previously, until we can't do this anymore. Now, all the imons $I$ have odd degree, so we delete imon $I$ , and then we can destroy $I'$ and then we do this operation until we can't. We repeat this until we cannot keep repeating. At this point, all the imons in Gen $0$ have both odd degree and even degree, which means there are no more imons in Gen $0.$ We deleted at least $2$ pairs, so there are at most $n-2$ imons left. By the induction hypothesis, we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

L567

1184 posts

L567

#25 h Jun 16, 2022, 7:09 AM • 4 Y

Y by lneis1, Periwinkle27, mxlcv, Mango247

Solved with Periwinkle27

Take the natural graph theoretic interpretation and induct on the chromatic number of the graph. Suppose currently it is $k$ and let the groups $g_1,g_2, \cdots, g_k$ of vertices have colors $c_1, c_2, \cdots, c_k$ respectively. If any vertex has odd degree, delete it by operation (i) until its not possible anymore, clearly this cannot increase the chromatic number. Now, use operation (ii) to double the graph and let the copy of group $g_i$ have color $c_{i+1}$ so that the coloring is still valid. Now, every vertex has odd degree, so delete all vertices in $g_k$ one by one, which is possible since deleting one does not affect the degree of any other vertex in that group. So now the chromatic number of the graph is at most $k - 1$ so we're done by the induction hypothesis. Eventually we reach chromatic number $1$ , which is an independent set, which is what the problem asks for, so we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5001 posts

IAmTheHazard

#26 h Sep 6, 2022, 2:24 PM

Y by

Wrong for now, know how to fix but will write up later

Edit: never mind, I'm not sure this is salvageable. My original idea was that you can prove that if we start out with some odd degree vertex and delete them such that we will not delete a vertex such that every remaining vertex has even degree unless we have to, we will get a complete graph with even vertices, since in brief every connected component with an odd degree vertex must have all odd degree vertices and be complete if we can't delete an odd degree vertex in that connected component. The issue is that this relies on the graph remaining connected. If we disconnect the graph, the issue is that one of the connected components could possibly end up having no odd degree vertices but also not being complete, so we can't be sure that the process will ever terminate with all complete graphs.

This post has been edited 5 times. Last edited by IAmTheHazard, Sep 12, 2022, 3:45 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Inconsistent

1455 posts

Inconsistent

#28 h Oct 5, 2022, 7:02 PM

Y by

$\mathcal{X}$

Strictly decrease it. After each iteration remove until all vertices have even degree. Color the original, derange the colors in the copy, and remove any color. $\blacksquare$

This post has been edited 1 time. Last edited by Inconsistent, Oct 5, 2022, 7:03 PM
Reason: edit

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

blackbluecar

302 posts

blackbluecar

#29 h Jan 28, 2023, 2:56 AM • 1 Y

Y by kamatadu

Lmao this problem is actually pretty funny. Call the obvious graph $G$ . Let $c(G)$ denote the graph after the copying operation is applied. We will now outline a working strategy.

Step 1: Greedily remove vertices from $G$ . We can do this until all vertices have even degree

Step 2: Replace $G$ with $c(G)$ , notice that $\chi (G) = \chi (c(G))$ because we can apply the same coloring to both copies of $G$ and shift the coloring of one of the $G$ ’s.

Step 3: Now, every vertex of $G$ has odd degree. Now choose a color of $G$ and remove all vertices of that color. We can do this since none of them are connected. This strictly reduces the chromatic number.

Back to step 1…

We strictly reduce the chromatic number each time. So, we will eventually get a chromatic number $1$ . This implies all edges are deleted

This post has been edited 1 time. Last edited by blackbluecar, Jan 28, 2023, 2:58 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

thdnder

197 posts

thdnder

#30 h Sep 22, 2023, 12:13 PM • 1 Y

Y by TheHU-1729

I think the induction solution is more easy to see.

We'll induct on number of vertices. Base case is clear. Now assume it's true on all graphs with number of vertices $\leq n - 1$ . If some vertex has odd degree, we can erase it and apply induction hypothesis on remaining graph. Thus we can assume all vertex $v$ , $\deg v$ is even.Let $G = (V,E)$ . Replacing $G$ to $G \mathop{\square} K_2$ , every vertex in $G \mathop{\square} K_2$ has odd degree now, where $G'$ is the other copy of $G$ in $G \mathop{\square} K_2$ . Delete all odd degree vertices from $G$ until there is no odd degree vertices in $G$ . Let $H$ be set of remaining vertices

If $H$ is empty, then undo the last delete of a vertex, $v$ . Delete $v$ 's copy $v'$ instead. $v$ is now an isolated vertex, so we can effectively ignore it and apply the inductive hypothesis to the $n-1$ vertices that remain.

Then for all vertices $v \in H$ , $\deg v'$ is odd, where $v' \in G'$ which is adjacent to $v$ and if $v$ is erased, then $\deg v'$ is even. Call a vertex $v \in H$ is good if $\deg v + \deg v'$ is odd. Then all vertices in $H$ is good. Now perform the following algorithm:

Choose a good vertex $v \in H$ that not yet deleted. If $\deg v$ is even, erase $v'$ , otherwise erase $v$ . Note that for all for $u \in H$ , $\deg u, \deg u'$ have changed the same amount as their copies, so if $u$ is good, then $u$ is still good. Then this algorithm doesn't terminate until $H$ becomes empty. Now applying the induction hypothesis on the remaining graph. We're done. $\blacksquare$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

signifance

140 posts

signifance

#31 h Oct 25, 2023, 5:27 AM

Y by

Proceed by induction on number of imons, base case n=1 trivial. Assume the inductive hypothesis for k=n, we prove it for n+1. Call the original imons in a set O and new imons in a set N, and by minimality assume all imons in O have even degree, now duplicate. Because all imons have odd degree, remove as many imons as you can, again by minimality you have at least two imons in O left (otherwise leave 1 imon I in O, then delete I' the duplicate, and I has degree 0 so it's inductive hypothesis n). The key is that all imons in N that have their O version left all have odd degree, while the O version has even degree, and the opposite parity is preserved throughout moves: If I,I' remain, delete the one with odd, then the one with even now has odd, so now delete that one; in particular, if a J was not affected then neither was J', so still opposite parity, while if J was affected so is J', still opposite parity. Now we can keep reducing the imons in O in this way (even in O means odd respective in N, and vice versa), until we get 1 imon, done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megarnie

5603 posts

megarnie

#32 h Jan 2, 2024, 7:10 AM

Y by

When we perform the operation $G \square K_2$ , the chromatic number stays the same. Now we claim that we can always decrease the chromatic number of $G$ if it isn't an empty graph. The way to do this is to delete vertices until all degrees are even, and clearly the chromatic number isn't changed. Now, we can perform the duplicating operation. After this, each vertex has odd degree and removing a vertex doesn't affect the degree of anything not adjacent to it. Hence we can delete a full color, and the chromatic number is decreased.

Motivation

This post has been edited 3 times. Last edited by megarnie, Jan 2, 2024, 7:12 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

YaoAOPS

1538 posts

YaoAOPS

#33 h Jan 12, 2024, 8:59 PM

Y by

This is correct till someone tells me what was wrong.

WLOG assume $G$ has no odd degree vertices.
Then double $G$ to get $G \cup G'$ . Then if $a, b, a', b'$ have even degree, then we can delete in order $a, b', a', b$ to get rid of an edge.

Claim: We can delete cycles.
Proof. Even cycles can be deleted by doing the above operation to every other edge in the cycle.
Odd cycles are the same but delete not alternating edges. $\blacksquare$
If deleting a cycle leaves some vertex $v$ unconnected, we can delete $v$ and $v'$ .
Now, delete cycles till acyclic, leaving a tree. We can then delete the leaves of trees until done.

This post has been edited 1 time. Last edited by YaoAOPS, Jan 12, 2024, 9:04 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

N3bula

268 posts

N3bula

#34 h Jan 3, 2025, 8:03 AM

Y by

Consider the graph colouring clearly we have that $\chi(G)$ is finite. Clearly the cartesian product does not increase $\chi(G)$ , thus play until all vertices
in $G$ have even degree. Take the cartesian product. Thus every vertice has odd degree. Now we can remove all vertices that are coloured the same colour for one specific
colour. Than we can remove every odd vertice until we have only even degree vertices. By repeating this process we eventually reach a point where $\chi(G)=1$
which suffices.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2534 posts

joshualiu315

#35 h Jan 26, 2025, 6:03 AM

Y by

Convert the problem to graph theory, where imons are vertices and an edge between vertices indicates entanglement. Let $G'$ be the result of $G$ under the second operation. Finally, let $\chi(G)$ be the chromatic number of $G$ . We perform the following operation:

Remove vertices until it is no longer possible.
Create $G'$ and color the vertices in the copy identical to $G$ but shifted; all the vertices in $G'$ have odd degree.
Remove all the vertices of one color, and then repeat.

This algorithm strictly decreases $\chi(G)$ , so we may repeat it until we have $\chi(G) = 1$ , which implies an edgeless graph. $\blacksquare$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

john0512

4186 posts

john0512

#36 h Feb 25, 2025, 1:43 AM

Y by

Assume the graph has only even degrees. That the following process strictly decreases the chromatic number (assuming it is at least 2).

Assign an $n$ -coloring to the graph. Perform the copy operation, and assigning to the second copy a derangement of the same colors (thus not changing the chromatic number). Then, since all vertices have odd degree, remove the entirety of one color (possible since the removals do not affect each other). Then, keep making arbitrary moves until all degrees are even again.

Thus we can eventually get to a chromatic number of $1$ , done.

remark: I played around with a lot of examples and eventually realized that bipartite graphs immediately go away. This is the $n=2$ case of the above process, and the generalization to this still works.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

575 posts

Maximilian113

#37 h Apr 23, 2025, 11:34 PM

Y by

WAY TOO OVERKILL SOLUTION AND BAD WRITEUP: View the problem as a graph theory one. Let $X$ denote the operation of arbitrarily removing odd degree vertices until there are only even degree vertices on a certain graph.

Let $G$ be the original graph, WLOG assume that all vertices have even degree as otherwise we can apply $X.$ Now, duplicate $G$ to get $G \cap C',$ then all vertices have odd degree. Now consider in $G$ an odd-degree vertex, call it $a.$ If there is another odd-degree vertex connected to it, $b$ then we can remove $a, b', a', b$ in that order. Meanwhile if there is no odd-degree vertex connected to it, let $b$ be an even-degree vertex. Then we can do $a, b, a', b'.$

Repeating those operations we are now left with $G, G'$ each having vertices of only even degree.

Now duplicate the configuration and rename the graphs to $G_{(\pm 1, \pm 1)},$ such that two are connected if and only if their subscripts differ in exactly one place. Clearly all vertices have odd degree. Apply $X$ to $G_{(1, 1)}$ and $G_{(-1, -1)}$ on the same configuration of points. Then apply it to $G_{(1, -1)}, G_{(-1, 1)}.$ Now all vertices have even degree and duplicating again we can continue the process.

The process works since after $n$ duplications you can imagine each copy of $G$ as a vertice of an $n$ -dimensional hypercube. If $n$ is even we can simply apply $X$ to half the vertices (which represent copies of $G$ ) such that no two vertices are adjacent, and then apply $X$ to the other half (and this works as every vertice has an even amount of adjacent vertices). Then every vertice has even degree, and then duplicate to get higher dimensions.
If $n$ is odd however, find adjacent vertice pairs, and pair these pairs with pair of points opposite the the points of the original pair (opposite with respect to the hypercube). (to do this find an alternating coloring (which is not hard) for an $n-1$ -dimension hypercube, duplicate this, and correspond them to find the pairs). Then take half of the pairs so that no two of the pairs are adjacent, then we can apply the algorithm from the second paragraph on each of these pairs (and the second paragraph algorithm must be operated IDENTICALLY for each pair). Finally do the same on the other half or pairs, so every vertice now has an even degree. Then duplicate to get higher dimensions.

It is clear that after doing the above, the number of vertices in each copy of $G$ is strictly decreasing. But the algorithm relies on the fact that there are is at least one edge on each copy of $G.$ So we will be left with multiple copies of some $n$ -dimensional hypercube with each of its vertices being an actual vertex. Then do the following algorithm on them:

If $n$ is odd take a $2$ -coloring and take out all vertices of one color and then we will be left with no edges.
If $n$ is even duplicate everything to obtain the same number of $n+1$ -dimensional hypercubes, and do the above.

Hence after this we will be done. QED

Z K Y