A341319 -id:A341319 - cp's OEIS frontend

A341721 a(n) = minimum number of total votes needed for one party to win if there are n voters divided into equal districts.

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

Offset: 1

Don Reble and N. J. A. Sloane, Feb 27 2021

nonn

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.

			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.

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, How to use Gerrymandering to win with only 14 votes when your opponent has 22: (1) Locations of voters
N. J. A. Sloane, How to use Gerrymandering to win with only 14 votes when your 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.
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences: An illustrated guide with many unsolved problems, Guest Lecture given in Doron Zeilberger's Experimental Mathematics Math640 Class, Rutgers University, Spring Semester, Apr 28 2022: Slides; Slides (an alternative source).

See A341578 for the case when the number of voters must be a square.
See A341319 for a variant.
See also A290323.

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

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]; Table[f[n], {n, 1, 100}] (* Jean-François Alcover, Apr 04 2023, after Maple code *)

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

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

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.

Original entry on oeis.org

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

Offset: 1

Sean Chorney, Feb 14 2021

nonn

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.

			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.

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.
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences: An illustrated guide with many unsolved problems, Guest Lecture given in Doron Zeilberger's Experimental Mathematics Math640 Class, Rutgers University, Spring Semester, Apr 28 2022: Slides; Slides (an alternative source).
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 21.

See A341721 for an analog where there are n voters, not n^2.
See A341319 for a variant.
See also A290323.

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 *)

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

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}.

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

A365271 Minimum number of shaded squares needed on an n X n grid divided into rectangular regions so that more than half of the regions have more than half of their squares shaded and the area of the smallest region is more than half that of the largest region.

Original entry on oeis.org

1, 3, 4, 6, 8, 11, 14, 16, 20, 24, 28, 32, 36, 42, 48, 54, 60, 66, 72, 80, 88, 96, 104, 112, 120, 130, 140, 150, 158, 168, 180, 192, 204, 215, 226, 238, 252, 264, 277, 289, 306, 320, 336, 351

Offset: 1

Andrew Parkinson, Aug 30 2023

Developed from the Destroying Democracy Puzzle created by Gordon Hamilton.

To achieve a minimum, we need there to be x regions of area >= 2m-1 and (x-1) regions of area <= 4m-3 and m squares shaded in each of the x smaller regions. It can be shown that it is sufficient to only consider an odd number (2x-1) of regions. A weak lower bound is given in the formula section. Exhaustive searches lead to a stronger lower bound on each term, a(n), by identifying values of x and m which enable us to apportion the n^2 grid squares into rectangular regions with side lengths <= n. We then confirm each term by finding an actual configuration of regions that fits the n X n grid.

			For n=4, a(4)=6:
.
              +-----------+---+
  Region A -->| X   X   O | O |
              +-----------+   |
  Region B -->| X   X   O | O |
              +-----------+   |<-- Region E
  Region C -->| X   X   O | O |
              +-----------+   |
  Region D -->| O   O   O | O |
              +-----------+---+
.
The diagram shows the 4 X 4 grid divided into 5 regions. In the 3 regions A, B and C (more than half of the regions), more than half of the squares within each region (2 out of 3) are shaded (X). Of the 16 squares, only 6 (the minimum possible) are shaded; therefore, a(4)=6.
See the Hamilton link for more examples.

Gordon Hamilton, Destroying Democracy!, MathPickle, 2020.
Andrew Parkinson and Rob Pratt, Additional and conjectured terms to a(61).

Cf. A341319, A172477.

A weak lower bound on a(n) is a(n) > n^2/6. (The area of the smaller regions with more than half of their squares shaded is more than half of the area of the larger regions, so the area of the smaller regions is more than one third of the total grid; therefore the number of shaded squares is greater than one sixth of the number of grid squares.)

a(29)-a(44) obtained via integer linear programming by Rob Pratt, Jul 26 2024

cp's OEIS Frontend

A341721 a(n) = minimum number of total votes needed for one party to win if there are n voters divided into equal districts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A365271 Minimum number of shaded squares needed on an n X n grid divided into rectangular regions so that more than half of the regions have more than half of their squares shaded and the area of the smallest region is more than half that of the largest region.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions