last number

[razorfane]

I think this is a pretty hard question:

 

All the whole numbers from 1 to 2002, including the both of them, are written on a chalkboard in increasing order: 1, 2, 3... 2001, 2002. Then, the first number is erased, then the fourth number, then the seventh number, then the tenth number and so forth erasing all the numbers that occupy a place in the form 3k+1.

 

In the new list of numbers(after the first erasing) the same procedure is applied, erasing all the numbers occupying a place with the form 3k+1. This same process is repeated until all the numbers are erased from the chalkboard. What number is erased last?

[dan19_83]

well a lot of views and still no reply so it is obviously a hard one.

 

I thought it would be simple at the start and it would be one of the last few numbers but that turned out to be way out.

 

mathematically, i can't figure out a way to do it, but at a guess, I would say the answer is somewhere near 1000.

[Dave]

I can't figure this one out myself Then again, I do suck at these kind of problems.

[dan19_83]

I think the main problem starts when you eliminate the first line of numbers. then you've got a sequence like 2, 3, 5, 6, 8, 9..... and so on.

 

I think there are only two ways of doing this puzzle:

1. Write all the numbers down and start eliminating them one by one (if anyone does that then you are a great, big loser!!)

2. A mathematical formula is required, mostly likely where the numbers are replaced with ,for example, a sequence of x, x+1, x+2..... and so on.

 

I think number two is the best option(!) but saying that I will probably get frustrated and do 1!

[Ducky Havok]

1,860 ..... and god damn my hand hurts

[Dave]

You didn't work it out by hand, surely?

[Algebracus]

2002 = 3*667 + 1, so after one elimination we have 2002 - 668 = 1334 numbers left. Going on,

1334 = 3*444 + 2, so after 2 eliminations we have 1334 - 445 = 889 numbers left.

889 = 3*296 + 1, so after 3 eliminations we have 889 - 297 = 592 numbers left.

592 = 3*197 + 1, so after 4 eliminations we have 592 - 198 = 394 numbers left.

394 = 3*131 + 1, so after 5 eliminations we have 394 - 132 = 262 numbers left.

262 = 3*87 + 1, so after 6 eliminations we have 262 - 88 = 174 numbers left.

174 = 3*57 + 3, so after 7 eliminations we have 174 - 58 = 116 numbers left.

116 = 3*38 + 2, so after 8 eliminations we have 116 - 39 = 77 numbers left.

77 = 3*25 + 2, so after 9 eliminations we have 77 - 26 = 51 numbers left.

51 = 3*16 + 3, so after 10 eliminations we have 51 - 17 = 34 numbers left.

34 = 3*11 + 1, so after 11 eliminations we have 34 - 12 = 22 numbers left.

22 = 3*7 + 1, so after 12 eliminations we have 22 - 8 = 14 numbers left.

14 = 3*4 + 2, so after 13 eliminations we have 14 - 5 = 9 numbers left.

 

Among 9 numbers, the 8th is the last one erased.

Among 14 numbers, the 8th not in the form 3k + 1 is 12.

Among 22 numbers, the 12th not in the form 3k + 1 is 18.

Among 34 numbers, the 18th not in the form 3k + 1 is 27.

Among 51 numbers, the 27th not in the form 3k + 1 is 41.

Among 77 numbers, the 41st not in the form 3k + 1 is 62.

Among 116 numbers, the 62nd not in the form 3k + 1 is 93.

Among 174 numbers, the 93rd not in the form 3k + 1 is 140.

Among 262 numbers, the 140th not in the form 3k + 1 is 210.

Among 394 numbers, the 210th not in the form 3k + 1 is 305.

Among 592 numbers, the 305th not in the form 3k + 1 is 458.

Among 889 numbers, the 458th not in the form 3k + 1 is 687.

Among 1334 numbers, the 687th not in the form 3k + 1 is 1031.

Among 2002 numbers, the 1031th not in the form 3k + 1 is 1547.

 

So my answer is 1547. This might be wrong, but the underlying algorithm is correct and should not be too hard to see.

 

 

