A341319 - OEIS

%I #47 Apr 04 2023 12:37:24

%S 1,3,4,9,9,14,16,25,25,33,36,45,49,60,64,81,81,95,100,117,121,138,144,

%T 165,169,189,196,225,225,247,256,289,289,315,324,350,361,390,400,429,

%U 441,473,484,529,529,564,576,625,625,663,676,729,729,770,784,825,841,885,900,943

%N 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.

%C 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.

%C This is related to the gerrymandering question. - _N. J. A. Sloane_, Feb 27 2021

%H Alois P. Heinz, <a href="/A341319/b341319.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) is the minimum value of (floor(d/2)+1)*(floor(n^2/(2*d))+1) over all divisors d of n^2.

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

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

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

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

%e Party A only needs 4 cells out of 9 to win a majority of districts.

%e For a(6), divisors of 6^2 are 1, 2, 3, 4, 6, 9, 12, 18, 36:

%e By symmetry we can ignore d = 9, 12, 18 and 36;

%e   d=1: (floor(1/2)+1)*(floor(6^2/(2*1))+1) = 1*19 = 19

%e   d=2: (floor(2/2)+1)*(floor(6^2/(2*2))+1) = 2*10 = 20

%e   d=3: (floor(3/2)+1)*(floor(6^2/(2*3))+1) = 2*7  = 14

%e   d=4: (floor(4/2)+1)*(floor(6^2/(2*4))+1) = 3*5  = 15

%e   d=6: (floor(6/2)+1)*(floor(6^2/(2*6))+1) = 4*4  = 16

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

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

%p seq(a(n), n=1..60);  # _Alois P. Heinz_, Feb 09 2021

%t a[n_] := Table[(Floor[d/2]+1)*(Floor[n^2/(2d)]+1), {d, Divisors[n^2]}] // Min;

%t Table[a[n], {n, 1, 60}] (* _Jean-François Alcover_, Apr 04 2023 *)

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

%o (Python)

%o from sympy import divisors

%o 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

%Y 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).

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

%K nonn

%O 1,2

%A _Sean Chorney_, Feb 08 2021

%E Terms a(29) and beyond from _Andrew Howroyd_, Feb 09 2021