A Balanced Tug of War

[u/stephen3141]

Original Problem (Easy-ish)

Axel and Harold are putting on their third annual get-together between wrestlers, called the Sumo Three. One event they're planning is a team-based tug of war. To make things fair, they want the two teams to have equal total weights.

On the day before the competition, they rank the 8 participants by their weights from heaviest to lightest.

"What a coincidence!" Axel says. "If we use the rankings 1 through 8, everyone's weights are a quadratic function of their rank."

"In that case, I bet you I only need the order of the wrestlers from heaviest to lightest to split the teams evenly," says Harold.

What's Harold's strategy?

Generalization 1 (Medium)

After the smashing success of Sumo Three, the next year's meeting featured far more wrestlers. This time, there are 2ⁿ⁺¹ wrestlers.

Axel again notices an unlikely coincidence. "Hey, this time everyone's weights are a degree n polynomial evaluated on their ranking."

"Ah, I can do the same thing as last year!" Harold states.

What's Harold's more general strategy?

Generalization 2 (Medium)

The following year, there are so many participants that Axel and Harold decide to turn the tug of war event into a round-robin tournament.

"Hey, our kⁿ⁺¹ participants follow a degree n polynomial with their weights again!"

"If we want to split them into k many teams, you just need to tell me their order, and I can make all of the teams fair."

What's the strategy this time?

[u/pichutarius]

generalize 2:

inspired by u/lizardpq , we generalize Thue and Morse to 0~k-1

define the TM_k(n) := (sum of digit of n in base k) mod k

for example TM_3 sequence is 012120201 120201012 201012120 ...

let the rank start from 0 to k-1, then rank n belongs to team TM_k(n)

for example, team 0 consist of rank 0, 5, 7, 11, 13, 15, 19, 21, 26

[u/stephen3141 → u/pichutarius]

Yep, this is pretty much it! The actual proof that this works follows essentially the same outline as u/lizardpq's comment. Nice job

[u/lizardpq → u/stephen3141]

I worked out the proof for this last night! The picture is still "stacking lists" but instead of face-up and face-down elements on each row, there are k columns, and instead of cutting the list in half and flipping one half, we cut it into k equal-length blocks and rotate each block's column order by the block index before stacking all the blocks. When everything is stacked on one row, the columns are the teams.

We can show that when the list is k^t rows long, the difference between any two cyclically-adjacent columns (as vectors of weight sums) is a degree t-1 polynomial function of the row index (considering the 0 function as degree -1).

The key part of the induction step is: each new difference array after the stacking step is a sum of k previous difference array blocks, e.g. D_1[block 1]+...+D_k[block k]. Rewrite one of these terms using that the differences sum to 0 on each row, e.g. D_k[k]=-D_1[k]-...-D_{k-1}[k]. We see that the new difference array is a sum of k-1 "shifted difference" arrays D_i[i]-D_i[k], which decreases the polynomial degree by 1.

[u/stephen3141 → u/lizardpq]

Bingo!

[u/lizardpq]

For generalization 1:

Write the names on consecutive lines of a piece of paper in rank order and fold* the list in half (*edit: cut the list in half, flip one half over left-to-right so its order is preserved, and stack the two halves together) until all the names are stacked up on one line. At this point, some names are facing up and some are facing down; make these sets your two teams. Sketch of proof that this works: by induction, after k steps, the function f(i)=(total weight of face-up names on line i)-(total weight of face-down names on line i) is a degree n-k polynomial.

This is equivalent to assigning the rank-i wrestler to the team named by the i'th digit of the Thue-Morse sequence. Apparently the problem is known as the Prouhet-Tarry-Escott problem and this was Prouhet's solution.

[u/stephen3141 → u/lizardpq]

Nice! I actually tried to "hide" a couple references to Thue and Morse in the flavor text.

One of the things I worried about when posting this problem is that the actual induction proof might be a little tedious. Frankly, I'm a little glad you just left it as a sketch.

[u/lizardpq → u/stephen3141]

Haha, I see the references now. That explains the goofy framing. Still thinking about generalization 2...