Interesting math question

[stupidkid]

You have a deck of cards numbered from 1-1000 from top to bottom. You throw away the top card and put the next card on the bottom of the deck. You repeat this process until you have one card left. What is the number of this card?

What if there are 10000 cards?


A friend told me this problem and I was never able to solve it.

 

[Aluvus]

The first pass all the way through the deck will eliminate the odd-numbered cards.

The second pass will eliminate even-numbered cards (which is all that are left) not divisible by 4.

The third pass will eliminate cards not divisible by 8.

Etc. After each pass, all remaining cards are divisible by 2^n.

After each pass, you will have 1000/(2^n) cards left (where n is the number of completed passes).

The number of passes you need can be determined with the inquality:

2 > 1000/(2^n) > 1, where n must be an integer
n = 9

2^9 = 512

Your card is number 512.

For 10,000 cards, n=13 and 2^13 = 8192

I am mostly sure this result is correct.

 

[stupidkid]

That can't be right. According to your solution, it would be the same for 513 cards to 1023 cards in that the last card would be 512. This is obviously not true. Testing 10 cards and you see the last card is 4 instead of 8.

 

[CycloWizard]

Originally posted by: stupidkid
That can't be right. According to your solution, it would be the same for 513 cards to 1023 cards in that the last card would be 512. This is obviously not true. Testing 10 cards and you see the last card is 4 instead of 8.

25.

 

[Nathelion]

Originally posted by: stupidkid
That can't be right. According to your solution, it would be the same for 513 cards to 1023 cards in that the last card would be 512. This is obviously not true. Testing 10 cards and you see the last card is 4 instead of 8.

Umm... his solution is a solution to the problem at hand, not a general solution. To apply the proposed method to the case with cards from 513 to 1023, you'd have to re-number them to 1-501, that is, you'd have to deduct 512 from every card number.

Barring some mistake on my part, I believe the proposed solution is correct. I can find nothing wrong with it, at any rate.

 

[Aluvus]

Originally posted by: Nathelion

Originally posted by: stupidkid
That can't be right. According to your solution, it would be the same for 513 cards to 1023 cards in that the last card would be 512. This is obviously not true. Testing 10 cards and you see the last card is 4 instead of 8.

Umm... his solution is a solution to the problem at hand, not a general solution. To apply the proposed method to the case with cards from 513 to 1023, you'd have to re-number them to 1-501, that is, you'd have to deduct 512 from every card number.

Barring some mistake on my part, I believe the proposed solution is correct. I can find nothing wrong with it, at any rate.

On further reflection, I'm not actually sure it's valid for any cases where the total number of cards is not a power of 2. Eventually you reach a point where complting a pass would leave you with an odd number of cards, which I believe fubars it. Looks like a more rigorous solution is needed.

 

[esun]

1000 => 976
10000 => 3616

Here are the results for 1-20 cards:

1 1
2 2
3 2
4 4
5 2
6 4
7 6
8 8
9 2
10 4
11 6
12 8
13 10
14 12
15 14
16 16
17 2
18 4
19 6
20 8

The pattern is that if n is a power of 2, then the last card has value n. For n = 2^k + l, we have that the last number is 2*l.

Hence, for 1000, n = 2^9 + 488, so the solution is 2*488 = 976.

Hmm, thinking about this, it looks like you had half the solution.

So for 1024 cards, our first round leaves us with 2, 4, 6, ..., 1024, the second round leaves us with 4, 8, ..., 1024, third round 8, 16, 24, ..., 1024, etc. until we end up with just 1024, the solution.

