1
$\begingroup$

In one board game, each player has a unique 4 x 4 grid with squares randomly labeled with each integer from 1 to 16. As the integers 1 to 16 are randomly called, each player puts an "X" in the square containing that integer. The first player with an "X" in all four squares in any row, column or diagonal wins. At most, how many integers must be called to get a winner?

For this problem, they say the answer is supposed to be 13, and I guess that's like 4 + 4 + 4 + 1 (so three row/column/diagonals of "X" 's plus 1), but why's that so?

$\endgroup$
2
  • 1
    $\begingroup$ I get the feeling that for several of your questions, you haven't spent enough time thinking about them yourself, especially if you're doing this to improve: Before you post in here, I suggest you really struggle with finding a solution; try every method you've got, write down a lot of examples and put them into different systems with different ordering and see if you can spot the pattern. Then be frustrated and then sleep on it (that usually helps a lot)! Then try again, and so on. Only when you've got absolutely nothing left to try, ask in here. $\endgroup$ Feb 24, 2016 at 8:37
  • 1
    $\begingroup$ More likely to be $3+3+3+3+1=13$ $\endgroup$
    – Henry
    Feb 24, 2016 at 8:38

1 Answer 1

1
$\begingroup$

This is an example of the Pigeonhole Principle at work. Ask yourself this: what is the greatest number of squares you can fill with an "X" and still not win? It's not hard to come up with a configuration with $3$ in each row and column, for a total of $4 \times 3 = 12$. For instance, this works: $$ \begin{array}{c|c|c|c} \times & \phantom{\times} & \times & \times \\ \hline \times & \times & \times & \phantom{\times} \\ \hline \times & \times & \phantom{\times} & \times \\ \hline \phantom{\times} & \times & \times & \times \end{array} $$

Any additional "X" will force a win, so with $12 + 1 = 13$ numbers called, a winner is guaranteed.

$\endgroup$
1
  • $\begingroup$ Thanks, Henry. Sometimes normal $\LaTeX$ markup doesn't work with MathJax. I'm not sure what was glitching there, but it looks nice now. :-) $\endgroup$ Feb 24, 2016 at 8:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .