# Minimum elements present in {0, 1, 2, ..., 225} to guarantee triple which sums to 225

Suppose I have the set: $$A=\{0, 1, 2, ... 224, 225\}$$

I want to find a triple that sums to $225$ (where a triple is a set of 3 unique values from the set).

No Repetition Version:

There are many such triples including: $$(0, 1, 224), (0, 2, 223), ... , (74, 75, 76)$$ Note: $(0, 0, 225)$ is not a valid triple as $0$ is repeated.

What is the minimum number of values which must be present in the set $A$ such that we can guarantee that a triple must exist?

Or put another way, how many elements can I allow an opponent to strategically remove such that I can still guarantee that a triple must exist (without seeing which values were removed)?

Background & Version with Repetition:

This question arose from an assignment to write an $O(n)$ algorithm which, given a list of perhaps $100,000$ non-negative integers, will determine whether there are $3$ integers which sum to $225$ (note: I have long since finished the assignment, but am still wondering about a better solution). Here, repetition is allowed so $(0, 0, 225)$ or $(75, 75, 75)$ are valid triples.

My approach was to create a 'counter' array $C$ of size $226$ and initialize it with $0's$. While iterating through the list, if the value $i$ is encountered where $0\le i \le 225$, then increment $C[i]$. The counter array therefore keeps track of the number of times each relevant value occurs.

We can stop counting after $1$ occurrence for any given value $j \gt 225/2$, and after $2$ occurrences for any other value, except $75$ which must be counted for up to $3$ occurrences since the triple $(75, 75, 75)$ must be checked for.

After iterating through the list the counter array can be checked for the presence of valid triples using nested loops and so on. But an optimization can be made. If for example, every value from $0...225$ has been found at least once, then we can say that a triple exists without even checking.

The question is then similar to the simplified case above. After how many 'hits', where some $A[i]$ is incremented, can we simply return true and know that a triple must exist?

I've been trying to find a solution to the simpler version of this problem for quite a while. I asked my algorithms professor and a TA. I also wrote a small program to try and brute force a ceiling on this but quickly ran into combinatorial problems.

## 2 Answers

$$A=\{0,1,2,\cdots224,225\}$$ Consider this $151$-element subset of $A$:$$B=\{75,76,77,\cdots224,225\}$$ The least-sum triple from this subset is $(75,76,77)$ with a sum of $228$. Adding another element from $\{0,1,2,\cdots73,74\}$ will provide a triple with a sum of $225$.

The minimum number of values which must be present in the set $A$ such that we can guarantee that a triple with sum $225$ must exist is $152$.

• A notational conflict: The need for $151$ numbers in your set $A$ mean at least $152$ numbers are required in Jordan's set $A$. Commented Feb 6, 2016 at 20:47
• Jordan's set $A$ contains $225$, while yours does not. Since you require $151$ numbers in your set $A$ to guarantee a triple with sum $225$, he requires $152$ numbers in his set $A$. All I am suggesting is that calling your set $\{0, 1, 2, \ldots, 223, 224\}$ $A$ introduces an unnecessary notational conflict that could lead to confusion. Commented Feb 6, 2016 at 20:57
• I see your point, $B=\{75,76,77,\cdots224,225\}$ has $151$ numbers and no valid triple. Commented Feb 6, 2016 at 20:59
• How can you be sure this is the right answer? Commented Feb 6, 2016 at 21:11
• Any single element $\lt73$ will provide a triple with at least $2$ distinct pairs of numbers $\ge75$. For example $72+75+78=72+76+77=225$. Thus, adding any single number $<73$ would necessitate the removal of two other numbers in order to prevent a triple having sum $225$. Including $73$ and $74$ and removing $75$ to avoid $73+75+77=74+75+76=225$ would provide $73+74+78=225$ It is therefore not possible to increase the size of the subset without providing for a triple with sum $225$ Commented Feb 6, 2016 at 21:31

Logophobic's answer gives the correct answer of $152$, but is missing a complete proof of optimality. Here is a complete proof.

We may partition $A$ into $A = A_1 \cup A_2$, where $A_1 = \{0,1,\ldots,74\}$ and $A_2 = \{75,76,\ldots,225\}$.

Suppose $B \subseteq A$ contains no triple summing to $225$. Let $B_1 = B \cap A_1$ and $B_2 = B \cap A_2$. Let $k$ be the size of $B_1$, so that the elements of $B_1$ are $0\leq x_1 < \cdots < x_k \leq 74$.

The $k=0,1$ cases were properly analyzed by logophobic, but I will repeat the analysis here for completeness.

If $k=0$, then $B = B_2 \subseteq A_2$, implying that $|B| \leq |A_2| = 151$. Indeed, the bound is tight, since no 3 distinct elements of $A_2$ sum to $225$.

If $k=1$, then we demand $B_2 \neq A_2$, since the distinct integers $y_1 = 75$ and $y_2 = 150-x_1$ have the property that $y_1, y_2 \in A_2$ and $x_1+y_1+y_2=225$. And so $|B| = |B_1|+|B_2| \leq 1 + 150 = 151$.

If $k=2$, then consider the distinct elements $y_1=75$ and $y_2=225-x_1-x_2$. Clearly, $y_2\notin B_2$, since $x_1+x_2+y_2=225$. If $y_1\notin B_2$, we have that $|B_2| \leq |A_2|-2 = 149$. If $y_1\in B_2$, then the distinct elements $y_3=150-x_1$ and $y_4=150-x_2$ both cannot be in $B_2$, since $x_1+y_1+y_3=x_2+y_1+y_4=225$. So in this case we also have $|B_2| \leq |A_2|-2 = 149$. Thus, we have $|B| = |B_1|+|B_2| \leq 2 + 149 = 151$.

If $k\geq3$, then note that the $(2k-3)$ distinct values given by $(225-x_i-x_j)$ where $1\leq i < j\leq k$ with $|\{i,j\} \cap \{1,k\}|=1$ all lie in the set $A_2$. This implies that $|B_2|$ is bounded by $|A_2| - (2k-3)$, and so we have $|B| = |B_1| + |B_2| \leq k + (151 - (2k-3)) = 154-k\leq 151$.

This completes the proof.

• Thank you @dshin for your work. I will bring your proof to my instructor! Commented Feb 7, 2016 at 6:10