Maths Olympiad Prep

Track / Stage 4 / 172 of 340 #432 of 1964

Problem 432

AMC 12 late, AIME early
Combinatorics Difficulty 4.9 Multiple choice

5. Arrange the numbers 1,2,3,4,51,2,3,4,5 in a row, with the last number being odd, and such that the sum of any three consecutive numbers is divisible by the first of these three numbers. How many arrangements satisfy these conditions?

Pick one

Official solution

5.D.

Let a1,a2,a3,a4,a5a_{1}, a_{2}, a_{3}, a_{4}, a_{5} be a permutation of 1,2,3,4,51,2,3,4,5 that meets the requirements.

First, for a1,a2,a3,a4a_{1}, a_{2}, a_{3}, a_{4}, there cannot be two consecutive even numbers, otherwise, all numbers after these two would be even, which contradicts the given conditions.

Second, if ai(1i3)a_{i}(1 \leqslant i \leqslant 3) is even and ai+1a_{i+1} is odd, then ai+2a_{i+2} is also odd. This means that an even number must be followed by two or more odd numbers, unless the odd number following it is the last number.

Therefore, a1,a2,a3,a4,a5a_{1}, a_{2}, a_{3}, a_{4}, a_{5} can only be even, odd, odd, even, odd. There are the following 5 scenarios that meet the conditions:
2,1,3,4,5;2,3,5,4,1;2,5,1,4,34,3,1,2,5;4,5,3,2,1. \begin{array}{l} 2,1,3,4,5 ; \quad 2,3,5,4,1 ; \quad 2,5,1,4,3 \text {; } \\ 4,3,1,2,5 ; \quad 4,5,3,2,1 . \\ \end{array}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.