Sometimes a seemingly minor rule is enough to make impossible what seems only difficult. The key is to find what remains invariant.
The impossible row of cards
Riddle statement
You start with the row of cards
4, 2, 6, 1, 5, 3.
The only operation allowed is to exchange two adjacent cards whose sum is odd.
Can
1, 2, 3, 4, 5, 6 be reached in this way?
Show solution
Solution
Answer: No, it is impossible.
You can only exchange adjacent cards with an odd sum, that is, an even one with an odd one. Two even or two adjacent odd ones can never be exchanged.
This implies that the relative order of the even cards to each other is an invariant, and the same goes for the odd ones.
In the initial row:
- even ones: $4, 2, 6$
- odd: $1, 5, 3$
In target row:
- even: $2, 4, 6$
- odd: $1, 3, 5$
Both relative orders have changed compared to the initial state. Since the invariant prohibits it, the transformation is impossible.