Is there a way to prove the 'Austrian deal' part of the 'Einstein' card trick?

Question

I watched this video the other day.

1. You have between 4 and 8 cards.
2. Look at the bottom one and memorise it.
3. Move the top card to the bottom; do this 8 times in total (like the number of letters in the word 'Einstein').
4. 'Austrian deal': remove the top card, move the next one to the bottom.
5. Repeat step 4 until you have only one card left.
6. That is the one you memorised.

I managed to figure out that, if you start with $4 \le n \le 8$ cards, the position of the bottom card (being $n$ at the beginning, so counting from the top set to $1$) at the end of step 3 becomes:

$$m = n - 8 \bmod n = n - 8 + \lfloor \frac 8 n \rfloor \cdot n$$

This by noticing that during step 3 the card loses one position at a time, until it gets to position $1$, after which it goes back to the bottom, i.e. $n$.
So you can ignore the cycles that take the bottom card back to the bottom (the number of these cycles is of course $\lfloor \frac 8 n \rfloor$), and the 'final' position after step 3 is only determined by the remainder $8 \bmod n$.

The 'Austrian deal' part seems to follow a similar logic.
However, I cannot figure out what the remainder is, as $n$ is no longer constant, but it changes at each step.
Of course one needs to prove that after step 5, $m$ invariably reduces to $1$.
Algorithmically it is easy to show that it is the case, but I am wondering if any other approach is possible.

Any ideas/suggestions?

It is clear that all cards that have an odd position at the end of step 3 are removed in steps 4 and 5, and only the originally even ones are left.
I suppose that's why the trick is limited to 4 to 8 cards: $m$ is even $\forall n \in \mathbb N, 4 \le n \le 8$, but it would be $1$ for $n = 3$ or $n = 9$, so at step 4 you would immediately discard the card you want to find.

---

EDIT: possible solution

After some more thought. May not be very general or rigorous though.

At the end of step 3 we have a pile of $n$ cards, and our chosen one is at position $m$ counting from the top, $n,m$ being defined as above.
For our card to reach position $1$, $m-1$ 'Austrian deal' steps are required, at the end of which $p = n - \lceil \frac {m-1} 2 \rceil$ cards remain.
As $m$ is even, $p = n - \frac m 2$.
Using the definition of $m$: $p = 4 + \frac n 2 \cdot (1 - \lfloor \frac 8 n \rfloor )$.

So, $n = 4, m = 4 \implies p = 4 + \frac n 2 \cdot (1 - 2) = 2$.
Our card is in position $1$ after $4-1=3$ 'Austrian deal' steps, thus the last action was to remove a card. The next steps are to move the top card (ours) to the bottom, remove the new top one, and our card is the only one left.

For all other values of $n \ge 5$: $p = 4 + \frac n 2 \cdot (1 - 1) = 4$.
I.e. our card reaches the top when there are exactly $4$ cards left, regardless of how many cards we started with.

As $m$ is always even, we reached this configuration in an odd ($m-1$) number of 'Austrian deal' steps, thus the last action was to remove a card.
The next step is to move the top card (ours) to the bottom.
This takes us to the exact same configuration that resulted from $n = 4$, and that invariably leaves our card as the last left at the end.

What do you think? Does this make sense?
Would you approach it differently?

Very interesting though; I wonder how people come up with these things, because it's perhaps possible to explain them a posteriori, but to invent them in the first place does not seem so trivial.

---

EDIT 2 examining cases for larger $n$

Just for fun, I tried to figure out if the trick would work for any $n > 8$.

Here's my reasoning.
We know from the above that after step 3 the position of the card is $m = n - 8 + \lfloor \frac 8 n \rfloor \cdot n$.
When $n > 8$, this reduces to $m = n - 8$, as clearly by moving 8 cards from the top to the bottom, our card never cycles back all the way to the bottom.
Knowing that $m$ must always be even for our card to not be discarded during the 'Austrian deal', we know that $n$ must be even, too.

The trick will work only if get to a final step where our card is moved to the bottom and there are only 2 cards left.

We already know that our card, in position $m = n - 8$ after step 3, will go back to the bottom for the first time during the 'Austrian deal' after $\frac m 2$ cards have been removed.
Thus $p = n - \frac m 2 = n - \frac {n-8} 2 = 4 + \frac n 2$.
At that point our card is at the bottom, at a position equal to $p$ itself, thus, always assuming that $p$ is even so our card does not get discarded, $\frac p 2$ cards must be removed to make another full cycle and get our card back to the bottom. Then our card is in position $\frac p 2$, and half of that number of cards ($\frac p 4$) must be removed; and so on, until we are left with exactly $2$ cards, provided that in none of these cases our card is an odd position.

So the sequence of number of cards left at each step is:
$$\{n, 4 + \frac n 2 = p, p - \frac p 2 = \frac p 2, \frac p 2 - \frac p 4 = \frac p 4, ..., \frac p {2^q}\}$$

The trick will work if:

$\exists q \in \mathbb N :\frac p {2^q} = 2$

$(4 + \frac n 2) \cdot \frac 1 {2^q} = 2$

$...$

$q = log_2 {(2 + \frac n 4)}$

$q$ can only be an integer when $2 + \frac n 4$ is an integer power of $2$:

$2 + \frac n 4 = 2^k$

$...$

$n = 4 \cdot (2^k - 2), k \in \mathbb N, k \ge 3$

If this is correct, the trick should work for:

$n = \{24, 56, 120, ...\}$

which appears to be matching this recurrence equation:

$n_{k+1} = 2 \cdot n_k + 8$

Answer 1

Ok. First of all, I really had a hard time comprehending your solution so thanks for that!

I could follow with your formulations till your solution started.

So let x be the number of Austrian deals after which the mth card comes to the first

Now, for all n excluding 8,

m = n - 8%n

= n -(8-n)

= 2n - 8

therefore as you have mentioned m will be always even

for 8 however, it is odd( n - 1 )

Now if m were even

on first round of step 4

1,2,3,......m,.....n

-> 3,.....m,.....n,2

Now it is clearly visible that the position of the m card is now m-2 and the total number of cards is m - 1

therefore if m is even, on x Austrian deals

m - 2x = 1

(m - 1)/2 = x, which is not possible as it will not be an integer

Also one can easily observe, just how you have mentioned that every odd card will be eliminated in first cycle of step 4

therefore mth card comes to the first place when there are n - x cards left, that is n - (m-1)/2 cards left only and if m is odd

Although, given that I could hardly understand your solution, please do tell me if there has been some misunderstanding