## Sticks in a Bag

Each stick in a certain bag has integral length. If any three sticks are selected from the bag, they will not form a triangle. The longest stick in the bag has length $100$. What is the maximum number of sticks in the bag?
Source: NCTM Mathematics Teacher, December 2005

SOLUTION
In a triangle the sum of the lengths of any two sides is greater than the length of the third side (Triangle Inequality theorem). One way of not forming a triangle is to have the sum of the lengths of any two sides equal to the length of the third side.
Let’s start with $3$ sticks of lengths $1,1,2$. They do not form a triangle because $1+1=2$.
Continue the process and make the fourth stick of length $1+2=3$, etc. and we end up with the following $12$ Fibonacci numbers
$1,1,2,3,5,8,13,21,34,55,89,144,\cdots$
Since the longest length is $100$, we cannot have $12$ sticks in the bag. But, we can use the first ten sticks plus the $100$ stick
$1,1,2,3,5,8,13,21,34,55,100$
The maximum number of sticks in the bag is $11$.

Answer: $11$