Vamos enteros positivos $\alpha$ $\beta$ ser dado. Es fácil encontrar conjuntos de $A$ $B$ de enteros positivos tales que:
- $|A|=\alpha$ $|B|=\beta$
- El conjunto $P = \{ab : a\in A, b\in B\}$ contiene exactamente $\alpha\beta$ de los miembros. Es decir, si $a_1,a_2\in A$$b_1,b_2\in B$, e $a_1b_1 = a_2b_2$,$a_1=a_2$$b_1=b_2$. O dicho de otro modo, la multiplicación es inyectiva cuando se limita a $A\times B$. O de otra manera: si calculamos la tabla de multiplicación de los miembros de $A$ multiplicado por los miembros de $B$, sin entrada aparece más de una vez en la mesa.
Quiero encontrar a $A$ $B$ de manera tal que la mayor entrada en la tabla de multiplicación, $M = \max P = \max A\cdot\max B$, es tan pequeño como sea posible.
Mis preguntas son: ¿cuáles son las buenas asintótica límites en el mínimo de $M$ como una función de la $\alpha$$\beta$? ¿Qué es un buen algoritmo para la búsqueda de conjuntos de $A$ $B$ pequeña $M$, determinado$\alpha$$\beta$? ¿Qué más se puede decir acerca de este problema que es interesante? Se ha estudiado antes, y si es así, lo que ya se conoce?
Ejemplo: $(\alpha, \beta) = (2,4)$
Por ejemplo, digamos que $\alpha=2$, $\beta=4$. Luego de tomar $A = \{1, 2\}$ $B=\{1,3,4,5\}$ hacer $M=10$, ya que los productos se $\{1,3,4,5,2,6,8,10\}$.
$$\begin{array}{r|rrrr} \times & 1 & 3 & 4 & 5 \\ \hline\\ 1 & 1 & 3 & 4 & 5 \\ 2 & 2 & 6 & 8 & 10 \end{array}$$
No es posible obtener un menor $M$ para este caso. Si fuera posible, el 8 elementos de $P$ tendría que ser elegido de $\{1,\ldots 9\}$. Pero $P$ no puede contener 7, desde luego $A$ o $B$ debe contener 7 y, a continuación, $P$ tendría que contener un segundo lugar distinto múltiplo de 7, por lo $M=\max P \ge 14$. Del mismo modo, si $P$ figura 5, tendría que contener un segundo múltiplo de 5, y por lo $M\ge 10$. Por lo $M\le 9$ implica $P\subset \{1,2,3,4,6,8,9\}$ y esto es imposible, ya $P$ tiene 8 elementos. Esta $M=10$ es óptimo.
Ejemplo: $(\alpha, \beta) = (3,4)$
Ahora vamos a considerar $\alpha=3$, $\beta=4$.Tomando $A=\{1,5,6\}$ $B=\{1,2,3,4\}$ trabaja y hace $M=24$, por lo que este es un límite superior para $M$:
$$\begin{array}{r|rrrr} \times & 1 & 2 & 3 & 4 \\ \hline \\ 1 & 1 & 2 & 3 & 4 \\ 5 & 5 & 10 & 15 & 20 \\ 6 & 6 & 12 & 18 & 24 \end{array}$$
$|A|=3$, lo $\max A\ge 3$, e $|B|=4$, lo $\max B\ge 4$. Es fácil ver que $|A\cap B|\le 1$, ya que si $|A\cap B| \ge 2$ podemos encontrar distintos $p$ $q$ $A\cap B$ y, a continuación, $(p, q)$ $(q, p)$ no tienen productos diferentes. Por lo $|A\cup B| \ge 6$, y sabemos que al menos uno debe poseer un elemento que es al menos de 6.
$M$ es igual a $\max A\cdot\max B$. $M=23$ es imposible, desde luego,$M=1\cdot 23$, por lo que uno de $A$ o $B$ tendría un máximo de 1; de la misma manera $M=22 = 2\cdot 11$ es imposible, desde luego, uno de $A$ o $B$ tendría un máximo de 1 o 2.
Así que para encontrar los conjuntos que hacen de $M<24$, debemos tener $M\le 21$. $M=20$ es imposible, desde entonces, uno de $A$ $B$ tendría un máximo de 4 y uno de ellos tiene un max de 5 y nos dijo que al menos uno tiene un máximo de al menos 6. (Obviamente, $20=2\cdot10$ $20 = 1\cdot20$ también fallan.) $M=19$ es imposible por el mismo argumento que descartar $M=23$. Cada una de las $M<18$ puede ser igual de descartar. El único resto de posibilidades se $(\max A, \max B) = (3, 6)$ o $(3, 7)$. A continuación,$A=\{1,2,3\}$. Tomando $\max B = 6$ obtenemos $\{4,5,6\}\subset B$ desde $|A\cap B|\le 1$. Pero, a continuación,$\{2,3\}\subset A$$\{4,6\}\subset B$, por lo que los productos no son todos distintos desde $2\cdot6 = 3\cdot 4$. Esto descarta $\max B = 6$.
Pero $\max B=7$ no funcionan:
$$\begin{array}{r|rrrr} \times & 1 & 4 & 5 & 7 \\ \hline \\ 1 & 1 & 4 & 5 & 7 \\ 2 & 2 & 8 & 10 & 14 \\ 3 & 3 & 12 & 15 & 21 \end{array}$$
Y en el anterior argumentos muestran que esta es la mejor posible.
