$k,n$ are two arbitrary positive integers. Prove that there exists at least $(k-1)(n-k+1)$ positive integers that can be produced by $n$ number of $k$'s and using only $+,-,\times, \div$ operations and adding parentheses between them, but cannot be produced using $n-1$ number of $k$'s. Proposed by Aryan Tajmir
Problem
Source: 2017 Iran TST second exam day2 p5
Tags: combinatorics, Iran, Iranian TST
24.04.2017 17:14
What is $ks$ ?
24.04.2017 20:10
Gems98 wrote: What is $ks$ ? It's the plural form of k
26.04.2017 13:27
Is it allowed to do something like: $$...k\cdot(-k)...$$or $$(k-k)...$$In begginning
27.04.2017 21:06
artsolver wrote: Is it allowed to do something like: $$...k\cdot(-k)...$$or $$(k-k)...$$In begginning Sure
12.09.2017 11:22
15.04.2020 13:17
Solution) For all $i, j$ which satisfies $n-1 \ge i \ge j$, $k^{n-2}+k^{i}+k^{j}$ can be produced by $n$ numbers of $k$s because of following. $$k^{n-2}+k^{i}+k^{j}=\underbrace{k \times k \times ... \times k}_{j-1}(\underbrace{k \times k \times ...\times k}_{i-j}(\underbrace{k \times k \times ... \times k}_{n-1-i}+k)+k)$$ For each $i,j$, if $k^{n-2}+k^{i}+k^{j}$ can’t be produced by $n-1$ number of $k$s, $k^{n-2}+k^{i}+k^{j}$ satisfies the conditions. If $k^{n-2}+k^{i}+k^{j}$ can be produced by $n-1$ number of $k$s, $k^{n-1}+k^{i+1}+k^{j+1}$ can be produced by $n$ number of $k$s. And, we can’t produce a number more than $k^{n-1}$ with $n-1$ numbers of $k$s. So, $k^{n-1}+k^{i+1}+k^{j+1}$ satisfies the condition. So, there exists at least $ {n-2} \choose {2} $ numbers which satisfies the condition.