This problem is pretty fun.

hint 1

hint 2

SpecialBeing2017 wrote: This problem is pretty fun.

hint 1

hint 2

Hint 1 is clear. Hint 2 seems more interesting, but I still can't see how to finish. May you post a sketch of how to proceed after that? Thanks.

It can be proved by using Euler's theorem of plane graph and referring to the method of proving Greenberg's condition Modesti wrote: SpecialBeing2017 wrote: This problem is pretty fun.

hint 1

hint 2

Hint 1 is clear. Hint 2 seems more interesting, but I still can't see how to finish. May you post a sketch of how to proceed after that? Thanks.

Yonko wrote: It can be proved by using Euler's theorem of plane graph and referring to the method of proving Greenberg's condition But Greenberg's condition really helps? Because the number of faces inside and outside the ant's cycle is always the same, and we don't know yet if the cycle is Hamiltonian. Also, I don't see how can we put "turning right" and "turning left" in graphical theoretic terms.

Modesti wrote: Yonko wrote: It can be proved by using Euler's theorem of plane graph and referring to the method of proving Greenberg's condition But Greenberg's condition really helps? Because the number of faces inside and outside the ant's cycle is always the same, and we don't know yet if the cycle is Hamiltonian. Also, I don't see how can we put "turning right" and "turning left" in graphical theoretic terms. No, no, no, that's not what I mean. I mean to prove it the same way we proved Greenberg's condition. Yes, it doesn't have to be Hamiltonian, but we can prove that the inner and outer polygons are equal

Let's define a function that indicates the direction of each vertex $V$ on a non self intersecting cycle $C$: $$f(V, C):\begin{cases} 1 & \text{if the vertex }V\text{ is a left turn} \\ 0 & \text{if the vertex }V\text{ is not on the cycle }C \\ -1 & \text{if the vertex }V\text{ is a right turn} \end{cases}$$Let $X_C$ be the sum of all $f(V, C)$ for each vertex $V$ on $P$ while $C$ is a non self intersecting cycle on $P$. Let $S_{C,1}$ and $S_{C,2}$ be the two sets of faces of two sides of $C$. Let $U_C$ be the set of numbers of sides of faces in $S_{C,1}$ and let $V_C=\{y_1, y_2, \cdots, y_l\}$ be the set of numbers of sides of faces in $S_{C,2}$. Lemma. For any non self intersecting cycle $C$, one of the following holds. $$X_C=6+\sum_{i\in U_C}(i-6)=-\left(6+\sum_{i\in V_C}(i-6)\right)$$or $$X_C=-\left(6+\sum_{i\in U_C}(i-6)\right)=6+\sum_{i\in V_C}(i-6)$$ Proof. We use mathematical induction for $|S_{C,1}|$ and $|S_{C,2}|$. Let's start with the first one. Base case is $|S_{C,1}|=1$ which means $|S_{C,1}|$ consists of only one face, say $F_1$ which has $x_1$ sides. $X_C$ is $x_1$ or $-x_1$, WLOG assume the first one. For $|S_{C,2}|$, this sign will change. In induction step, we will show each additional face $F$ having $x$ sides added to $|S_{C,1}|$ will increase $X_C$ by $x-6$. Assume the vertices belonging to both $|S_{C,1}|$ and the newly added face $F$ are $V_1,V_2,\cdots,V_s$. For all consecutive vertices $V_j$ and $V_{j+1}$, other side of this segment is a different face than others. Therefore, $\{f(V_i,C):1\leq i\leq s\}$ is $\{1,-1,-1,-1,\cdots,-1,-1,1\}$ before the new face is added. After $F$ is added, it becomes $\{-1,0,0,0,\cdots,0,0,-1\}$. This will increase $X_C$ by $-2+(s-2)-2=s-6$. Other vertices of face $F$ will rise from 0 to 1, thereby bringing $x-s$ to $X_C$. These two sets of vertices together increase $X_C$ by $(s-6)+(x-s)=x-6$. For the other part, each face added to $|S_{C,2}|$ will conversely decrease $X_C$. Problem statement says that sets $S_{C,1}$ and $S_{C,2}$ are the same. Therefore, $U_C=V_C$ and $$6+\sum_{i\in U_C}(i-6)=6+\sum_{i\in V_C}(i-6)$$Combined with the lemma, this gives that $X_C=0$ which means that the number of left turns and the number of right turns are the same.

Here is a translation of the official solution. On a sad note, this and P4 are the only problems I couldn't solve, and this destroyed my combinatorics 2/5 streak of twelve problems. Consider the two parts of the polyhedron. They are planar. They have the same number of edges and they have the same number of faces. By Euler's characteristic, they have the same number of vertices and "inner angles". Suppose turning left gives the first side 1 "inner angle" and the second side "inner angles", then turning right gives the first side 2 "inner angles" and second side 1 "inner angle". The end. P.S. I hope Specialbeing would post his solution. His solution seems to be extremely innovative.

Solved with: Eric Shen, Kevin Wu, Ryan Yang, Alan Bu, Chris Qiu, and Elliott Liu

Attachments:

Unfortunately this is not as impressive as the above solution. Solved with Alan Bu, Christopher Qiu, Elliott Liu, Jeffrey Chen, Kevin Wu, and Ryan Yang. Let the cycle \(\mathcal C\) split the planar graph into subgraphs \(G_1\) and \(G_2\). Say a boundary vertex is one that lies on \(\mathcal C\), and let an interior vertex be a vertex not on \(\mathcal C\). Say a boundary edge is one that is incident to a boundary vertex. We are given \(G_1\) and \(G_2\) have the same number faces and edges, so they have the same number of vertices by Euler's characteristic. Observe that in both \(G_1\) and \(G_2\), \[\#\text{edges}=\frac{3\cdot\#\text{interior vertices}+\#\text{boundary edges}}2.\]Since \(G_1\) and \(G_2\) have the same number of edges and interior vertices, they have the same number of boundary edges. But a boundary edge in \(G_1\) corresponds with a left turn (without loss of generality), and a boundary edge in \(G_2\) corresponds with a right turn. Thus we are done.

You can solve it easy in considering the amount of left-point and right-point

Here is my solution: https://calimath.org/pdf/CNO2020-5.pdf And I uploaded the solution with motivation to: https://youtu.be/hJbpCTd_jTU

This elegant problem is proposed by Yijun Yao. However, it is very tricky during contest and have low average point. Let $P$ be a polyhedron divided into two parts, $A$ and $B$, by a path $L.$ Suppose $A$ and $B$ have $a$ and $b$ vertices, respectively. Suppose path $L$ has $c$ vertices on one face of $A$ and $d$ vertices on two faces of $A.$ Then $L$ has $d$ vertices on two faces of $B$ and $c$ vertices on one face of B. Note that as an ant crawls along $L,$ the number of times it turns left is $c$ and the number of times it turns right is $d.$ Therefore, we need only prove that $c=d.$ Let $n_k$ be the number of $k$-sided faces in $A$ and $B.$ Then, $$3a+c+2d= \sum_{k}n_k=3b+2c+d.$$Therefore $3(a-b)=c-d.$ Applying Euler's formula to $A$ and $B,$ we get $$2\sum_{k}n_k+2(a+c+d)-2=3a+2c+3d$$and $$2\sum_{k}n_k+2(b+c+d)-2=3b+2d+3c$$Subtracting these two equations, we get $a-b=c-d.$ Combining the two equations, we get $c=d.\Box$