CombinatoricsDifficulty 5.3AIME, harderFind the answerItaly
Problem:
Abelarda, Brunilda and Callisto, three old acquaintances, want to buy a house each among the 10 little houses in a row on the main street of the town. Since they cannot stand each other, they absolutely want to avoid being neighbors: they therefore wish the houses they buy to be pairwise non-adjacent. In how many ways can they buy houses so as to satisfy this condition?
Pick one
Solution
Solution:
The answer is (C). Let us first consider a slightly different problem: for now, let us leave the number of houses undetermined, and disregard the assumption that the houses cannot be adjacent. In this case, letting n be the number of houses on the street, we would have (3n) ways to choose which houses are inhabited by the three acquaintances and 3! ways to assign such houses to them.
At this point, to guarantee that the houses are not adjacent, it suffices to insert one house after the first choice and another after the second choice. Since we know that the houses on the street are 10 in total, this means that the n houses considered before are actually 8 houses. Hence the number we are looking for is (38)⋅3!=3!6⋅7⋅8⋅3!=336
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 translated into English from it; metadata (topic, difficulty) added by this project.