Math Is Fun Forum

Euripides

Member

Registered: 2005-09-21

Posts: 2

last card standing problem

so heres the big question. I have a deck of 9 cards (numbered numerically 1-9) and they are stacked numerically so 1 is on top and 9 on bottom. I take the 1 and place it down, then I take the 2 on put it on the bottom of the deck. I repeat the process putting the 3 down  and placing the 4 on the bottom of the deck. I repeat this process taking one card and putting it down and the next card back on the bottom of the deck. If done right you end up with 2 as the last card. If you try it with 13 cards you get 10 as the last. So my question is whats the last card if i "X" number cards? Is there a formula relating to the number of cards and the last card?

ryos

Member

Registered: 2005-08-04

Posts: 394

Re: last card standing problem

I've made a start, but it's late and I need to go to bed. Maybe someone else can finish it, or I'll continue it later.

Anyway, you start by discarding 1 (an odd number), so in the first round, all odd numbers drop out.

In the second round, the "odds to the evens" drop out. That is to say, every other even, which, when you start at two (which you do), is every multiple of 4.

With each subsequent round, the distance (numerically) between each card in the deck doubles, like so:
Round   Distance
0           1
1           2
2           4
3           8

And so on. Also, with every round, the number of cards is cut in half.

We ought to be able to write some sort of series with this information. Also, whether you start with an odd or even number of cards has some significance.

Oh! I've got it! If you start with an odd number of cards, then the highest-numbered even comes out last. If you start with an even number of cards, then the middle card comes out last -- the middle of the evens, that is. So, if you start with a run from 1 - 30, 16 comes out. If you start with 1 - 31, 30 comes out.

There's probably an easy, compact way to explain this, but I'm too tired. Goodnight.

---

El que pega primero pega dos veces.

MathsIsFun

Administrator

Registered: 2005-01-21

Posts: 7,711

Re: last card standing problem

Goodnight. Dream about cards.

---

"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Euripides

Member

Registered: 2005-09-21

Posts: 2

Re: last card standing problem

But how does that work? When you try it with 13 you get 10 not 12.

ryos

Member

Registered: 2005-08-04

Posts: 394

Re: last card standing problem

Ok, I was writing the sequences out wrong. Let's try a few and see what happens:

1  2  3
    2

1  2  3  4
    2     4
           4

1  2  3  4  5
    2     4
    2

1  2  3  4  5  6
    2      4     6
            4

1  2  3  4  5  6  7
    2      4     6
    2             6
                   6

1  2  3  4  5  6  7  8
    2      4     6      8
            4             8
                          8

1  2  3  4  5  6  7  8  9
    2      4     6      8
    2             6
    2

1  2  3  4  5  6  7  8  9  10
    2      4     6      8      10
            4             8
            4

1  2  3  4  5  6  7  8  9  10  11
    2      4     6      8      10
    2             6              10
                   6

1  2  3  4  5  6  7  8  9  10  11  12
    2      4     6      8      10       12
            4             8                12
                          8

1  2  3  4  5  6  7  8  9  10  11  12  13
    2      4     6      8      10       12
    2             6             10
    2                            10
                                  10

1  2  3  4  5  6  7  8  9  10  11  12  13  14
    2      4     6      8      10       12        14
            4             8                12
            4                               12
                                             12

The pattern I see in the last cards is that they increase by 2 cyclically with each successively greater number of cards. In other numbers,

3    (2)
4    (4)
5    (2)
6    (4)
7    (6)
8    (8)
9    (2)
10  (4)
11  (6)
12  (8)
13  (10)
14  (12)

If this pattern holds, we should be able to predict the next numbers:

15  (14)
16  (16)
17  (2)
18  (4)
19  (6)
20  (8)
21  (10)
22  (12)
23  (14)
24  (16)
25  (18)
26  (20)
27  (22)
28  (24)
29  (26)
30  (28)
31  (30)
32  (32)
33  (2)

etc. The cycle "resets" when the next even in line is greater than the total number of cards in the stack.

Fortunately, it seems that the resetting follows another pattern; the cycle resets at every power of two! We now have enough info gleaned from patterns to write a general relationship between the number of cards and the last card standing!

First, some definitions to improve readability:
Last card standing = L
Number of cards to start with = n

L = 2 * [ n - (Largest power of 2 < n) ]

This just tells us how many steps we are above the last point the pattern was reset, and multiplies by 2 to convert from that to the last card standing.

Does it work? Let's try it on 6:
L = 2 * [6 - 4] = 4

Well, it worked for six. Whew! *pants*

I have no idea if this formula, which is just based off of observed patterns, actually works all the time, or is provable. I'll let somebody else figure that one out...;)

---

El que pega primero pega dos veces.