The integer numbers from $1$ to $2002$ are written in a blackboard in increasing order $1,2,\ldots, 2001,2002$. After that, somebody erases the numbers in the $ (3k+1)-th$ places i.e. $(1,4,7,\dots)$. After that, the same person erases the numbers in the $(3k+1)-th$ positions of the new list (in this case, $2,5,9,\ldots$). This process is repeated until one number remains. What is this number?
Problem
Source: Spanish Communities
Tags: number theory unsolved, number theory
spx2
27.05.2006 07:15
int a[2003],i,j; for(i=1;i<=2002;i++)a[i]=i; while(n>3){n=0; for(i=1;i<=2002;i+=3)a[i]=0; //erase numbers for(i=1;i<=2002;i++) if(a[i]!=0&&a[i-1]==0) {n++; j=i; while(!a[j--]);a[j]=a[i];a[i]=0 } //moves numbers together after erase //and counts numbers } //now one should just //show a to see the last 2 numbers
kodasjeib
27.09.2008 22:49
2,5,9... ? Why? 2,6,10..?
ElChapin
25.09.2012 07:23
It is actually 2,6,10. Working backwards we can reach the desired number.
A number with position
a) $3m$ goes to position $2m$ after erasing
b) $3m+2$ goes to position $2m+1$
Talking about the last number
it can get to position $1$ only if it comes from position $2$
it can get to position $2$ only if it comes from position $3$
it can get to position $3$ only if it comes from position $5$
it can get to position $5$ only if it comes from position $8$
it can get to position $8$ only if it comes from position $12$
it can get to position $12$ only if it comes from position $18$
it can get to position $18$ only if it comes from position $27$
it can get to position $27$ only if it comes from position $41$
it can get to position $41$ only if it comes from position $62$
it can get to position $62$ only if it comes from position $93$
it can get to position $128$ only if it comes from position $192$
it can get to position $192$ only if it comes from position $288$
it can get to position $288$ only if it comes from position $432$
it can get to position $432$ only if it comes from position $648$
it can get to position $648$ only if it comes from position $972$
it can get to position $972$ only if it comes from position $1458$
Since $1.5\times 1458\ge 2003$, $1458$ is the number we were looking for.