I am doing the #EverybodyCodes quests this November. ( #coding #puzzle ) Today I’d like to talk about quest 11, part 3. Spoilers.

Everybody Codes, quest 11

This next bit will make much more sense if you are actually familiar with part 3. If you haven’t solved it yourself, you might want to look at this description .

Quest 11, part 3 has been described this way:

• “Key insight 2 is that each round in a phase effectively only moves one duck from one column to another. Key insight 3 is that in phase 2, when a column get the number of ducks each column ends with, it will never get more/less (it won’t fluctuate). In other words, the number of ducks per column in phase 2 is either monotonically increasing or monotonically decreasing.” Source
• “If you know that it is sorted, and effectively, every turn one duck moves from the “large” half to the low half, then how many ducks have to be moved to have exactly equal columns in the end?” Source
• “Phase 2 brings the columns to equilibrium using a left to right flood of deficits. If the left column is smaller than the right, then a single duck moves to the left. When applied across the full range of columns in a single round, the smallest column (which must be on the left) gains a duck and the largest column (which must be on the right) loses a duck. The only way it’s not possible for a duck to move is if the columns are at equilibrium.” Source

Maybe I am dumb and just don’t see, that b actually follows from a.

Maybe I needed more than intuition and “when I used this method, I got the correct result”.

Anyway. I have tried writing a proof.

---

We have some columns of ducks.

a b c d e f g

a <= b <= c etc.

The average of a-g is x
We can insert |, so that e.g. c <= x < d

a b c | d e f g

WHAT HAPPENS BEFORE |?

Choose the first among a-c (they are left of |), so that the chosen one is strictly smaller than the one to its right.
Call this candidate m.

So we might have

a b c | d … (a < b)
b b c | d … (a = b < c)
c c c | d … (a = b = c < d)

Notice that it is always possible to choose m.

We might have

m b c | d …

In that case the next step is

m+1 b-1 c | d …

As b <= c, it follows that b-1 < c, and the next step is

m+1 b c-1 | d …

This goes on until we reach c and d.

m+1 b c | d-1 …

IMPORTANT: m grows 1, d-g shrinks 1.
IMPORTANT: the list is still sorted. See below what happens when c = d.

We might also have

m m c | d …

In the first round we get 1 or more steps bringing us to this

m m+1 c | d-1 …

In the next round this becomes

m+1 m+1 c | …

IMPORTANT: each m grows 1, d-g shrinks accordingly.
IMPORTANT: given z m’s, each m grows 1, d-g shrinks z.
IMPORTANT: the list is still sorted after each round.

WHAT HAPPENS AFTER |?

Choose the last among d-g, so that the chosen one is strictly larger than the one to its left.
Call this candidate n.

So we might have

… c | d e f g (f < g)
… c | d e f f (e < f = g)
… c | d e e e (d < e = f = g)
… c | d d d d (c < d = e = f = g)

Notice that it is always possible to choose n.

We might have a step, right after d shrinking.

… | d-1 e f n

In that case we go through these steps.

… | d e-1 f n
… | d e f-1 n
… | d e f n-1

IMPORTANT: d goes back to d, n shrinks 1

We might have

… | d-1 e n n

In that case we go through these rounds

… | d e n n-1
… | d e n-1 n-1

IMPORTANT: d goes back to d, each n shrinks 1.
IMPORTANT: given y n’s, each n shrinks 1, a-c grows y.
IMPORTANT: the list is still sorted after y rounds.

We might have

… | n-1 n n n

In that case we end up here after a round

… | n-1 n-1 n-1 n-1

IMPORTANT: d goes to d-1 = n-1, each n shrinks 1. See below what happens when c = d. Otherwise we keep the property that c < d.
IMPORTANT: given y n’s, each n shrinks 1, a-c grows y.
IMPORTANT: the list is still sorted after y rounds.

To sum up:

We begin with a sorted list.
A duck crosses the | in each round.
The list before | will stay sorted.
The list after | will stay sorted or go back to being sorted after a finite number of steps.

We are headed to a situation looking like

m m m | n n n n

or something similar.

This process ends when m = n = x.
1 round before the end we had something like

m-1 m m | n+1 n n n

All the way through the process, c < d. (Ending with m < n+1.)

---

Maybe all of this is easier to understand watching an example.