Help plz with counting

Find the number of ways of arranging the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 in a row so that the product of any two adjacent numbers is even or a mutliple of 3

Guest Feb 13, 2023

#1**+1 **

My answer got deleted, so here we go again: (Note: I'm not too confident with this answer)

We find the number of cases where a pair of products is not a multiple of 3 or even and subtract that from the total number of cases (10!)

The only way for a pair of numbers to have a product that isn't even or a multiple of 3 is if two adjacent numbers are both of the set: {1 ,5, 7}

Split this up into 3 cases:

Case 1 - All 3 numbers are next to each other: There are 3! ways to order them, 8 spots for this "block" and 7! ways to order the other numbers. This makes for \(7! \times 8 \times 3! = 241920\) cases

Case 2 - A pair of 2 numbers are next to each other and are on the edge (spots 9 to 10 and 1 to 2): There are 3 ways to choose the numbers, 2 ways to order them, 7 spots for the third number, 2 spots to put the numbers, and 7! ways to order the rest. This makes for \(7! \times 2 \times 7 \times 3 \times 2 = 423360\) cases.

Case 3 - A pair of 2 numbers are next to each other and they aren't on the edge: There are 3 ways to choose the numbers, 2 ways to order them, 7 spots to put them, 6 spots for the third number, and 7! ways to order the rest, which makes for \(7! \times 6 \times 7 \times 3 \times 2 = 1270080 \) cases.

So, there are \(10! - 1270080 - 423360 - 241920 = \color{brown}\boxed{1,693,440}\)cases.

BuilderBoi Feb 13, 2023