|
|
A341721
|
|
a(n) = minimum number of total votes needed for one party to win if there are n voters divided into equal districts.
|
|
3
|
|
|
1, 2, 2, 3, 3, 4, 4, 5, 4, 6, 6, 6, 7, 8, 6, 8, 9, 8, 10, 9, 8, 12, 12, 10, 9, 14, 10, 12, 15, 12, 16, 14, 12, 18, 12, 14, 19, 20, 14, 15, 21, 16, 22, 18, 15, 24, 24, 18, 16, 18, 18, 21, 27, 20, 18, 20, 20, 30, 30, 21, 31, 32, 20, 24, 21, 24, 34, 27, 24, 24, 36, 25, 37, 38, 24
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
This is a two-party election. The size d of each district must divide n, so there are d' = n/d equal districts. The districts are winner-takes-all, 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.
In general the best choice for d is not unique, since d and n/d give the same answer.
This is related to the gerrymandering question.
See A341578 for further information.
|
|
LINKS
|
|
|
FORMULA
|
a(n) is the minimum value over all ways of writing n = d*d' of:
(d+1)*(d'+1)/4 if d and d' are both odd;
(d+2)*(d'+1)/4 if d is even and d' is odd;
(d+1)*(d'+2)/4 if d is odd and d' is even;
(d+2)*(d'+2)/4-1 if d and d' are both even.
a(n) is bounded roughly between n/4 and n/2 (see graph). More precise bounds, which are attained infinitely often, are floor((n+1)/4 + sqrt(n)/2) <= a(n) <= floor((n/2)+1).
|
|
EXAMPLE
|
For n=25 voters the smallest number of votes needed to win is 9: gerrymander 5 districts of 5 voters each, with three votes for the party in each of three districts.
For n=36 voters the smallest number of votes needed to win is 14: gerrymander 3 districts of 12 voters each, with seven votes for the party in each of two districts.
For n=64 voters the smallest number of votes needed to win is 24: gerrymander 8 districts of 8 voters each, with five votes for the party in each of four districts and four votes in a fifth district.
|
|
MAPLE
|
with(NumberTheory);
f:=proc(n) local a, v, d, dp; a:=n;
for d in Divisors(n) do dp:=n/d;
if type(d, 'even') and type(dp, 'even')
then v:=(d+2)*(dp)/4+d/2; if v<a then a:=v; fi;
elif type(d, 'even') and type(dp, 'odd')
then v:=(d+2)*(dp+1)/4; if v<a then a:=v; fi;
elif type(d, 'odd') and type(dp, 'even')
then v:=(d+1)*(dp+2)/4; if v<a then a:=v; fi;
elif type(d, 'odd') and type(dp, 'odd')
then v:=(d+1)*(dp+1)/4; if v<a then a:=v; fi;
fi;
od: # od d
a;
end;
t1:=[seq(f(n), n=1..100)];
|
|
MATHEMATICA
|
f[n_] := Module[{a, v, d, dp}, a = n;
Do[dp = n/d; v = Which[
EvenQ[d] && EvenQ[dp], (d + 2)*(dp)/4 + d/2,
EvenQ[d] && OddQ[dp], (d + 2)*(dp + 1)/4,
OddQ[d] && EvenQ[dp], (d + 1)*(dp + 2)/4,
OddQ[d] && OddQ[dp], (d + 1)*(dp + 1)/4];
If[v < a, a = v],
{d, Divisors[n]}];
a];
|
|
PROG
|
(Python)
from sympy import divisors
def A341721(n): return min((d+2-(d%2))*(e+2-(e%2))//4+int((d%2)or(e%2))-1 for d, e in ((v, n//v) for v in divisors(n) if v*v <= n)) # Chai Wah Wu, Mar 05 2021
|
|
CROSSREFS
|
See A341578 for the case when the number of voters must be a square.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|