0
$\begingroup$

I was participating in a high-school math olympiad qualification contest and this was one of the problems I didn't manage to solve. The solutions will be posted in a month or so, but I'm very eager to know how I could have solved it so I was wondering if someone could help me :)

The problem:

There are $3n$ coins on a pile, either heads or tails up. In a move you can take the top $1\leq m\leq 3n$ coins, pick them up, flip them and put them back on the main pile. Show that no matter what the pile looked like at first, you can reach all possible orderings of heads or tails in the pile with at most $4n - 1$ moves.

I was thinking of representing the orderings as binary numbers (for e.g. head head head tail = 1 1 1 0), so there are $2 ^ {3n} = 8 ^ n$ possible orderings and thought that the solution will have something to do with logs base $2$ but didn't get much further.

$\endgroup$
4
  • 3
    $\begingroup$ While this is a problem that can be resolved by mathematical reasoning, you have presented Readers with a "bare problem statement" and it might be closed for lack of context. There are several ways to supply context, such as what motivates the problem, where you encountered it, or what resulted from research done before posting. Please edit the body of the Question to supply context. $\endgroup$
    – hardmath
    Commented Sep 29, 2021 at 15:56
  • $\begingroup$ Can $\ m\ $ have any value? If so, there appears to be something missing from the statement of the problem, since otherwise there's a reasonably obvious solution in at most $\ 3n\ $ moves. Successively put each of the coins $\ 3n, 3n-1, \dots, 1\ $ into its proper orientation in the desired configuration by either reversing that coin, if necessary, as well as all those above it, or leaving it alone, if it's already in its proper orientation. $\endgroup$
    – lonza leggiera
    Commented Sep 30, 2021 at 7:59
  • $\begingroup$ @lonzaleggiera If you flip a stack of coins, their order is reversed too. They don't flip in place, except when you just flip over the top coin. You can of course flip the $k$th coin by first flipping over the top $k$ to bring the coint to the top, then flipping over the top coin, and then flipping the top $k$ coins to put it back into position. This leads to a solution of at most $9n$ moves. $\endgroup$
    – Jaap Scherphuis
    Commented Sep 30, 2021 at 8:18
  • $\begingroup$ @Jaap Scherphius Ok, thanks. That should have been obvious, but simply didn't occur to me! $\endgroup$
    – lonza leggiera
    Commented Sep 30, 2021 at 8:27

1 Answer 1

Reset to default
2
$\begingroup$

We use induction on $n$. Suppose with at most $4n-1$ moves we can reorder any $3n$-pile to any possible ordering. Then consider any $3(n+1)$-pile: $c_1, c_2, c_3, ..., c_{3n+1}, c_{3n+2}, c_{3n+3}$ where $c_i$ is above $c_j$ for any $i<j$.

Suppose we could reorder $c_1, c_2, c_3$ to any possible ordering in at most three moves and then use one move to flip the entire $3(n+1)$-pile, we have essentially reordered $c_{3n+1}, c_{3n+2}, c_{3n+3}$. So with four moves we have essentially reduced our pile to a $3n$-pile.

By the inductive hypothesis we know how to reorder a $3n$-pile to any possible ordering using at most $4n-1$ moves. So in total we use at most $4+4n-1=4(n+1)-1$ moves which means we are done.

Now we just need to prove the base case, i.e. that we can always reorder a $3$-pile to any possible order using at most three moves. I'll let you do this cause imma tired.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .