$101$ people, sitting at a round table in any order, had $1,2,... , 101$ cards, respectively. A transfer is someone give one card to one of the two people adjacent to him. Find the smallest positive integer $k$ such that there always can through no more than $ k $ times transfer, each person hold cards of the same number, regardless of the sitting order.
Problem
Source: 24 Mar 2013
Tags: combinatorics proposed, combinatorics
01.04.2013 18:02
the answer is 42925
02.04.2013 14:51
my method 42925=$\ 1^2+2^2+...+50^2$ FIRST ASSUME A1,...,A51,B50,...B1,(A1)are the 101 points ai be the number of Ai,bi be the number of Bi let ai=2i-1,bi=2i prove not less than 42925 steps let f=$\sum_{i=1}^{51}ai*i+\sum_{i=1}^{50}bi*i$ for each thansfer f +1 or -1 or don't change $\Delta$F=-42925 so not less than 42925 STEP
02.04.2013 15:07
THEN PROVE42925 IS ENOUGH assume the points are A1...A101 the number of Ai -51be ai thena1+...a101=0 the arc lenghed 50 that is there's 51 points on it be$\widehat{ A{}_1A{}_5{}_1},\widehat{ A{}_5{}_1A{}_1{}_0{}_1}...\widehat{ A{}_5{}_2A{}_1}$ assume L1,...L101 the number of Li be li so there exit $\l_i*l_{i+1}$$\ge 0$ assumel1,l101$\ge0$ that is a1+...a51$\ge$0 divide a1 into a1"and a1" st.ai'+a2+...a51=0,a1',a1"$\ge0$ seprate the circe into two parts through A1 each part has 51 points it's not hard to prove for part1 can do by |a1'|+|a1'+a2|+...|a1'+...a25|+|a27+...a51|+...|a51|$\le$25|a1'|+24|a2|+...+|a25|+|a27|+2|a28|+...+25|a51|step,and for ai<0 ,the number of Ai not get less so not more than 25|a1'|+24|a2|+...+|a25|+|a27|+2|a28|+...+25|a51|+25|a1"|+24|a101|+...+|a78|+|a75|+2|a74|+...+25|a52|$\le$ $\ 50^2+...+1^2$=42925
22.03.2018 12:37
14.06.2020 22:11
Solved with naman12 We claim that when $101$ is replaced by $2n+1$ for arbitrary $n$ the answer is $\sum_{i=1}^n i^2$. It is easy to see that in the configuration where we arrange the card numbers $n+(0,2,4,\dots,3,1,-1,-3,\dots,-4,-2)$ on the circle clockwise gives a construction that can be finished in $\sum_{i=1}^n i^2$ moves. We'll first prove that $\sum_{i=1}^n i^2$ is the smallest number of moves required in this situation. One proof will be given at the beginning and another at the end. Proof: Write $n$ on the position of the largest number, $n-1$ on the position of the 2nd and 3rd largest numbers, and so on. These are weights of the cards at the respective positions. Observe that each move decreases the sum of weights by at most $1$, and the sum of weights should have decreased by $n\cdot n + (n-1)\cdot (n-1 + n-2) + (n-2)\cdot (n-3 + n-4) + \dots = n^2 + \sum_{i=1}^n (n-i)(2n+1-4i) = \sum_{i=1}^n i^2$. This shows that at least $\sum_{i=1}^n i^2$ moves are needed. Now we prove that $\sum_{i=1}^n i^2$ moves is sufficient. Draw an arrow from each card's starting position to its ending position. Define the length of an arrow to be $1+$ the number of vertices of the regular $n$-gon on the minor arc intercepted by the arrow. It is clear that given a set of arrows, the number of moves required to move all cards from their starting positions to their ending positions is at least the sum of lengths of the arrows, equality only if there exists a sequence of moves that makes each person have a nonnegative amount of cards at all times. Note that we are allowing moves that could potentially cause a negative amount of cards at some point during the process but will eventually show that a set of moves keeping the amount of cards at each vertex of the $2n+1$-gon of $2n+1$ people nonnegative exists. Remove all self-loops and suppose that these cards remain in their respective positions throughout the process. Getting rid of paths: Consider the multigraph generated by the arrows. If there is a vertex $u$ such that $v\to u\to w$ , this means that there are two cards $c_1, c_2$ such that $c_1$ starts at $v$ and $c_2$ starts at $u$, $c_1$ ends at $u$ and $c_2$ ends at $w$. Replace this situation by $v \stackrel{c_1}\to w$ and $u \stackrel{c_2}\to u$ and remove self-loop $c_2$. This does not change the sum of lengths of arrows drawn. After the arrows are drawn, if two of them cross (i.e. chords under the arrows intersect in the interior of the circle, this does not include intersections on the boundary of the circle) but are not identical, uncross the edges. That is, if there are arrows $a\to c, b\to d$ for some $4$ distinct vertices $a,b,c,d$, we now make them $a\to d, b\to c$. Claim: Sum of lengths of arrows does not increase when we uncross edges. Proof: The proof is divided into several cases. See illustrations below (gray arrows represent actual paths of cards that correspond to travelling minimum distance in the left, while the zigzag arrow in the bottom case is a path that may potentially be shorter than the gray line after modification). Repeatedly uncross arrows one pair at a time. Claim: Eventually all arrows will be uncrossed. Proof: Draw a line through each pair from the $2n+1$ vertices for a total of $\binom{2n+1}{2}$ lines and consider $N$, the number of pairs (arrow, line) such that the arrow segment intersects the line but is not included in the line. Each uncrossing decreases $N$ by at least 2 since any line that crosses $ad$ must cross $bd$ or $ac$ and any line that crosses both $ad, bc$ must cross both of $bd,ac$, it follows that $N$ will eventually become negative if the process continues indefinitely, impossible. $\blacksquare$ When the edges are uncrossed, if there are paths then we can replace some edges as before to delete the paths, and each replacement decreases the number of arrows drawn by at least $1$. When uncrossing edges, the number of arrows in the multigraph stays unchanged. Therefore eventually we will end up with a graph that has no crossed arrows and no paths either. Replace $1,\dots,2n+1$ by $-n,\dots,n$ on the circle denoting the number of cards. Since the edges around a vertex are either all incoming or all outgoing, the vertex labelled $a$ must have $a$ edges outgoing if $a > 0$ and $-a$ edges incoming if $a < 0$, while no edges are drawn from the vertex labelled $0$. Now for some $M \le \sum_{i=1}^n i^2$ we will show that the sum of edge lengths is $M$. It will then be clear that a set of moves exists that take $M$ moves according to the edges drawn in the original problem (without ever making any person having a negative number of cards at any point) by moving cards to their destinations one at a time. Lemma: Given any two disjoint sets of vertices $A,B$ with $|A| = |B| = m+1$ such that directed arrows are drawn from $A$ to $B$ in a way such that every vertex in $A$ and every vertex in $B$ is incident to some arrow, prove that there exists an arrow of length $n-m$. Proof: Suppose all arrows have length $\ge n-m+1$. Since the arrows do not intersect, we may select some chords (which have arrows drawn on them) such that the region bounded by the lines passing through those chords contains all arrows. Considering the portion of the circumference lying outside this region, we see that there must be at least $2$ contiguous blocks of $n-m$ points not incident to any arrow, which means that $2(m+1) = |A| + |B| \le (2n+1) - 2(n-m) = 2m+1$, contradiction. $\blacksquare$ The pivotal claim is the following: Claim: For all $m \in \mathbb N$, there exists a set of $m$ vertices that are either all receivers or all givers in the directed multigraph induced by the arrows having lengths $n,...,n+1-m$. Proof: Suppose otherwise. Let $A$ be the set of givers and $B$ the set of receivers with $|A|, |B| \ge m+1$. $A\cup B = \emptyset$ since there are no paths in the digraph. By the lemma there exists an arrow of length $n-m$, contradiction. $\blacksquare$ From the Claim above it follows that there are at most $m$ vertices that are all receivers or all givers, say the former. It follows that at most $n + (n-1) + \dots + (n-m+1)$ of the arrow lengths $\ge n-m+1$. This shows that the multiset of lengths having $i$ copies of length $i$ for each $1\le i \le n$ majorizes the multiset of arrow lengths which we define as $\{\mu_i \cdot i: 1\le i \le n\}$. Thus $$\sum_{i=1}^n \mu_i\cdot i\le \sum_{i=1}^n i\cdot i,$$as desired. At the end we will give another proof of necessity as promised. Note that the characterizations above, when applied to the case that gave the construction of $\sum_{i=1}^n i^2$ in the beginning, shows that the minimum number of moves required can be achieved when all edges are uncrossed and no paths are allowed. We see that the arrow from $1$ must go into $-1$ for edges to not cross and paths to not exist, and then all $3$ arrows from $3$ must go into $-3$, and all $5$ arrows from $5$ must go into $-5$ and so on, which shows that all arrows from $a$ must go into arrows from $-a$ for all $a$. These arrows have sum of lengths $\sum_{i=1}^n i^2$, so at least $\sum_{i=1}^n i^2$ moves are required.
09.08.2021 18:59
Hardest problem I've ever done? The answer is $42925 = \sum^{50}_{i=1} i^2.$ To show our answer is at least this, initially arrange the card numbers in the order $1,3,5, \dots 99, 101, 100, 98, 96, \dots 6, 4, 2$ around the circle, letting the weight of an individual card at each of these positions be $1,2,3, \dots 50, 51, 50, 49, 48, \dots 3, 2, 1$ respectively. Each move can decrease the sum of the weights of all the cards by at most $1$ and it can be seen with computation that we must decrease the sum of the weights by $\sum^{50}_{i=1} i^2$ in order to get all card numbers to become $51,$ so we need at least that many moves. To prove this is enough, arrange the $101$ people as points spaced out evenly on a circle naming them $A_1,A_2, \dots A_{101}$ in clockwise order. Let $p_i$ be the integer $51$ less than $A_{i}$'s initial card number. For each card transferred, we draw an arrow from its starting position to its ending position creating a directed graph on the vertices. Let the length of an arrow be $1$ more than the number of vertices included inside the minor arc on the circle bounded by it. We construct our graph with no directed paths, i.e. a vertex cannot both receive and emanate arrows. Thus, each person will send out, in total, a number of cards that is less than his initial value. So our graph corresponds for a sequence of moves that allows each person have a nonnegative amount of cards at all times. Given that the number of arrows emanating from a vertex $A_i$ minus the number of arrows leading to that vertex must always equal $p_i,$ it suffices to minimize the sum of the lengths of all arrows in our graph. Consider the sequence of minor arcs $A_{1}A_{51}, A_{51}A_{101}, A_{101}A_{151}, \dots A_{52}A_{1}.$ There are an odd number of such arcs, so we may conclude that two consecutive minor arcs in the sequence satisfy the property that the sum of $p_{i}$ over all $51$ vertices (including the endpoints here) for each of the arcs is either both not negative, or both not positive. Suppose WLOG that $p_{1}+p_{2} + \dots + p_{50}+ p_{51}$ and $p_{52}+p_{53}+ \dots+ p_{101} + p_{1}$ have the same sign. "Split" $p_1$ into two components $p_1'$ and $p_1 ''$ with the same sign summing to $p_1$ such that $p_{1}'+p_{2} + \dots + p_{50}+ p_{51} = p_{52}+p_{53}+ \dots+ p_{101} + p_{1}'' = 0.$ We construct a directed graph for each of these two sets of vertices separately with the following claim: Claim: Given $2n+1$ consecutive vertices encompassing a minor arc of our circle, label them $A_{1},A_{2}, \dots A_{2n+1}$ in clockwise order and let their numbers be $p_{1}, p_{2}, \dots p_{2n+1}$ respectively. Suppose $p_{1}+ p_{2}+ \dots + p_{2n+1} = 0.$ We can draw arrows between these vertices such that the number of arrows emanating from a vertex $A_i$ minus the number of arrows leading to that vertex must always equal $p_i,$ there are no directed paths, and the sum of the lengths of the arrows is at most $$n \times | p_{1} | + (n-1) \times | p_{2} |+ \dots + 0 \times | p_{n+1} | + 1 \times |p_{n+2}| + \dots + n \times |p_{2n+1} |$$ Proof: We use induction, the base case is trivial. To prove our required bound, we split each $p_k$ in $p_2, p_3, \dots p_{2n}$ into two components $p_k '$ and $p_k''$ with the same sign summing to $p_k$ such that $p_2' + p_3' + p_4'+ \cdots+ p_{2n}' = 0,$ and either all $p_k''$ are not negative (when $p_{1} + p_{2n+1} \le 0$), or all $p_k''$ are not positive (when $p_{1} + p_{2n+1} \ge 0$). Then, the inductive assumption implies we can construct arrows with length sum at most $$(n-1) \times | p_{2}' |+ \dots + 0 \times | p_{n+1}' | + 1 \times |p_{n+2}'| + \dots + (n-1) \times |p_{2n}' |$$at which point all arrows must lead to one of $p_{1}$ or $p_{2n+1}.$ We can prove that these arrows have length sum at most $$n \times | p_{1} | + (n-1) \times | p_{2}'' |+ \dots + 0 \times | p_{n+1}'' | + 1 \times |p_{n+2}''| + \dots + n \times |p_{2n+1} |$$through simple casework on the signs of $p_{1}$ and $p_{2n+1}.$ Summing these two quantities and using $|a| + |b| = |a+b|$ gives the required bound. $\square$ Applying this claim on our two sections shows that we may create such a graph where the sums of the lengths of the arrows is at most $$25 \times | p_{1} | + 24 \times | p_{2} |+ \dots + 0 \times |p_{26}| + \dots + 25 \times |p_{51} | + 25 \times | p_{52} |+24\times |p_{53}| + \dots + 0 \times |p_{77}| + \dots + 25 \times |p_{101} |$$and since $| p_{1} |, | p_{2} |, \dots | p_{101} |$ is a permutation of $\{1,1,2,2,3,3, \dots 100,100,101\},$ it is not hard to see that this is at most $\sum^{50}_{i=1} i^2.$ $\square$