[Math] Creating 6 Digit Numbers Whose Adjacent Digits are Relatively Prime

combinatoricsprime numbers

Six-digit integers will be written using each of the digits $1$ through $6$ exactly once per six-digit integer. How many different positive integers can be written such that all pairs of consecutive digits of each integer are relatively prime? (Note: $1$ is relatively prime to all integers.)

The pairs of numbers that are relatively prime from $1-6$ are: $1:2,3,4,5,6$ and
$2:3,5$ and $3,4,5$ and $4,5$ and $5,6$. Now, what should I do from here.

Best Answer

Edit 2: If you consider the analogous question for five digit numbers, then you will also find that the answer is $72$; so, perhaps someone can find a slick bijection between the two sets.

The technique for five digit numbers is relatively simple:

You need to avoid having $2$ and $4$ as adjacent; so, you can place them without constraints in $5(4) = 20$ places, but then subtract off the $8$ adjacent cases for $12$ in total.

Once $2$ and $4$ are placed, the $1$, $3$, and $5$ can be placed in any order among the three empty slots, i.e., $3! = 6$ ways, yielding $12 \cdot 6 = 72$ as the total.


Edit 1: Here is an AoPS link that also finds the answer to be 72. The underlying technique is to place the 2, 4, and 6 first; then, you figure out where the remaining digits can go. For those who do not wish to click through, here is an image of the text:

enter image description here


Brute force, in case others have craftier ways and want to check/verify; seventy two in total:

123456 143256 165234 165432 213456 214356 216534 216543 231456 231654 234156 234165 234516 234561 235416 235614 253416 254316 256134 256143 321456 321654 325416 325614 341256 341652 345216 345612 412356 413256 416523 416532 431256 431652 432156 432165 432516 432561 435216 435612 452316 453216 456123 456132 523416 543216 561234 561432 612345 612354 612534 612543 613254 613452 614325 614352 614523 614532 615234 615432 651234 651432 652134 652143 652314 652341 653214 653412 654123 654132 654312 654321

Related Question