Geometric Give and Take J.T. supported by Charles Univ. projects UNCE 24/SCI/008 and PRIMUS 24/SCI/012, and by GAČR project 25-17221S. Oswin Aichholzer, Katharina Klost, Kristin Knorr, Viola Mészáros, Josef Tkadlec Abstract We consider a special, geometric case of a balancing game introduced by Spencer in 1977. Consider any arrangement ℒ \mathcal{L} of n n lines in the plane, and assume that each cell of the arrangement contains a box. Alice initially places pebbles in each box. In each subsequent step, Bob picks a line, and Alice must choose a side of that line, remove one pebble from each box on that side, and add one pebble to each box on the other side. Bob wins if any box ever becomes empty. We determine the minimum number f ⁡ ( ℒ ) f(\mathcal{L}) of pebbles, computable in polynomial time, for which Alice can prevent Bob from ever winning, and we show that f ⁡ ( ℒ ) = Θ ⁡ ( n 3 ) f(\mathcal{L})=\Theta(n^{3}) for any arrangement ℒ \mathcal{L} of n n lines in general position. Graz University of Technology oswin.aichholzer@tugraz.at Freie Universität Berlin and Universität Tübingenkathklost@inf.fu-berlin.de Freie Universität Berlinknorrkri@inf.fu-berlin.de Bolyai Institute, University of Szeged meszaros.viola@gmail.com Charles Universityjosef.tkadlec@iuuk.mff.cuni.cz \crefname claimClaimClaims \Crefname claimClaimClaims ccs Theory of computation Computational geometry keywords Line Arrangements, Geometric Games † † runningtitle: Geometric Give and Take † † runningauthor: O. Aichholzer, K. Klost, K. Knorr, V. Mészáros and J. Tkadlec † † copyright: Oswin Aichholzer, Katharina Klost, Kristin Knorr, Viola Mészáros and Josef Tkadlec † † articleno: 100 1 Introduction Inspired by the following game that appeared in the shortlist of problems for the International Math Olympiad in 2019 [ 4 ] , we consider a special case of the balancing game introduced by Spencer [ 6 ] in 1977. The game [ 4 ] is played with n boxes that are placed in a row and each box can contain a number of pebbles. There are two players: Alice and Bob. Initially, Alice places p_{i} pebbles into box i . Then the game proceeds in rounds: In each round, first Bob picks a line \ell_{i} with 1\leq iP . We also define a total order on the set of all pebble distributions, by considering the lexicographic order on the lists [p(b_{1}),p(b_{2}),\dots,p(b_{R})] . We write p\prec_{L}p^{\prime} if p is before p^{\prime} in the lexicographic ordering. Bob’s strategy proceeds in stages. Let p be the pebble distribution before a stage and p^{\prime} be the pebble distribution at the end of the stage. We show that after each stage one of the following holds: 1. Bob wins, that is, there is a box b with p^{\prime}(b)=0 2. The total number of pebbles decreases or p^{\prime}\prec_{L}p . Since the second situation can only happen finitely many times, Bob will win. At the beginning of each stage, we have Pc_{\ell_{i+1}} and the statement follows. (iii) This follows from the same argument as (ii), using that c_{\ell_{i}}=c_{\ell_{i+1}} . (iv) Consider the pebble distributions p and p^{\prime} before and after the green pair respectively and let B_{i} , B_{i+1} be the sets of boxes on the smaller sides determined by \ell_{i} , \ell_{i+1} , respectively. The net effect of decreasing \ell_{i} and increasing \ell_{i+1} is that each box b\in B_{i}\setminus B_{i+1} loses two pebbles, and each box b^{\prime}\in B_{i+1}\setminus B_{i} gains two pebbles. Since the lines \ell_{i} , \ell_{i+1} have the same rank (and are different), we have |B_{i}\setminus B_{i+1}|=|B_{i+1}\setminus B_{i}|>0 , and thanks to the ordering by characteristic vectors we get p^{\prime}\prec_{L}p . \claimqedhere Figure 3: Illustrations for the three cases which correspond to (1) Alice decreasing \ell_{A} (left); (2) Alice increasing \ell_{1} (middle); and (3) Alice never decreasing \ell_{A} and never increasing \ell_{1} (right). Next, we argue that Bob wins in a finite number of steps. We distinguish 3 cases, depending on what happens in a stage. (1) Alice decreases \ell_{A} Let p be the initial pebble distribution of the stage. Each decrease of a line that is still on the stack removes one pebble from b . Furthermore, by \cref claim:pairs (i) no pair changes the number of pebbles in b . At the beginning of the stage there were p(\textbf{b})\leq p_{a}(\textbf{b})-1=A pebbles in b and each decrease on the A lines on the stack removed a pebble. Thus, b is now empty and Bob wins. (2) Alice increases \ell_{1} Let p be the initial pebble distribution of this stage and p’ be the pebble distribution after the stage. We show that in this case, the total number of pebbles decreased or p^{\prime}\prec_{L}p . By \cref claim:pairs (ii) and (iii) , red pairs decrease the total number of pebbles, green pairs do not change it. After Alice increases \ell_{1} , the stack is empty, and thus the number of pebbles did not increase in this stage. Thus, if there is a red pair or \ell_{1} has rank strictly less than R/2 , then increasing \ell_{1} decreases the total number of pebbles. In the other case, all pairs are green and \ell_{1} has order exactly R/2 . In that case, the effect of increasing \ell_{1} and by \cref claim:pairs (iv) the effect of any green pair is to decrease the pebble distribution with regard to \prec_{L} . In particular, b_{1} is on the larger side of \ell_{1} by definition and thus increasing \ell_{1} decreases the number of pebbles in the most significant position. If follows that p^{\prime}\prec_{L}p as claimed. As the total number of pebbles is still smaller than X , Bob can ignore all previous moves, pick a new focal box and start a new stage. Since the number of pebbles and the lexicographical ordering of the pebble distribution can only decrease a finite number of times, there are only finitely many stages that end with Alice increasing \ell_{1} . (3) Alice never decreases \ell_{A} or increases \ell_{1} We show that in this case, the stage ends with reaching some empty box. By \cref claim:pairs (i) , the pairs do not increase the total number of pebbles. The lines on the stack increase the initial number of pebbles P by at most Z=n\cdot R\leq n\cdot\left(\binom{n}{2}+1\right) . Since by \cref claim:pairs (ii) each red pair removes at least 2 pebbles in total, the sequence may contain at most \frac{1}{2}(P+Z) red pairs. Consider the moment of the last occurrence of a red pair (or the very beginning, if no red pair ever occurs). In the subsequence following this moment, all pairs are green and all the lines involved in them have the same rank. Let (\ell_{i},\ell_{i+1}) be any green pair and p,p^{\prime} be the pebble distributions before and after the green pair. Then by \cref claim:pairs (iv) after each green pair we have p^{\prime}\prec_{L}p . Since the total number of pebbles is finite, after finitely many moves some box becomes empty and Bob wins. ∎ Proof of \cref thm:formula. Immediate from \cref lem:formula-LB,lem:formula-UB. ∎ 4 General position In this section we prove \cref thm:cubic. The upper bound turns out to be simple (any autopilot will do). For the lower bound, we introduce several auxiliary notions, we prove a helpful lemma, and we use a known result about \leq k -levels. Definition 8 . Let \mathcal{L} be a line arrangement. Its dual graph is the unweighted graph D(\mathcal{L})=(B,E) that has one vertex for each box, and edges between boxes that share a side. The distance of two nodes u , v in D(\mathcal{L}) is denoted d(u,v) . Moreover, given a pebble distribution p\colon B\to\mathbb{N} , we say that a pair u,v\in B is small if p(u)+p(v)