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

Author

Pontus von Brömssen, Jan 24 2025

Keywords

• nonn

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.

Examples

			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.
		

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.

Crossrefs

Row minima of A380378.

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

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