However, if we have 1025 cards (let's say), then on our first pass, let's say I'm on card 1023. I toss it out, then I put 1024 on the bottom. At this point, my stack is 1025, 2, 4, 6, ..., 1024. Now I toss out 1025 and put 2 on the bottom. It is effectively saved this way. Now my stack is 4, 6, ..., 1024, 2.

There are 512 cards there, but they're rotated by 1, so instead of 1024 being last, 2 is. Therefore, 2 is the solution. I won't do a full induction proof, but it's pretty clear that if you used induction you could prove the observation I made earlier that for n = 2^k + l, the last card is 2^k if l = 0 and 2*l if l != 0.

 

[stupidkid]

Nice, makes sense, thanks.

 

[CycloWizard]

Oh, whoops... I numbered the cards backwards it looks like. So the top card is labeled #1 and the bottom is #1000?

 

[esun]

Yeah, looks like you reversed it. Though that problem is also interesting, since the pattern I get is:

1 1
2 1
3 2
4 1
5 4
6 3
7 2
8 1
9 8
10 7
11 6
12 5
13 4
14 3
15 2
16 1
17 16
18 15
19 14
20 13

So powers of 2 give 1 as the result (obviously), but then it counts down leading up to the next power of 2.

 

[pcy]

Suppose there are n cards in the deck, numbered 1 (top card) to n (bottom card).

n >1

Define m as the largest power of 2 less than n


The last card wil be card number (n-m)x2


Peter

 

[Nathelion]

Since I wanted to have a way to test all these theories, I made a little Java program that calculates what the last card will be. I don't know how to post files here, so I'll just post the source code:

Edit: Please be advised that you need both classes to run this code

//This is a simulation of a card problem, where every
//other card is removed in sequential passes until only
//one card remains. The first pass removes the odd cards.

import java.util.*;

public class OddCardProblem {

public static void main(String[] args) {
start();

}

public static void start() {
Scanner sc = new Scanner(System.in);
System.out.println("Hi! How many cards would you like you deck to have? ");
int size = sc.nextInt();
Deck myDeck = new Deck(size);

while(size != 1) {
size = myDeck.doPass();
}
System.out.println("Result: " + myDeck.getResult());
}
}

 

[Nathelion]

edit: I don't know why it started doing italics in the middle of everything.

//The deck class

public class Deck {

int[] array;
int end;

public Deck(int size) {
if (size%2 == 1)
size = size-1; //the odd number at the end will always be discarded
end = size-1;
array = new int[size];
for(int i = 0; i < size; i++) {
array = i+1;
}
printArray();
}

public int doPass() {
end = (end-1)/2;
for(int i=0; i <= end; i++) {
array = array[2*i+1];
}
printArray();
return end+1;
}

public int getResult() {
return array[0];
}

private void printArray() {
for(int n = 0; n <= end; n++) {
System.out.print("" + array[n] + " ");
}
System.out.println("");
}

}

 

[Nathelion]

Barring some mistake in my coding (which you are all welcome to proofread), the answer for 1000 cards is 512, so the OPs problem is definitely solved

After a little bit of testing, the pattern is clear. The last remaining number is the largest power of two smaller than n (with n being the number of cards).

Again, please proofread the java code. I don't think there are any mistakes in it, but I could always be wrong.

 

[Born2bwire]

Originally posted by: Nathelion
Barring some mistake in my coding (which you are all welcome to proofread), the answer for 1000 cards is 512, so the OPs problem is definitely solved

After a little bit of testing, the pattern is clear. The last remaining number is the largest power of two smaller than n (with n being the number of cards).

Again, please proofread the java code. I don't think there are any mistakes in it, but I could always be wrong.

You're missing in the class declaration:

boolean Life = false; //

 

[CycloWizard]

Originally posted by: Born2bwire
You're missing in the class declaration:

boolean Life = false; //

I solved the wrong problem in MATLAB. Life = Life--;

 

[esun]

I'm sorry, Nathelion, your code must be wrong, because 512 is incorrect. Your theory is also incorrect. For example:

Take cards 1 to 4 (each line lists the current deck in order):

0. n = 4: 1 2 3 4
1. Toss out 1: 2 3 4
2. Put 2 on the bottom: 3 4 2
3. Toss out 3: 4 2
4. Put 4 on the bottom: 2 4
5. Toss out 2: 4
6. Last card is 4

4 is not the largest power of two smaller than 4!

Try other small examples and you'll see this doesn't hold. Here is a correct Perl program which I used to generate my results:

#!/usr/bin/perl

my @cards = ();

# For loop just iterates over the list in parens and prints results
for my $j (1..20) {
    print "$j  ";
    &count($j);
    print "\n";
}

# This subroutine does the actual work
sub count {
    for my $i (1..$_[0]) {
        $cards[$i-1] = $i;
    }

    # Uncomment next line for version where cards count down from n to 1
    # @cards = reverse @cards;

    while (@cards > 1) {
        shift @cards; # remove first card and throw it away
        push (@cards, shift @cards); # remove first card, put it on the bottom
    }

    print $cards[0];
}

 

[esun]

Here's a Java implementation I just put together for kicks:

import java.util.*;

public class cards {
public static void main(String[] a) {
int n = 1000;
System.out.println(count(n));
}

public static int count (int n) {
// Create array counting from 1 to n
int[] cards = new int[n];
for (int i = 0; i < n; i++) {
cards[ i ] = i+1;
}

while (cards.length > 1) {
// Remove first card
int[] cards1 = new int[cards.length-1];

for (int i = 0; i < cards.length-1; i++) {
cards1[ i ] = cards[i+1];
}

// Put next card on the end
cards = new int[cards1.length];

for (int i = 0; i < cards1.length-1; i++) {
cards[ i ] = cards1[i+1];
}
cards[cards.length-1] = cards1[0];
}
return cards[0];
}
}


Basically I manually shift and rotate arrays as a representation of the cards (I would've used an ArrayList if I could remember enough Java for it...). Change n and run it again for different stack sizes.

I had to put extra spaces since I indexed with the letter i (since the forum interprets square brackets around an i as italics).

I think your implementation is wrong in more than one way. You started doing simplifications on the program instead of just simulating what is happening.

For example, when constructing a deck of odd size, you immediately just remove the last card and make the deck of even size and work from there. This is incorrect behavior. Take a look at the simplest base case, n = 1. If you were to construct a deck of size 1, your code would shrink it to size 0 and you'd give an incorrect answer. The correct answer should be 1.

Yeah, you coded a completely different problem. You're basically doing what Aluvus did in code, which is wrong. Read the problem again and I think you'll see your mistake.

 

[pcy]

Hi,


I don't write java but I do write in other laguages. I'm trying to figure what this code is meant to achieve.


We already know the answer - 2 x (n - (2 * ((ceiling n log (2) n) - 1)))
note: 2 * ((ceiling n log (2) n) - 1) merely finds the largest power of two less than n

and I see no need to try to find the reult by a simulation.



Peter

 

[esun]

Well if you think the result is obvious, then there's no need to write a program. I suppose there's never a "need" to solve a problem via simulation. It can help confirm your results if you're uncertain of them, and it can help you figure out the result if you don't know where to start (by looking for patterns). It's a way to get the answer, then work backwards to reason why that is the answer.

Plus, there are obviously people in here that don't believe the answer (or at least solved the problem incorrectly), in which case a program to simulate the behavior could be useful. Then again, a complete proof would also be useful, but programs are more fun to write.

 

[Nathelion]

I meant to say that the answer was the largest power of 2 less than or equal to n, and you're right, I didn't consider the case n=1.

And you're right again, I didn't read the OPs problem correctly. I was assuming that you went through the deck once, removing every other card, and that you then started over fresh from the top. But that's an entirely different problem (and, although I believe I simulated that problem correctly, it doesn't have much bearing on the ropic of this thread).

I'll try to convince myself of the answer...

 

[pcy]

Hi,

Originally posted by: esun
Well if you think the result is obvious, then there's no need to write a program. I suppose there's never a "need" to solve a problem via simulation. It can help confirm your results if you're uncertain of them, and it can help you figure out the result if you don't know where to start (by looking for patterns). It's a way to get the answer, then work backwards to reason why that is the answer.

Plus, there are obviously people in here that don't believe the answer (or at least solved the problem incorrectly), in which case a program to simulate the behavior could be useful. Then again, a complete proof would also be useful, but programs are more fun to write.

Simulations can have bugs at least as often as proofs are invalid....

I tried to produce a genuine proof, but without the matematics and symbolic logic fonts it is almost impossible.

I've posted the result twice now, and it sems pretty obvious to me. You get to it by doing one pass which reduces the size of the deck to the highest power of two less than the initial size of the deck, and then sucessively halving the size of the deck with complete passes.

All the sucessive complete passes leave the bottom card of the deck unchanged as others had already observed, so the only remaing question is the card that will be on the bottom after you have finished the first pass.

Each turn (i.e remove one card and put the next on the bottom) reduces the size of the deck by one, and j turns leaves card 2 x j on the bottom.


So if the deck has n cards, and m is the largest power of 2 less than n, and n -m = j

the answer is card 2 x j



Peter

 

[esun]

True, but it's easier for many to check whether a line of code actually shifts then rotates an array rather than checking that your statement of the solution is correct.

Again, math and simulation can both be used to solve the problem. If you can see the math more easily, then that's fine. Doesn't mean simulation can't be useful for some.