Question

There are five cards in a row with numbers from 1 to 100. Each adjacent pair must not differ by a multiple of 4. The remainder when each number is divided by 4 is written on a sixth card, in that order. How many different sequences can be written on the sixth card?

• A. \( 2^3 3 \)
• B. \( 4 3^4 \)
• C. \( 4^2 3^3 \)
• D. \( 4 3^3 \)

Hint:

For constraints on adjacent elements, model transitions. Start with all possible values for first element, then apply transition limits recursively.

Answer 1

The Correct Option is C

Each number can leave remainder 0, 1, 2, or 3 when divided by 4. So there are 4 possible values per card initially.
Let us denote the remainder on each of the 5 cards as a sequence of values: R₀ to R₄.

Condition: The difference between two adjacent numbers must not be divisible by 4.
That means: if two adjacent cards have the same remainder (i.e., difference \( \equiv 0 \mod 4 \)), it is invalid.

So from any remainder, the next can be any of the remaining 3 remainders (not equal to current).

Step 1: First card can have any of 4 remainders → 4 options.
Step 2–5: Each of the next 4 cards must differ in remainder from the previous → 3 options each.

\[ \text{Total valid sequences} = 4 \times 3 \times 3 \times 3 \times 3 = 4 \times 3^4 = \boxed{4 \times 3^4} \]

Alternatively:
\[ \boxed{4^1 \times 3^4} \]