OFFSET
1,2
COMMENTS
See A380377 for further details.
It is never optimal to have any supporters in a losing district or to win a district with a greater margin than necessary. This implies that, in any optimal strategy, any district of size m should have 0, m/2, (m+1)/2, or m/2+1 supporters. If k is odd, the optimal strategy is to win the (k+1)/2 smallest districts. If k is even and n/k is an odd integer, the best strategy is to win k/2+1 districts (all districts have n/k voters in this case). If k is even and n/k is not an odd integer, the best strategy is to draw one of the even districts and win the k/2 smallest remaining districts.
LINKS
Pontus von Brömssen, Table of n, a(n) for n = 1..5050 (first 100 rows)
Pontus von Brömssen, Illustration for row n=100000.
EXAMPLE
Triangle begins:
n\k| 1 2 3 4 5 6 7 8 9 10 11 12
---+-----------------------------------
1 | 1
2 | 2 2
3 | 2 2 2
4 | 3 3 2 3
5 | 3 3 3 3 3
6 | 4 4 4 3 3 4
7 | 4 4 4 4 3 4 4
8 | 5 5 4 5 4 4 4 5
9 | 5 5 4 5 5 4 4 5 5
10 | 6 6 4 5 6 5 4 5 5 6
11 | 6 6 5 5 6 6 5 5 5 6 6
12 | 7 7 6 6 6 7 6 5 5 6 6 7
PROG
(Python)
def A380378(n, k):
q, r = divmod(n, k)
q2, rq = divmod(q, 2)
k2, rk = divmod(k, 2)
x = (k2+1)*(q2+1)
if 2*r<k: x -= rk==0 and rq==0
else:
if rq==1: x += r-k2+1-rk
x += rk-1
return x
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Pontus von Brömssen, Jan 24 2025
STATUS
approved