Problem:
In how many ways can 3 bottles of ketchup and 7 bottles of mustard be arranged in a row so that no bottle of ketchup is immediately between two bottles of mustard? (The bottles of ketchup are mutually indistinguishable, as are the bottles of mustard.)
Solution
Solution:
22
Consider the blocks of consecutive bottles of ketchup in such an arrangement. A block of just one bottle must occur at the beginning or the end of the row, or else it would be between two bottles of mustard. However, a block of two or three bottles can occur anywhere. We cannot have three blocks of one bottle each, since there are only two possible locations for such blocks. Thus, we either have a block of one bottle and a block of two, or one block of all three bottles. In the first case, if the single bottle occurs at the beginning of the row, then anywhere from 1 to 7 bottles of mustard may intervene before the block of 2 ketchup bottles, giving 7 possible arrangements. We likewise have 7 arrangements if the single bottle occurs at the end of the row. Finally, if there is just one block of three bottles, anywhere from 0 to 7 mustard bottles may precede it, giving 8 possible arrangements. So, altogether, we have configurations.
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.