Math Olympiad Grade 7 Puzzle
In this blog, I wanted to summarize the approach which I used to solve this problem. This problem was asked in the 2021 class 7 German Math Olympiad
Problem:
Cindy has ten cards. Each card is numbered with one of the ten numbers from 1 to 10. Each of these numbers appears once. She wants to place many cards together in a row in such a way that for each pair of cards next to each other, the smaller of the two numbers is a divisor of the larger. She wants as many of these cards as possible.
a) Prove that Cindy cannot lay all ten cards this way.
b) Determine the largest possible number of such cards that can be arranged in such a manner.
Imagine we’re dealing with a deck of cards where each number from 1 to 10 represents a card. We’ll designate one card as our “Joker” — let’s say it’s 1. Why? Because in the sequence of numbers 1 to 10, prime numbers like 7 stand out. You might notice that 2, 3, and 5 are missing, but don’t worry! Each of them has multiples present elsewhere in the sequence. However, we can give ourselves a little flexibility by “sandwiching” 1 between 7 and 5. Despite 5 having a multiple (10), it’s only got one, so our “Joker” can fill in nicely there.
Now, let’s dive into solving this puzzle.
Possibility 1:
We start our row of cards with 7–1–5–10, as discussed. Since we’ve sandwiched 1 between 7 and 5, our next logical move is to go to 10. But we can’t use 1 again, so we need a 2. This leads us to: 7–1–5–10–2…
Now, there are only three possible ways to continue:
1. 7–1–5–10–2–4–8
2. 7–1–5–10–2–6–3–9
3. 7–1–5–10–2–8–4
As you can see, none of these sequences have all 10 cards. So, let’s check if any other possibility exists.
Possibility 2:
Now we start with 7–1 again, but this time we’ll keep 10–5 at the end. So, it looks like: 7–1-? -? -? -? -10–5. Following the logic from before, we add a 2 at the end. Since we’ve placed a 2 at the end, we won’t need a multiple of 2 at the start. So, we can choose 3, followed by 9 and then 6, because we can get from 6 to 2.
This gives us: 7–1–3–9–6–2–5–10.
As you can see, we’re short of 10 digits.
conclusion:
a) We’ve shown that the largest possible sequence satisfying the constraint is 9 digits.
b) We can achieve this with 9 digits using the sequence:
5–10–2–6–3–9–1–8–4.
Hope you enjoyed this brain teaser! Stay tuned for more challenges coming your way soon!