Competition problem — Number theory

Library / /146 of 348

Number theory Difficulty 4.8 AIME Find the answer

Find the number of ways in which the nine numbers $1,12,123,1234, \ldots, 123456789$ can be arranged in a row so that adjacent numbers are relatively prime.

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

The six numbers $12,123,12345,123456,12345678$ , and 123456789 are divisible by 3 , so they cannot be adjacent. However, arranging six numbers in a row with no two adjacent requires at least 11 numbers, which is impossible.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.