¿Teoría de números / problema de combinatoria?

Question

Dado un conjunto de números naturales$14$ (diferente), demuestre que para algunos$k$ ($1 ≤ k ≤ 7$) existen dos disjuntos$k$ - subconjuntos de elementos$\{a_1,...,a_k\}$ y$\{b_1,...,b_k\}$ tal que la suma de los recíprocos de todos los elementos en cada conjunto difiere en menos que$0.001$, es decir,$|A−B| < 0.001$, donde$A =$ la suma de los recíprocos de los elementos de primer subconjunto y$B =$ la suma de los recíprocos de los elementos del segundo subconjunto.

Nota: este problema es de la Olimpiada de Matemáticas Checa y Eslovaca de 1998

Answer 1

Considere los subconjuntos de elementos de los catorce números de$\binom{14}{7} = 3432$$7$ y observe las sumas de los recíprocos de los números de cada subconjunto. Cada suma es a lo sumo $$1 + {1\over2} + \ldots + {1\over7} = {{363}\over{140}} < 2.60,$$ so each of the $3432$ sums lies in one of the $2600$ intervals $$\left(0, {1\over{1000}}\right], \text{ }\left({1\over{1000}}, {2\over{1000}}\right], \text{ }\ldots\text{ }, \text{ }\left({{2599}\over{1000}}, {{2600}\over{1000}}\right].$$ Then by the pigeonhole principle, some two sums lie in the same interval. Taking the corresponding sets and discarding any possible common elements, we obtain two satisfactory subsets $A$ and $B$.

Answer 2

Aquí es un codicioso enfoque, lo que sugiere que el $14$ podría reducir a $13$, pero no es una prueba. Si el primer número es muy grande para mantener su recíproco pequeño, el siguiente tiene que ser en la mayoría de los $999$, por lo que su recíproco supera $0.001$. A continuación, el siguiente tiene que ser en la mayoría de los $499$, por lo que su recíproco supera $0.002$. El próximo recíproca debe tener al menos $0.004$, por lo que el número es en la mayoría de las $249$. Podemos representar estas como $0,1,2,4$, el número de milésimas en la reciprocidad. Si seguimos llegamos $0, 1, 2, 4, 7, 13, 24, 44, 84, 161, 309, 594, 1164, 2284\ldots$, que se muestra en OEIS A005318. El hecho de que la decimotercera plazo supera $1000$ sugiere que hemos de ejecutar fuera de la habitación ya.