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!)
A341319 Minimum number of cells needed in an n X n grid to win a majority of districts when all districts are required to be the same size. 3
1, 3, 4, 9, 9, 14, 16, 25, 25, 33, 36, 45, 49, 60, 64, 81, 81, 95, 100, 117, 121, 138, 144, 165, 169, 189, 196, 225, 225, 247, 256, 289, 289, 315, 324, 350, 361, 390, 400, 429, 441, 473, 484, 529, 529, 564, 576, 625, 625, 663, 676, 729, 729, 770, 784, 825, 841, 885, 900, 943 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Consider an n X n grid in which each cell represents a vote for a political party "A" or "B". The grid is divided into equal-sized districts and the winner of each district is decided by a majority of "A"s or "B"s. This sequence is the minimum number of "A"s needed to win more districts than "B" if n = 1, 2, 3, ... A tie within a district is not accepted. For example, if n=5, and the district size is also 5, party "A" needs 3 cells in 3 districts (total = 3*3=9) to win 3 districts to 2.

This is related to the gerrymandering question. - N. J. A. Sloane, Feb 27 2021

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..10000

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.

EXAMPLE

For a(3), divisors of 3^2 are 1, 3, 9:

d=1: (floor(1/2)+1)*(floor(3^2/(2*1))+1) = 1*5 = 5

d=3: (floor(3/2)+1)*(floor(3^2/(2*3))+1) = 2*2 = 4

d=9: (floor(9/2)+1)*(floor(3^2/(2*9))+1) = 5*1 = 5

Party A only needs 4 cells out of 9 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

Party A only needs 14 cells out of 36 to win a majority of districts.

MAPLE

a:= n->min(map(d->(iquo(d, 2)+1)*(iquo(n^2, 2*d)+1), numtheory[divisors](n^2))):

seq(a(n), n=1..60);  # Alois P. Heinz, Feb 09 2021

PROG

(PARI) a(n)={vecmin([(floor(d/2) + 1)*(floor(n^2/(2*d)) + 1) | d<-divisors(n^2)])} \\ Andrew Howroyd, Feb 09 2021

(Python)

from sympy import divisors

def A341319(n): return min((d//2+1)*(e//2+1) for d, e in ((v, n**2//v) for v in divisors(n**2) if v <= n)) # Chai Wah Wu, Mar 05 2021

CROSSREFS

Cf. A341578 (ties are allowed), A002265(n+6) (US Electoral College system: unequal sizes of districts, winner in each district takes all its votes), A290323 (multiple levels).

See A341721 for a case where the number of voters need not be a square.

Sequence in context: A076120 A082188 A202499 * A307992 A323180 A095047

Adjacent sequences:  A341316 A341317 A341318 * A341320 A341321 A341322

KEYWORD

nonn

AUTHOR

Sean Chorney, Feb 08 2021

EXTENSIONS

Terms a(29) and beyond from Andrew Howroyd, Feb 09 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 September 27 18:30 EDT 2021. Contains 347694 sequences. (Running on oeis4.)