Anastasia wants to write the numbers from 1 to 8 into the cells of a 2x4 grid. The number in each cell must be smaller than the number in the cell to its right and smaller than the number in the cell below it. In how many different ways can Anastasia fill the grid? So first observe that if we look at the top left cell, the number there must be smaller than every other number. Clearly it's smaller than all the numbers in the rest of its row. It's also smaller than the number below it, and this number right below it is smaller than the rest of the numbers in its row. This means that this top left cell is smaller than everything, so it has to contain a 1. Similarly, the bottom right cell is bigger than everything else, and it must contain the 8. Now let's look at where we can put the 2 and the 7. So the 2 must either go directly underneath or directly to the right of the 1. That's because in every other cell in this diagram, there would be another square that would have to be smaller than it in addition to the 1. Everything in this bottom row, these 3 in the bottom row, have another square that's directly left of them, and whatever would go in that square directly left would have to be smaller than the 2. So we can't have a 2 in any of these 3. And we also cannot have a 2 in these 2 because they also have a square that's directly left where we would have to put something smaller than a 2, and there is nothing else that's smaller than the 2 that we can place there since we already have the 1 placed. So the 2 either goes here or the 2 goes here. Similarly, the 7 either goes here or the 7 goes there. And so this creates 4 possibilities that are listed here. We will look at each possibility and see how many ways it gives us to fill the grid. So in case 1, in both rows, we have 2 missing numbers, and they could be any 2 of the 4 remaining numbers. And then once we pick which 2 numbers go in which row, then we have to list those 2 numbers in increasing order. So for example, if we pick 3 and 5 to go in this first row, we would put first the 3 and then the 5, and then the bottom row first the 4 and then the 6. There's 6 ways to pick 2 out of the 4 numbers that are remaining, so we have 6 possible ways to fill in the grid in this first case. In the second case, we have this bottom rightmost empty cell, and that has to contain a number that's larger than all the numbers in the other empty cells. So that has to be a 6. Now we can put any of the 3 remaining numbers in the cell above the 6, they all fit, and then the other 2 would have to fit in the bottom row in their natural order, and that works as well. So there's 3 possibilities here. Case 3 is similar to the second case, this cell is going to have to contain the 3. It's smaller than everything else. And then after that, we can pick any of the 3 remaining numbers to fit in the cell between the 2 and the 7, and the other 2 fit into the first row in their natural order. In the fourth case, we both know that this cell contains a number smaller than all the other empty cells, so it has to be a 3, and that this cell in the bottom right contains a number bigger than all the other empty squares, and has to be a 6. So we only have 2 numbers left to assign, and we can assign them in either order. So there's 2 possible fillings. So in total across the 4 cases, we have 6 plus 3 plus 3 plus 2, which is 14 possible fillings, and the answer is E.

grid

arrangements

numbers

scenarios

complexity