There is number $N$ on the board. Every minute Ivan makes next operation: takes any number $a$ written on the board, erases it, then writes all divisors of $a$ except $a$( Can be same numbers on the board). After some time on the board there are $N^2$ numbers. For which $N$ is it possible?
Problem
Source: All Russian Olympiad 2017,Day2,grade 11,P7
Tags: number theory, algebra
rafayaashary1
02.05.2017 01:34
Interesting... I think the bound is by size. Let $f(n)$ be the maximum amount of numbers we can have written on the board at a given time. Assume by strong induction that $f(n)\leq n^2$ (prime case trivial). Then $$f(n)=\text{max}\left(\sum_{d\mid n,\ d<n} f(d),\ 1\right)\leq_{n\neq 1} \sum_{d\mid n,\ d<n}d^2\iff \frac{f(n)}{n^2}\leq-1+ \sum_{d\mid n}\frac{1}{d^2}\leq \frac{\pi^2}{6}-1<1$$So $\boxed{n=1}$ is the only solution.
laegolas
02.05.2017 02:54
Harder problem: Letting $N={p_1}^{k_1}{p_2}^{k_2}{p_3}^{k_3}\cdots {p_n}^{k_n}$, find the function $f(N)$ in terms of $k_1,k_2,k_3,\dots k_n$ that gives the maximum amount of numbers that can be written on the board.
Bashwork$$f({p_1}^{k_1})=2^{k_1-1}$$$$f({p_1}^{k_1}p_2)=2^{k_1-1}\cdot (k_1+2)$$$$f({p_1}^{k_1}{p_2}^2)=2^{k_1-1}\cdot \left(\binom{k_1+4}{2}-2\right)$$$$f({p_1}^{k_1}{p_2}^3)=2^{k_1-1}\cdot \left(\binom{k_1+6}{3}-3(k_1+4)\right)$$$$f({p_1}^{k_1}{p_2}^4)=2^{k_1-1}\cdot \left(\binom{k_1+8}{4}-4\binom{k_1+6}{2}+6\right)$$
Conjecture (fairly confident):
$$f({p_1}^{k_1}{p_2}^{k_2})=2^{k_1-1}\cdot \left( \sum_{i=0}^{\lfloor k_2\rfloor} (-1)^i\binom{k_2}{i}\binom{k_1+2k_2-2i}
{k_2-2i}\right)$$ewww maybe this isn't going to be very nice
rafayaashary1
02.05.2017 04:37
In case anyone needs to compute laegolas's function for specific integers: def board(n): if n == 1: return 1 else: ans=0 for num in range(1,n): if n%num==0: ans+=board(num) return ans N=int(input('Enter N: '))print(board(N))def board(n): if n == 1: return 1 else: ans=0 for num in range(1,n): if n%num==0: ans+=board(num) return ans N=int(input('Enter N: ')) print(board(N))RunResetPop Out /
Ruy
16.12.2021 06:04
rafayaashary1 wrote: Interesting... I think the bound is by size. Let $f(n)$ be the maximum amount of numbers we can have written on the board at a given time. Assume by strong induction that $f(n)\leq n^2$ (prime case trivial). Then $$f(n)=\text{max}\left(\sum_{d\mid n,\ d<n} f(d),\ 1\right)\leq_{n\neq 1} \sum_{d\mid n,\ d<n}d^2\iff \frac{f(n)}{n^2}\leq-1+ \sum_{d\mid n}\frac{1}{d^2}\leq \frac{\pi^2}{6}-1<1$$So $\boxed{n=1}$ is the only solution. $N=1$ does not display an empty board after a singular movement?
Ruy
16.12.2021 06:13
I claim that there is a function $\Gamma : \mathbb{N}^* \to \mathbb{N}^*$ such that for some other function $\gamma : \mathbb{N}^* \to \mathbb{N}^*$ the maximum quantity of numbers on a board after an optimal time, starting with $N$ written, is $$\Gamma (N)=\sum_{j\in J}\gamma (j)\ |\ J=\{j;\ \forall \ q\ |\ j,\ v_{q}j=v_q{N}\}.$$That is actually a really strong conjecture as I proved this with strong induction haha. You also should notice that $\gamma(n)$ is $2^{k-1}$ where $k$ is the sum of exponents in prime factorization of $n$.