Library / /697 of 740

, 2019

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

Wendy eats sushi for lunch. She wants to eat six pieces of sushi arranged in a $2 \times 3$ rectangular grid, but sushi is sticky, and Wendy can only eat a piece if it is adjacent to (not counting diagonally) at most two other pieces. In how many orders can Wendy eat the six pieces of sushi, assuming that the pieces of sushi are distinguishable?

Solution

Solution:

Call the sushi pieces $A, B, C$ in the top row and $D, E, F$ in the bottom row of the grid. Note that Wendy must first eat either $A, C, D$ , or $F$ . Due to the symmetry of the grid, all of these choices are equivalent. Without loss of generality, suppose Wendy eats piece $A$ .

Now, note that Wendy cannot eat piece $E$ , but can eat all other pieces. If Wendy eats piece $B, D$ , or $F$ , then in the resulting configuration, all pieces of sushi are adjacent to at most 2 pieces, so she will have $4!$ ways to eat the sushi. Thus, the total number of possibilities in this case is $4 \cdot 3 \cdot 4! = 288$ .

If Wendy eats $A$ and then $C$ , then Wendy will only have 3 choices for her next piece of sushi, after which she will have $3!$ ways to eat the remaining 3 pieces of sushi. Thus, the total number of possibilities in this case is $4 \cdot 1 \cdot 3 \cdot 3! = 72$ .

Thus, the total number of ways for Wendy to eat the sushi is $288 + 72 = 360$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.