

A341578


a(n) is the minimum number of total votes needed for one party to win if there are n^2 voters divided into equal districts.


3



1, 3, 4, 8, 9, 14, 16, 24, 25, 33, 36, 45, 49, 60, 64, 80, 81, 95, 100, 117, 121, 138, 144, 165, 169, 189, 196, 224, 225, 247, 256, 288, 289, 315, 324, 350, 361, 390, 400, 429, 441, 473, 484, 528, 529, 564, 576, 624, 625, 663, 676, 728, 729, 770, 784, 825, 841, 885, 900, 943
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

This is a twoparty election. The size d of each district must divide n^2, so there are n^2/d equal districts.
The districts are winnertakesall, and tied districts go to neither candidate. For an even number of districts, it is enough to win half the districts and tie in one further district.
So for 5 districts of 5 votes each, one party could win with 3 votes in each of 3 districts, and 0 in all other districts, for a total of a(5) = 9 votes.
For 8 districts of size 8, 5 votes in each of 4 districts and 4 votes in a fifth district are enough, for a total of a(8) = 24 votes.
d need not equal n. For n=6, it is better to gerrymander the 36 votes into 3 districts with 12 votes each, and then a(6) = 14 = 7+7+0 votes are enough to win. (End)
This is related to the gerrymandering question. What is the asymptotic behavior of a(n)?  N. J. A. Sloane, Feb 20 2021. Answer from Don Reble, Feb 26 2020: The lower bound is [(n^2+1)/4 + n/2]; the upper bound is [n^2/4 + n]. Each bound is reached infinitely often. In general the best choice for d is not unique, since d and n/d give the same answer.


LINKS



FORMULA

a(n) is the minimum value of {(floor(d/2)+1)*(floor(n^2/(2*d))+1) over all divisors d of n^2 AND (n/2+1)^21, if n is even}.


EXAMPLE

For a(2), divisors of 2^2 are 1, 2, 4:
d=1: (floor(1/2)+1)*(floor(2^2/(2*1))+1) = 1*3 = 3
d=3: (floor(2/2)+1)*(floor(2^2/(2*2))+1) = 2*2 = 4
d=9: (floor(4/2)+1)*(floor(2^2/(2*4))+1) = 3*1 = 3
OR
since n is even, ((2/2)+1)^21=3
Party A only needs 3 cells out of 4 to win a majority of districts.
For a(6), divisors of 6^2 are 1, 2, 3, 4, 6, 9, 12, 18, 36:
By symmetry we can ignore d = 9, 12, 18 and 36;
d=1: (floor(1/2)+1)*(floor(6^2/(2*1))+1) = 1*19 = 19
d=2: (floor(2/2)+1)*(floor(6^2/(2*2))+1) = 2*10 = 20
d=3: (floor(3/2)+1)*(floor(6^2/(2*3))+1) = 2*7 = 14
d=4: (floor(4/2)+1)*(floor(6^2/(2*4))+1) = 3*5 = 15
d=6: (floor(6/2)+1)*(floor(6^2/(2*6))+1) = 4*4 = 16
OR
since n is even, ((6/2)+1)^21=15
Party A only needs 14 cells out of 36 to win a majority of districts.


MATHEMATICA

Table[Min[Table[(Floor[d/2]+1)*(Floor[n^2/(2*d)]+1), {d, Divisors[n^2]}], If[EvenQ[n], (n/2+1)^21, Infinity]], {n, 60}](* Stefano Spezia, Feb 15 2021 *)


PROG

(Python)
from sympy import divisors
c = min((d//2+1)*(n**2//(2*d)+1) for d in divisors(n**2, generator=True) if d<=n)
return c if n % 2 else min(c, (n//2+1)**21) # Chai Wah Wu, Mar 05 2021


CROSSREFS

See A341721 for an analog where there are n voters, not n^2.


KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



