A proof by contradiction worded example

Question

So I have this question.

"There are 101 buttons up to 11 different colors in a box. Show that either there are 11 buttons of the same color in the box or there are 11 buttons all in different colors in the box."

I need to prove this by contradiction but I am not sure how to derive the contradiction.

This is all I have done so far

Proof by contradiction -

Assume that neither are there 11 buttons of the same color in the box and neither are there 11 buttons of all different colors in the box.

How can I use this to derive a contradiction?

Answer 1

Suppose the proposition is not true.

There are 10 or fewer different colors of buttons in the box and there are 10 or fewer of each color of button.

There are at most 100 buttons in the box.

This creates a contradiction, as there are 101 buttons in the box.

The proposition must be true.

Answer 2

Proceed in two steps:

• First, assume that it's not the case that there are 11 buttons all of the same color. That would imply that, at most, you have 10 buttons per color. But, since you have 101 buttons in all, this would also imply that there are 11 buttons all of different colors.

• Second, assume that it's not the case that there are 11 buttons all of different colors. This would imply that you have at most 10 colors among all 101 buttons. However, this would also imply that there must be 11 buttons of the same color.