Mínimo de los elementos presentes en {0, 1, 2, ..., 225} para garantizar el triple de la suma de 225

Question

Supongamos que tengo el set: $$A=\{0, 1, 2, ... 224, 225\}$$

Quiero encontrar un triple que las sumas a $225$ (donde un triple es un conjunto de 3 valores únicos en el conjunto).

No Repetición De La Versión:

Hay muchos de esos triples incluidos: $$(0, 1, 224), (0, 2, 223), ... , (74, 75, 76)$$ Note: $(0, 0, 225)$ is not a valid triple as $0$ se repite.

¿Cuál es el número mínimo de valores que deben estar presentes en el conjunto de $A$ tal que se pueda garantizar que un triple debe existir?

O dicho de otra manera, ¿cuántos elementos pueden permitir a un oponente estratégicamente eliminar dicho que todavía puedo garantizar que un triple debe existir (sin ver que los valores fueron retirados)?

De fondo y la Versión con la Repetición:

Esta pregunta surgió a partir de una asignación para escribir un $O(n)$ algoritmo que, dada una lista de quizás $100,000$ enteros no negativos, será la que determine si hay o no $3$ números enteros cuya suma $225$ (nota: yo hace mucho tiempo que han terminado la tarea, pero todavía estoy preguntando acerca de la mejor solución). Aquí, la repetición es permitido para $(0, 0, 225)$ o $(75, 75, 75)$ son válidos triples.

Mi enfoque era crear un 'contador' de la matriz de $C$ del tamaño de la $226$ e inicializarla con $0's$. Mientras que la iteración a través de la lista, si el valor de $i$ se encontraron en $0\le i \le 225$, entonces el incremento de $C[i]$. El contador de la matriz, por tanto, mantiene un seguimiento del número de veces que cada valor relevante se produce.

Podemos dejar de contar después de $1$ ocurrencia para cualquier valor dado $j \gt 225/2$, y después de $2$ acontecimientos de cualquier otro valor, con la excepción de $75$ a que se debe contar para a $3$ apariciones desde la triple $(75, 75, 75)$ debe ser verificada.

Después de la iteración a través de la lista el contador de la matriz se puede comprobar por la presencia de válido triplica el uso de bucles anidados y así sucesivamente. Pero una optimización se puede hacer. Si, por ejemplo, cada valor de $0...225$ se ha encontrado al menos una vez, entonces podemos decir que un triple existe sin siquiera comprobar.

Entonces la pregunta es similar a la simplificación del caso anterior. Después de cuántos 'hits', donde algunos de los $A[i]$ se incrementa, puede simplemente devolver true y saber que un triple debe existir?

---

He estado tratando de encontrar una solución a la versión más simple de este problema durante bastante tiempo. Le pregunté a mi algoritmos profesor y un TA. También escribí un pequeño programa para probar y la fuerza bruta de un techo sobre esto, pero rápidamente corrió hacia los problemas de combinatoria.

Answer 1

$$A=\{0,1,2,\cdots224,225\}$$ Considere esto $151$-elemento subconjunto de $A$:$$B=\{75,76,77,\cdots224,225\}$$ El que menos se suma el triple de este subconjunto es $(75,76,77)$, con una suma de $228$. Añadiendo otro elemento de $\{0,1,2,\cdots73,74\}$ proporcionará una triple con una suma de $225$.

El número mínimo de valores que deben estar presentes en el conjunto de $A$ tal que se pueda garantizar que un triple con suma $225$ debe existir es $152$.

Answer 2

Logophobic la respuesta que da la respuesta correcta de $152$, pero la falta de una completa prueba de optimalidad. Aquí está la prueba.

Podemos partición $A$ a $A = A_1 \cup A_2$ donde$A_1 = \{0,1,\ldots,74\}$$A_2 = \{75,76,\ldots,225\}$.

Supongamos $B \subseteq A$ no contiene el triple de sumar a $225$. Deje $B_1 = B \cap A_1$$B_2 = B \cap A_2$. Deje $k$ ser el tamaño de $B_1$, de manera que los elementos de $B_1$$0\leq x_1 < \cdots < x_k \leq 74$.

El $k=0,1$ de los casos fueron debidamente analizados por logophobic, pero voy a repetir el análisis para completar.

Si $k=0$,$B = B_2 \subseteq A_2$, lo que implica que $|B| \leq |A_2| = 151$. En efecto, el obligado es ajustado, ya que hay 3 elementos distintos de a $A_2$ total $225$.

Si $k=1$, entonces exigimos $B_2 \neq A_2$, desde los distintos números enteros $y_1 = 75$ $y_2 = 150-x_1$ tienen la propiedad de que $y_1, y_2 \in A_2$$x_1+y_1+y_2=225$. Y por lo $|B| = |B_1|+|B_2| \leq 1 + 150 = 151$.

Si $k=2$, luego de considerar los distintos elementos del $y_1=75$$y_2=225-x_1-x_2$. Claramente, $y_2\notin B_2$, ya que el $x_1+x_2+y_2=225$. Si $y_1\notin B_2$,$|B_2| \leq |A_2|-2 = 149$. Si $y_1\in B_2$, a continuación los distintos elementos del $y_3=150-x_1$ $y_4=150-x_2$ tanto no puede ser en $B_2$, ya que el $x_1+y_1+y_3=x_2+y_1+y_4=225$. Así que en este caso también tenemos $|B_2| \leq |A_2|-2 = 149$. Por lo tanto, tenemos $|B| = |B_1|+|B_2| \leq 2 + 149 = 151$.

Si $k\geq3$, a continuación, tenga en cuenta que el $(2k-3)$ distintos valores dados por $(225-x_i-x_j)$ donde $1\leq i < j\leq k$ $|\{i,j\} \cap \{1,k\}|=1$ se encuentran en el conjunto de $A_2$. Esto implica que $|B_2|$ está delimitado por $|A_2| - (2k-3)$, y así tenemos el $|B| = |B_1| + |B_2| \leq k + (151 - (2k-3)) = 154-k\leq 151$.

Esto completa la prueba.