A spider built a web on the unit circle. The web is a planar graph with straight edges inside the circle, bounded by the circumference of the circle. Each vertex of the graph lying on the circle belongs to a unique edge, which goes perpendicularly inward to the circle. For each vertex of the graph inside the circle, the sum of the unit outgoing vectors along the edges of the graph is zero. Prove that the total length of the web is equal to the number of its vertices on the circle.
Problem
Source: Russian TST 2018, Day 8 P3 (Group NG); thank you, Fedor Bakharev, for the translation
Tags: combinatorics, graph theory, vector geometry, physics
oVlad
01.04.2023 12:22
Just to clarify some things related to the statement: For each vertex $v$ on the circle, the unique edge is simply a segment of the line joining $v$ and the center of the circle. For each $v$ inside the circle, the unit vectors "leaving" from $v$ on the rays determined by the edges of $v$, have sum zero. Here's an example of a web of total length six, which indeed corresponds to the number of vertices on the circumference: [asy][asy] import olympiad; import geometry; dot(dir(0)); dot(dir(60)); dot(dir(120)); dot(dir(180)); dot(dir(240)); dot(dir(300)); dot(dir(0)*4/7); dot(dir(60)*4/7); dot(dir(120)*4/7); dot(dir(180)*4/7); dot(dir(240)*4/7); dot(dir(300)*4/7); draw(dir(0)*4/7--dir(60)*4/7--dir(120)*4/7--dir(180)*4/7--dir(240)*4/7--dir(300)*4/7--cycle); draw(dir(0)--dir(0)*4/7); draw(dir(60)--dir(60)*4/7); draw(dir(120)--dir(120)*4/7); draw(dir(180)--dir(180)*4/7); draw(dir(240)--dir(240)*4/7); draw(dir(300)--dir(300)*4/7); draw(unitcircle); [/asy][/asy]
starchan
05.04.2023 18:19
this solution was discovered with mxlcv, and blessed by Atul, because there is a little of Atul in all of us morgan freeman wrote: along came a spider...
Let there be $n$ vertices strictly inside the circle, called $P_1, P_2, \dots, P_n$. Suppose there are $m$ vertices on the circle. Let $G$ denote the planar graph with edge set $e(G)$ and vertex set $v(G)$. As usual, for a vertice $u$ the notation $N(u)$ denotes the neighbour set of $u$. Let the centre of the unit circle be $O$. Suppose $\hat{n}_{uv}$ denotes the unit vector directed from vertex $P_u \mapsto P_v$. We assign each vertex $P_i$ a velocity $V_i$ whose direction is always towards $O$ and of arbitrary magnitude (at least for now). Consider the location of the points after some time $t$. We define $g(t)$ as the sum of all web lengths in this new structure. Observe that the points on the circle do not move, or that they have velocity zero. Observe that $g$ is obviously differentiable. We show that $g'(0) = 0$. To this, first observe that \[2g(t) = \sum_{u \in v(G)} \sum_{v \in N(u)} \bar{P}_u(t) - \bar{P}_v(t)\]and so \[2g'(0) = \sum_{u \in v(G)} \sum_{v \in N(u)} (V_u - V_v) \cdot \hat{n}_{uv}\]Using the constraint that for all vertices $u$ we have $\sum_{v \in N(u)} \hat{n}_{uv} = 0$, the above some is easily seen to be zero, in particular $g'(0) = 0$. Now, the idea is to set appropriate velocities $V_i$ so that the unit vector conditions holds at all points in time. For this, we set each $V_i$'s magnitude to $OP_i$. This means that once $t = 1$ all the vertices inside the circle will reach the origin, and for any $0 < t < 1$, the structure will be homothetic to the original structure about the centre $O$ (except for the vertices on the circle, of course). Define $g(t)$ for these set of velocities as before. Now the idea is that for all $0 \leq t < 1$ the unit vector condition holds and so $g'(t) = 0$. In particular, $g$ is constant. Now observe that $g(1) = m$ as all the vertices inside the circle have degenerated at $O$ whereas the $m$ points on the circle are each connected to $O$ contributing a total length of $m$. Hence $g(0) = m$, which is precisely what we wanted to show.
gvole
08.06.2024 18:21
I was thinking of a solution with a physical system, but couldn't figure it out as I'm no physicist. Namely, if you model the problem as a bunch of pipes and some ideal gas or fluid inside the pipes (or current flowing through wires), then you have that the center of mass of the matter inside the pipes stays the same, while some change happens on the endpoints. For example, you can put candlesticks on the edges and let them burn. The center of mass of one stick moves by 1 so the total work done should be proportional to the total length of pipes, heuristically speaking (the center of mass of matter in the pipes stays the same while the center of mass of matter inside a candlestick at one point moves with constant velocity). You could also play with an ideal gas and a vacuum outside the pipes and calculate some pressures and forces using ideal gas law. Another possible approach is modelling with strings or springs and some weights. If anyone can solve it using these ideas I would be delighted.
cosmicgenius
09.06.2024 05:54
Here's a physics solution in the spirit of the above: Let each pair of vertices connected by an edge attract each other with a force of $1$ Newton, and furthermore, apply an external force of $1$ Newton radially outward to every vertex on the circle. It is not hard to see that the conditions imply that the vertices are at mechanical equilibrium. Furthermore, the forces, except for the external forces, can be modeled by a central conservative force (separate for each pair) with potential given by the distance between two interacting vertices. Thus, by the virial theorem, we have \[ 0 = 1 \cdot V - \sum_v \mathbf{F_v} \cdot \mathbf{r_v}, \]where $V$ is the total potential of the system, and $\mathbf{F_v}$ and $\mathbf{r_v}$ are the external force on and position of vertex $v$, respectively, for each $v$. But it is easy to see that $V$ is the total length of the edges, and, setting the center of the circle to be the origin, $\mathbf{F_v} \cdot \mathbf{r_v}$ is the indicator function of the vertices on the circle. $\blacksquare$
gvole
09.06.2024 06:03
@above username checks out.
gvole
09.06.2024 19:18
Here's a redemption solution. Connect edges with springs so that the force on each spring is equal, and also add strings on the boundary pulling radially out (the same setup as above).The conditions tell us that the system is at equilibrium. Now pull on the outside strings until everything is stretched out by $1+\epsilon$. The work done is $n\cdot R\cdot F \cdot \epsilon$ and the potential energy changes by $\ell \cdot F\cdot \epsilon$.