© Zya Santuario, MATH+
Author: Anne Zander (University of Twente)
Challenge
The two elves Atto and Bilbo were assigned to wrap gifts. Instead of working, they prefer to admire the presents. They have just discovered the card game “Uno” and are playing their third round. Atto is losing yet again. Frustrated, he throws the cards on the table. Then he starts pondering: “In most card games, cards have attributes, such as a color and a symbol. Suppose I have a card game with n colors and m symbols, where n \geq 2 and m \geq 2, so that each color-symbol combination appears exactly once as a card. As the sole player, I draw a given number x of random cards, where x \geq 2, from the entire game. Can I always arrange these x cards in such a way that they can be discarded one by one no matter which cards I picked?” By “discarding,” Atto means that—apart from the first card in the sequence—each subsequent card must either have the same color or the same symbol as the previously discarded card.
We define x_{n,m} as the minimum number of drawn cards in a card game with n colors and m symbols such that it is always possible to find an order for discarding them. Which of the following statements is true?
Possible Answers:
1. x_{n,m} = (n-1)(m-1)
2. In a card game with 4 colors and 10 symbols, one can find a selection of 30 cards such that no discarding sequence is possible.
3. x_{n,m} = (n-2)(m-2)
4. A discarding sequence can always be found for any selection x of drawn cards.
5. x_{n,m} = (n-1)m-3
6. In a card game with 3 colors and 6 symbols, a sequence of 10 cards can always be discarded.
7. x_{n+1,m} = x_{n,m} + m + 1
8. x_{n+1,m+1} = x_{n,m} + m + n - 4
9. It holds that x_{4,6} = x_{3,8}
10. x_{n,m+1} = x_{n,m} + n - 1