More to say: Let f(n) be the answer in the general case (n instead of 2002). Then f(n) = int(1.5*f[int(2n/3)]).

[bloodhound]

algebracus, you did the same thing i did. but i gave up after the 4th wave of elimination as i couldn't be bothered anymore.

[dan19_83]

damn ducky havok, well done if you wrote all the numbers out and you got the answer right (ya big loser!)! just kidding.

 

The mathematical way that was shown was what I was doing but I gave up very early also. Why do you only go as far as 13 eliminations when there are still nine numbers left?

[razorfane]

Among 9 numbers, the 8th is the last one erased.

Could you explain this deduction, please. I'm also working on the problem, btw.

[Ducky Havok]

I didn't write EVERY number out... most though. What I did was started until about 50, then started crossing out until I found a pattern. Then I found a pattern that went 5,3,4,2,4,3,5,1 and then repeated (those numbers being the gap between the numbers. Ex. 5, 8, 12, 14, 18, 21, 26, 27). I also did it in columns on 27 lined paper, so instead of having to go through and mark every single one out, I could just do entire rows at a time.... I just hope I didn't miss a number there somewhere.... I think I would die.

[Algebracus]

I stopped at 13 elimination rounds because I found it easier to just start working with nine numbers than going on until I only had one number left. The deduction for nine numbers is immeadiate:

1 2 3 4 5 6 7 8 9

2 3 5 6 8 9

3 5 8 9

5 8

8

 

OK, I will do the rest of it, then (not because it is necessary, but why not?)

 

9 = 3*2 + 3, so after 14 eliminations we have 9 - 3 = 6 numbers left.

6 = 3*1 + 3, so after 15 eliminations we have 6 - 2 = 4 numbers left.

4 = 3*1 + 1, so after 16 eliminations we have 4 - 2 = 2 numbers left

2 = 3*0 + 1, so after 17 eliminations we have 2 - 1 = 1 number left.

 

Among 1 number the last one singled out is, naturally, 1.

Among 2 numbers the 1st not in the form 3k + 1 is 2.

Among 4 numbers the 2nd not in the form 3k + 1 is 3.

Among 6 numbers, the 3rd not in the form 3k + 1 is 5.

Among 9 numbers, the 5th not in the form 3k + 1 is 8.

[dan19_83]

Thanks for explaining it a bit better. I see where you came from now and it looks like a good guess.

 

I had an idea of putting all the numbers into three columns in microsoft excel. This would only take a few seconds. All that would be left to do is delete the third column and arrange the two columns left into three coulmns again and then delete the third column. Do thid until you have only one number left. Just two questions:

 

1. Would this work?

2. How do you change all the numbers from two columns into three columns?! I was trying this for ages and I couldn't do it.

 

Hope that made sense!

[Ducky Havok]

dan19 83, wouldn't you have to delete the first column though, not the 3rd? Since it started off with 1, then 4 and so on. I suck at using excel though so I wouldn't know how to do it

[dan19_83]

sorry your correct ducky havoc. wasn't thinking straight! It would work though, wouldn't it?

The only problem I have is trying to arrange two columns into three

[Algebracus]

I was wondering about the more general case in which we substitute 2002 with n and 3k + 1 with [MATH]mk + a[/MATH]. First, we have the trivial observations that at the end the a - 1 first numbers are not erased, meaning we have too many numbers left for a > 2, and for a = 2, the last erased number is surely 1 (since we for each round having more than one number left surely decrease the number of numbers, erasing the second number, and therefore at some moment the second number also is the last number). The only case of interest is therefore a = 1.

 

The simple algorithm to solve the problem is the same as before, and based on the same simple result: Suppose the last erased number for a particular n, letting m be unchanged, is [MATH]f(n)[/MATH]. Then, we first write [MATH]n = mn' + r, r = 1, 2, ..., m.[/MATH]. After the first round of erasing, we have [MATH]n - n' - 1 = n - int[n/m] - 1 = int[\frac{m - 1}{m}n][/MATH] numbers left, and we find that [MATH]f(n) = int(\frac{m}{m - 1}f(int[\frac{m - 1}{m}n]).[/MATH]