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,2

Comments

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.

Links

Pontus von Brömssen, Table of n, a(n) for n = 1..10000

Pontus von Brömssen, Illustration for a(100000)=25116.

Wikipedia, Gerrymandering.

Formula

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)).

Example

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.

Crossrefs

Row minima of A380378.

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

Sequence in context: A220658 A127757 A172264 * A079001 A032615 A261231

Adjacent sequences: A380374 A380375 A380376 * A380378 A380379 A380380

Keyword

nonn

Author

Pontus von Brömssen, Jan 24 2025

Status

approved