Edit Town and Simoleons 3: Per-Person Wealth Gaps¶
Codex (GPT-6) provides the optimality proof, closed formula, and implementation for two fixed household slots. The derivation uses only the stated moving rules.
1. Result¶
Write \(k=p_1\) and \(l=p_2\) . If \(l=0\) , the answer is \(m_1\) . Otherwise define
If \(a\ge b\) , doing nothing is optimal. Otherwise set
The answer is
For \(k=l=2,m_1=2,m_2=18\) , we have \(\rho=1/3\) and answer \(10+8/9=98/9\) .
2. The richer slot cannot become the poorer slot¶
Suppose fixed slots A and B currently have \(s,N-s\) residents and per-person wealth \(u,v\) . After one resident moves from A to B, A still has per-person wealth \(u\) if it remains nonempty, while B has
Thus the gap \(v-u\) is multiplied by \((N-s)/(N-s+1)\) . A move from B to A multiplies it by \(s/(s+1)\) . Both factors lie strictly between zero and one when both households remain nonempty.
If a household becomes empty, all residents have merged into the other one and have equal per-person wealth. Every later move preserves this common value.
Consequently the wealth order of the two slots cannot reverse, and the gap can only shrink. This is the key simplification specific to two households.
3. Choosing the final slot¶
If \(a\ge b\) , A is initially at least as rich per person. With the targets back in A and its size restored to \(k\) , the final gap cannot exceed the initial gap. With the targets in B, they occupy the poorer side. Neither case improves on \(m_1\) .
Now assume \(a<b\) . Targets ending in A can receive at most their share of global equal wealth, \(k(m_1+m_2)/N\) . Merging everyone and then separating by identity attains this share.
If the targets end in B, all residents must exchange slots. Let \(F\) be the fraction of the initial per-person gap that remains. A finally has \(l\) residents and B has \(k\) , so conservation of money gives
It remains to maximize \(F\) .
4. Bounding every possible schedule¶
First suppose \(N\ge3\) and both households remain nonempty throughout. Let \(s\) be the population of A. Each move changes it by one; it starts at \(k\) and ends at \(l\) .
A round trip across the population edge \(h\leftrightarrow h+1\) multiplies the gap by
For each edge, pair its upward and downward traversals. Unpaired traversals form exactly a monotone route from \(k\) to \(l\) . Their factors telescope to \(r/t\) : this is \(k/l\) for upward travel and \(l/k\) for downward travel.
If there are \(L\) moves, every resident must change slots, so \(L\ge N\) . The number of paired traversals is
The two factors of \((h+1)(N-h)\) sum to \(N+1\) . Their product is largest when they are as close as possible, giving maximum \(D\) . Every round-trip factor is therefore at most \(\rho\) , where \(0<\rho<1\) , and
A schedule passing through an empty household produces global equal wealth and cannot beat the wealth represented by this bound.
5. Attaining the bound¶
Choose \(h=\lfloor N/2\rfloor\) . Its edge satisfies \((h+1)(N-h)=D\) .
Use the following population route: move monotonically from \(k\) to \(h\) , repeat \(h\to h+1\to h\) exactly \(r\) times, and move monotonically from \(h\) to \(l\) . Since \(h\) lies between \(k\) and \(l\) , the route has exactly \(N\) steps.
Whenever A loses a resident, move a target who has not yet moved from A to B. Whenever A gains a resident, move an outsider who has not yet moved from B to A. The route has exactly \(k\) decreases and \(l\) increases, so every step has an eligible resident. Everyone moves exactly once, and the households exchange all members.
The retained gap is exactly \((r/t)\rho^r\) . Substitution using \(kl(r/t)=r^2\) proves the formula.
For \(N=2\) , both households initially contain one resident. Merge and split them to obtain equal wealth. Here \(\rho=0\) , so the same formula applies. In every branch the maximum is attained after finitely many moves.
6. Modular implementation¶
First compare \(m_1l\) and \(m_2k\) using 64-bit integers. Neither floating-point comparisons nor comparisons of residues are needed.
For \(N=2q\) , use \(D=q(q+1)\) ; for \(N=2q+1\) , use \(D=(q+1)^2\) . Compute these products and the initial cross-products in 64-bit integers.
The denominator factors are \(k,l,N\) and the two integers forming \(D\) . All are nonzero and strictly less than \(P\) , so all are invertible modulo \(P\) . Although \(D\) may exceed \(P\) , it is not divisible by \(P\) . The reduced optimal wealth also has a denominator coprime to \(P\) .
Use Fermat inverses and binary exponentiation for \(\rho^r\) . Use 64-bit modular products and reduce between successive multiplications. Initial cross-products are at most \(10^{15}\) and also fit in 64 bits.
Let \(M\) be the maximum initial household size. One town takes \(O(\log P+\log M)\) time and \(O(1)\) extra space; \(T\) towns take \(O(T(\log P+\log M))\) time.
7. Two ways to evaluate the optimum¶
The reference program evaluates the closed formula. The affine moving-schedule method and its program instead build the proven optimal population route and evaluate each segment in batches. They share the schedule proof but calculate wealth differently. Both use constant space and logarithmic time, and both pass all formal data.
The affine method directly follows the moves; the closed formula gives a direct expression for the result and is selected as the reference. Exact rational full-state search provides additional small-case verification; see the testing guide.