$n$ symbols line up in a row, numbered as $1,2,...,n$ from left to right. Delete every symbol with squared numbers. Renumber the rest from left to right. Repeat the process until all $n$ symbols are deleted. Let $f(n)$ be the initial number of the last symbol deleted. Find $f(n)$ in terms of $n$ and find $f(2019)$.
Problem
Source: CSMO 2019 Grade 11 Problem 3
Tags: combinatorics
30.07.2019 09:28
1+2*(1+2+3+...+44)=1981
30.07.2019 11:22
How did you get it?Could you please show us more clearly?
30.07.2019 11:24
FUSK wrote: How did you get it?Could you please show us more clearly? Consider the 'first' number deleted in each process. In fact f(n) should be one first deleted number in some process. Then every first number in each process should be: 1, 2, 3, 5, 7, ... The diff should be: 1, 1, 2, 2, 3, 3, ...
30.07.2019 11:39
yamamaya wrote: FUSK wrote: How did you get it?Could you please show us more clearly? Consider the 'first' number deleted in each process. In fact f(n) should be one first deleted number in some process. Then every first number in each process should be: 1, 2, 3, 5, 7, ... The diff should be: 1, 1, 2, 2, 3, 3, ... Could you please give a rigorous proof?
31.07.2019 15:03
yamamaya wrote: FUSK wrote: How did you get it?Could you please show us more clearly? Consider the 'first' number deleted in each process. In fact f(n) should be one first deleted number in some process. Then every first number in each process should be: 1, 2, 3, 5, 7, ... The diff should be: 1, 1, 2, 2, 3, 3, ... can you give a complete solution?
10.07.2020 22:13
Define $a_n$ as the greatest square less than $n$ and let $b_n = n - a_n^2$. \[ f(n) = \begin{cases} a_n^2 +1 &\text{if $b_n \leq a_n$} \\ a_n^2 + a_n + 1 &\text{if $a_n< b_n \leq 2a_n + 1$.} \end{cases} \]The proof proceeds by strong induction on $n$. The base case $n=1$ is checked by hand. Now we move on to the inductive step. If $n$ is a perfect square, then it is clear that $f(n) = f(n-1)$ and the conclusion is obvious. Suppose, then, that $n$ is not a perfect square. In the first instance, there are $a_n$ terms removed. Enumerate the remaining terms in increasing order as $x_1, x_2, \dots, x_{n-a_n}$. Then \[ f(n) = x_{f(n-a_n)} . \]If $b_n \leq a_n$, then $a_{n-a_n} = a_n -1$. It's a simple calculation to check that $b_{n-a} > a_n$, so $$f(n-a_n) = a_{n-1}^2 + a_{n-1} + 1 = a_n^2 - a_n +1$$by hypothesis. Since this is more than $a_n^2 - a_n$, it follows that \[ f(n) = x_{f(n-a_n)} = f(n - a_n) + a_n = (a_n^2 - a_n + 1) + a_n = a_n^2 + 1. \] If $b_n > a_n$, the logic is identical, except that $a_{n - a_n} = a_n$. This implies that $f(n-a_n) = a_n^2 + 1$. Thus the final step of our calculation turns to \[ f(n) = (a_n^2 + 1) +a_n , \]as desired. Substituting $n = 2019$ gives $a_n = 44$ and $b_n = 83 > 44$, so \[ f(2019) = 44^2 + 44 + 11 = 1981. \]
27.10.2022 06:10
It's not difficult to could discover that \[f(n) = \begin{cases} k^2-k+1 &\text{if $k^2-k+1 \leq n \leq k^2, k \ge 1$} \\ k^2+1 &\text{if $k^2+1 \leq n \leq k^2+k, k\ge 1$} \end{cases}\]It's easy to prove by induction.