Thank you to Stacey from Wales High School,
Dmitri from Cork in Ireland, and many others for ideas about what's
going on here.
If you start with 8 cards you end up with the number 8, and if you
start with 9 cards you end up with the number 2.
If you start with 2 or 4 or 8 or 16 the last card is 2, 4, 8 or 16
to match.
After any one of those, for example 9 after 8, the last card moves
on by 2.
So 8 cards finishes with 8, 9 cards finishes with 2, 10 cards
finishes with 4, 11 cards finishes with 6, and so on until 14
finishes with 12, 15 finishes with 14 and 16 (the next power of 2
after 8) finishes with 16.
Then it all happens again, in the same way : 17 cards finishes with
2, 18 cards with 4 and so on.
Here's why that
happens
For example starting with : 1 2 3 4 5 6 7 8
Every second card is kept and we get : 2 4 6 8
Half the cards have gone, the second card of each pair.
The same thing happens and we are left with: 4 8
Half the cards have been lost again, as before the second card in
each pair has gone.
Finally 4 8 goes down to 8
It's always the second card of the pair that stays in.
So when the number of cards is a plain power of 2, like 8, only
half the cards stay, then only half of those, and so on until it's
just the end card, like 8, that remains.
Now for the other numbers
:
Start at a plain power of two, like 8, and increase by 1, that's 9,
and make the first move of 'one out and one under'.
Now we have 8 cards again, we had 9 but one's gone out.
And for 8 we know what will happen, we'll be left with the last
card in that order as the final card remaining.
So what's the order ?
We've done one out and one under so all positions will have moved
by two cards.
So we don't finish on the 8, or the next card (1  it's out), but
the one after that, that's the 2.
Now think about 10 cards.
Make the first move : 'one out and one under'.
And then there are 9 cards and we know that that will finish with
2, but all the positions have moved by 2 places, so the final card
is the 4.
The same thing happens again and again  when there's one more card
at the start the last card moves 2 on from the previous
result.
Nice reasoning !
Here is a table sent in to us by
children at Weston Turville CE School:
Start Card 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
Card Left 

2 
2 
4 
2 
4

6 
8 
2 
4 
6 
8 
10 
12 
14 
16 
Start Card 
17 
18 
19 
20 
21 
22 
23 
24 
25 
26 
27 
28 
29 
30 
31 
32 
Card Left 
2 
4 
6 
8 
10 
12 
14 
16 
18 
20 
22 
24 
26 
28 
30 
32 
In the table shown you can see that every time that you have a
number of cards to start with that is a power of $2$ i.e. $\{2,
2^2, 2^3, 2^4, 2^5, 2^6\}$ then it results in itself.