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.

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

Offset: 1

Author

Sean Chorney, Feb 08 2021

Keywords

• nonn

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

Examples

			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.
		

Links

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

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.

Programs

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

Mathematica

a[n_] := Table[(Floor[d/2]+1)*(Floor[n^2/(2d)]+1), {d, Divisors[n^2]}] // Min;
Table[a[n], {n, 1, 60}] (* Jean-François Alcover, Apr 04 2023 *)

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

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.

Extensions

Terms a(29) and beyond from Andrew Howroyd, Feb 09 2021