A380378 Triangle read by rows: T(n,k) is the minimum number of total votes needed for one party to win if there are n voters divided into k balanced districts, 1 <= k <= n.

1, 2, 2, 2, 2, 2, 3, 3, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 3, 3, 4, 4, 4, 4, 4, 3, 4, 4, 5, 5, 4, 5, 4, 4, 4, 5, 5, 5, 4, 5, 5, 4, 4, 5, 5, 6, 6, 4, 5, 6, 5, 4, 5, 5, 6, 6, 6, 5, 5, 6, 6, 5, 5, 5, 6, 6, 7, 7, 6, 6, 6, 7, 6, 5, 5, 6, 6, 7, 7, 7, 6, 6, 6, 7, 7, 6, 5, 6, 6, 7, 7

Offset: 1

Author

Pontus von Brömssen, Jan 24 2025

Keywords

• nonn
• tabl

Comments

See A380377 for further details.

It is never optimal to have any supporters in a losing district or to win a district with a greater margin than necessary. This implies that, in any optimal strategy, any district of size m should have 0, m/2, (m+1)/2, or m/2+1 supporters. If k is odd, the optimal strategy is to win the (k+1)/2 smallest districts. If k is even and n/k is an odd integer, the best strategy is to win k/2+1 districts (all districts have n/k voters in this case). If k is even and n/k is not an odd integer, the best strategy is to draw one of the even districts and win the k/2 smallest remaining districts.

Examples

			Triangle begins:
  n\k| 1  2  3  4  5  6  7  8  9 10 11 12
  ---+-----------------------------------
   1 | 1
   2 | 2  2
   3 | 2  2  2
   4 | 3  3  2  3
   5 | 3  3  3  3  3
   6 | 4  4  4  3  3  4
   7 | 4  4  4  4  3  4  4
   8 | 5  5  4  5  4  4  4  5
   9 | 5  5  4  5  5  4  4  5  5
  10 | 6  6  4  5  6  5  4  5  5  6
  11 | 6  6  5  5  6  6  5  5  5  6  6
  12 | 7  7  6  6  6  7  6  5  5  6  6  7
		

Links

• Pontus von Brömssen, Table of n, a(n) for n = 1..5050 (first 100 rows)
• Pontus von Brömssen, Illustration for row n=100000.

Crossrefs

Cf. A380377 (row minima), A380379, A380380, A380381, A380382, A380383.

Programs

Python

def A380378(n,k):
    q,r = divmod(n,k)
    q2,rq = divmod(q,2)
    k2,rk = divmod(k,2)
    x = (k2+1)*(q2+1)
    if 2*r