A393584 - OEIS

%I #52 Mar 28 2026 13:09:58

%S 1,1,2,2,3,3,3,4,4,5,5,5,6,6,6,7,7,8,8,8,9,9,10,10,10,11,11,11,12,12,

%T 13,13,13

%N a(n) is the minimum, over all partitions {X, Y} of {1..2n} with |X| = |Y|, of the maximum number of pairs (x, y) with the same difference x - y for x in X and y in Y.

%C a(n) is floor(5*n/13) for small n but a(n) ~ (c - o(1))*n for some 0.379005 < c < 0.380876. - _Sharvil Kesarwani_, Mar 04 2026

%C From _Bert Dobbelaere_, Mar 02 2026: (Start)

%C a(k*n) <= k*a(n) can be shown by constructing a set X' containing all elements in range [k*(x-1)+1...k*x] for each element x of X (similar for Y).

%C a(n+1) <= a(n) + 1 can be shown by extending X with element 2n+1 and Y with element 2n+2.

%C It follows that a(n)/n >= the lower bound for c, otherwise it would be violated for arbitrary large k. (End)

%H Thomas F. Bloom, <a href="https://www.erdosproblems.com/36">Erdős Problem #36</a>

%F a(2n) <= n.

%F a(k*n) <= k * a(n) for positive integer k. - _Bert Dobbelaere_, Mar 02 2026

%F a(n+1) <= a(n) + 1. - _Bert Dobbelaere_, Mar 02 2026

%e For n = 2, the equal partitions of {1,2,3,4} are:

%e - {1,2} and {3,4}: the differences are 2, 1, 3, 2: max repetition is 2.

%e - {1,3} and {2,4}: the differences are 1, -1, 3, 1, max repetition is 2.

%e - {1,4} and {2,3}: the differences are 1, -2, 2, -1, max repetition is 1.

%e Hence a(2) = 1.

%e For n = 3, the partition {1,2,4} and {3,5,6} has at most two pairs with the same difference, so a(3) <= 2. Exhaustive checking shows that no partition has lower repetition.

%o (Python)

%o from itertools import combinations

%o from collections import Counter

%o def a(n): return min(max(Counter(a-b for a in A for b in range(1, 2 * n + 1) if b not in A).values()) for A in combinations(range(1, 2*n + 1),n))

%K nonn,more

%O 1,3

%A _Touch Sungkawichai_, Feb 22 2026

%E a(19)-a(21) from _Christian Sievers_, Feb 26 2026

%E a(22)-a(26) from _Bert Dobbelaere_, Feb 28 2026

%E a(27)-a(28) from _Sharvil Kesarwani_, Mar 01 2026

%E a(29)-a(30) from _Bert Dobbelaere_, Mar 02 2026

%E a(31)-a(33) from _Bert Dobbelaere_, Mar 28 2026