login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Comments from Jack W Grahl and Andrew Weimholt, Feb 26 2021: (Start):

This is a two-party election. The size d of each district must divide n^2, so there are n^2/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.

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

N. J. A. Sloane, Table of n, a(n) for n = 1..5000

N. J. A. Sloane, How to use Gerrymandering to win with only 14 votes when you opponent has 22: (1) Locations of voters

N. J. A. Sloane, How to use Gerrymandering to win with only 14 votes when you opponent has 22: (2) Make three districts with 12 voters in each, drawn so that your 14 votes win 2 out of the 3 districts

N. J. A. Sloane, Exciting Number Sequences (video of talk), Mar 05 2021.

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)^2-1, 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)^2-1=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)^2-1=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)^2-1, Infinity]], {n, 60}](* Stefano Spezia, Feb 15 2021 *)

PROG

(Python)

from sympy import divisors

def A341578(n):

    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)**2-1) # Chai Wah Wu, Mar 05 2021

CROSSREFS

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

See A341319 for a variant.

See also A290323.

Sequence in context: A047204 A050035 A306901 * A046974 A177986 A186775

Adjacent sequences:  A341575 A341576 A341577 * A341579 A341580 A341581

KEYWORD

nonn

AUTHOR

Sean Chorney, Feb 14 2021

EXTENSIONS

Entry revised by N. J. A. Sloane, Feb 26 2021.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 3 08:21 EDT 2021. Contains 346435 sequences. (Running on oeis4.)