A new game show on TV has $100$ boxes numbered $1,2\dots,100$ in a row, each containing a mystery prize. The prizes are items of different types $a,b,c,\dots,$ in decreasing order of value. The most expensive item is of type a, a diamond ring, and there is exactly one of these. You are told that the number of items at least doubles as you move to the next type. For example, there would be at least twice as many items of type b as of type a,at least twice as many items of type c as of type b and so on. There is no particular order in which the prizes are placed in the boxes.
You ask for the type of item in box $45$. Instead of being given a direct answer, you are told that there are $31$ items of the same type as box $45$ in boxes $1$ to $44$ and $43$ items of the same type as box $45$ in boxes $46$ to $100$
What is the maximum possible number of different types of items?
- $6$
- $3$
- $5$
- $4$