Problema del solapamiento mínim

En teoria de números, el problema del solapamiento mínim (de l'anglés Minimum overlap problem) és un problema propost pel matemàtic hongarés Paul Erdös en 1955.

Enunciat formal del problema

Sean A={a_i} i B={b_j} dos conjunts complementaris, dividits del conjunt de número natural {1,2,…,2n}, de tal manera que abdós posseïxquen la mateixa cardinalidad, o siga, que la cantitat de números d'abdós conjunts siga igual, en este cas, que siga igual a n. Denote's a M_k com el número de solucions de l'equació a_i-b_j=k a on k és un número entero que varia entre -2n i 2n. Es definix M(n) com:

$M(n)=\underset{A,B}{\min }\underset{k}{\max }{M}_k$

El problema consistix en estimar M(n) quan n és lo suficientment gran.

Història

Entre els problemes plantejats per Paul Erdös en teoria combinatòria de números, es trobava este problema, que es coneix en anglés com The minimum overlap problem (El problema del solapamiento mínim), formulat per primera volta en 1955 en l'artícul, Some remark on number theory, de Riveon Lematematica, i que s'ha convertit en un dels problemes clàssics proposts per Richard Guy en el seu llibre Unsolved problems in number theory.