Pigeonhole, using "OR"

Question

I have ten (10) items each of six (6) different colors (so 60 items total).

For easier reading, I'll call the colors {A, B, C, D, E, F}.

I would like to find the minimum number of items I need to have 3 A's OR 4 B's OR 5 C's OR 6 D's OR 7 E's OR 8 F's.

I think I'm having the most trouble grasping how the or works in this case.

My first thought was that, well, if I take $6*7 +1 = 43$ items then I ensure that I get at least 8 of some color, right?

And, in that case, I would have at least 7 of all the other colors, so I know that taking 43 items would satisfy the condition.

But can I do that with fewer than 43 items? I haven't been able to find a calculator or something of the sort for these questions, so I'm not sure how to check my work.

Answer 1

The maximum number of items for which all of the OR conditions fail is $$2+3+4+5+6+7=27$$ which can be realized by the selection $$2A,\;\;3B,\;\;4C,\;\;5D,\;\;6E,\;\;7F$$ where the coefficient indicates the multiplicity of the color.

Thus, any selection of $28$ items guarantees that at least one of the OR conditions is satisfied.

Answer 2

The answer is to have $2+3+4+5+6+7+1$.

I think the easiest way is to negate the requirement, so that ORs become ANDs. If none of the 6 conditions in the requirement is fulfilled, then you would have at most $2$ A's, AND at most $3$ B's, ..., AND at most $7$ F's. So you would have in total at most $2+3+4+5+6+7$ items, which is a contradiction.

Having only $2+3+4+5+6+7$ items doesn't work, because you could indeed have exactly $2$ A's, exactly $3$ B's, ..., exactly $7$ F's.

Answer 3

In such problems you should consider the worst case scenario.

The largest number of items of the same color is $8F$. So imagine you select $7F$. Next item you select must not be $F$ again, otherwise the selection process stops and it would not be the worst case.

Next largest number of items is $7E$. So you select at most $6E$.

Using this approach you can select: $$7F+6E+5D+4C+3B+2A=27.$$ without ending the process and being extremely unlucky (i.e. the worst case scenario). Now selection of any extra item of any color will end the process, because one of the colors will be as many as required by OR conditions. Hence the minimum number is $27+1=28$.

Answer 4

A solution to this problem can be visualized using "buckets". Assume that you had buckets for each of the colors, $A$ through $F$. Now to build towards the given condition, let's say you try to exhaustively avoid the condition. In other words, you try to color the items in such a way that when being placed in buckets, none of the counts violate the condition.

Before moving on, take a moment to realize that the condition still holds as long as: $|bucket\,A| \le 2, |bucket\,B| \le 3, |bucket\,C|\le4, \dots, |bucket\,F|\le7$.

Now, you try to maximize the number of items that you could place in color-related buckets while keeping the condition valid. You color 2 items in color $A$, 3 in $B$, and so on. Then you get $2+3+4+5+6+7 = 27$ items in all (this particular fact has been pointed out in one or two answers above). Now try to add as few as just one more item: what do you color it using? If you color it in color $A$, we have $|A|\not\le2$, since $|A|=3$. Similarly, for any of the other buckets, we violate the holding condition.

So indeed, 27 is the minimum. But I hope this answer helps you visualize why instead of just formulaically computing it.