A380383 -id:A380383 - cp's OEIS frontend

A380377 Minimum number of total votes needed for one party to win if there are n voters divided into balanced districts, i.e., the numbers of voters in two districts may differ by at most 1.

1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 11, 12, 12, 12, 12, 12, 12, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 17, 18, 18, 18, 18, 18, 18, 18, 19, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 22

Offset: 1

Pontus von Brömssen, Jan 24 2025

nonn

The rules are the same as in A341721 (except that the number of voters in two districts may differ by 1 here): The winner must have a strict majority of the votes in a strictly larger number of districts than the other party has.

Empirically, it seems that the limit of (a(n)-n/4)/sqrt(n) exists with an approximate value of 0.3538.

			For n = 9, a(9) = 4 votes are required to win. There can be either 3 districts 3+3+3 with 2 supporters in 2 of them, 6 districts 1+1+1+2+2+2 with 3 supporters in the single-voter districts and 1 in a 2-voter district, or 7 districts 1+1+1+1+1+2+2 with supporters in 4 of the single-voter districts.
For n = 17, a(17) = 6 votes are required to win. This can only be achieved with 5 districts 3+3+3+4+4 with 2 supporters in each of the 3 smaller districts.

Pontus von Brömssen, Table of n, a(n) for n = 1..10000
Pontus von Brömssen, Illustration for a(100000)=25116.
Wikipedia, Gerrymandering.

Row minima of A380378.

Cf. A341721, A380379, A380380, A380381, A380382, A380383.

a(n) <= A341721(n).
a(n) = a(n-1)+1 if n is in A380379, otherwise a(n) = a(n-1).
a(n) = A380378(n,A380381(n)) = A380378(n,A380382(n)).

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.

Original entry on oeis.org

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

Pontus von Brömssen, Jan 24 2025

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.

			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

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.

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

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

cp's OEIS Frontend

A380377 Minimum number of total votes needed for one party to win if there are n voters divided into balanced districts, i.e., the numbers of voters in two districts may differ by at most 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula