Азиатско-Тихоокеанская математическая олимпиада, 2003 год

Пусть $k \geq 14$ является натуральным числом и $p_k$ является наибольшим простым числом, которое в точности меньше $k$. Вы можете положить, что $p_k \geq \frac{3k}{4}$. Пусть $n$ является составным числом. Докажите, что
(а) если $n = 2pk$, то $(n-k)!$ не делится на $n$;
(б) если $n > 2pk$, то $(n-k)!$ делится на $n$.

Комментарий/решение

$(a)$

$n-k=2p_k-k<p_k \rightarrow p_k \nmid (n-k)!$

$(b)$

$(i)n=a^2$

$a \notin P$

$a=q^pp_1^{\alpha_1} \dots p_i^{\alpha_i}$

$q^p>p_1^{\alpha_1}, \dots, p_i^{\alpha_i}$

$a^2-k\geq 2q^p$

$a^2-k>\frac{k}{2}$

Если $\frac{k}{2} \geq 2q^p$ то утверждение верно значит:

$\frac{k}{2} < 2q^p$

$2q^p=\frac{k}{2}+x$

$a\geq 2q^p$

$a^2 \geq \frac{k^2}{4}+{kx}+x^2$

$\frac{k^2}{4}+{kx}+x^2-k \geq \frac{k}{2}+x$

При:

$x\geq 1$

$x^2 \geq x$

$kx\geq \frac{k}{2}$

$\frac{k^2}{4} \geq k$

$x=\frac{1}{4},\frac{1}{2},\frac{3}{4}$

Подставив получим три случая:

$\frac{k^2}{4}+\frac{k}{4}+\frac{1}{16} \geq \frac{3k}{2}+\frac{1}{4} \rightarrow k^2-5k-1+\frac{1}{4} \geq 0$

$\frac{k^2}{4}+\frac{k}{2}+\frac{1}{4} \geq \frac{3k}{2}+\frac{1}{2} \rightarrow k^2-4k-1\geq 0$

$\frac{k^2}{4}+\frac{3k}{4}+\frac{9}{16} \geq \frac{3k}{2}+\frac{3}{4} \rightarrow k^2-3k-\frac{3}{4} \geq 0$

Что верно

$a \in P$

$a=q$

$q^2-k\geq 2q$

Пойдем от обратного

$q^2-k+1\leq 2q$

$2q \geq \frac{3k}{2}+2-k=\frac{k}{2}+2 \rightarrow q \geq \frac{k}{4}+1$

$k\geq q^2-2q+1=(q-1)^2\geq \frac{k^2}{16} \rightarrow k\leq16$

$q \leq 5, q^2\leq 25$

$p_k\geq 13$

$n>26 \rightarrow \varnothing$

$(ii)ab=n$

$a,b \ne 1$

Б.О.О. $a>b$

$ab-k\geq a$

$a(b-1)\geq k$

$a(b-1)>\frac{3k(b-1)}{2b} \rightarrow \frac{3k}{2}-\frac{3k}{2b}$

При:

$b\geq 3 \rightarrow \frac{3k}{2}-\frac{3k}{2b}\geq k$

$b=2$

$a \in P \rightarrow a>p_k \rightarrow a\geq k \rightarrow 2a-k\geq a$

$a \notin P$

$2a-k \geq a$

$\frac{3k}{4}<a<k$

$a=k-l$

$2a-k=k-2l$

Если степень каждого простого делителя $a$ меньше $2$ то:

Наибольший возможный простой делитель:

$\frac{k-l}{2}$

$2k-4l>k-l \rightarrow k>3l$

Что верно

Значит число $(n-k)!$ будет содержать все простые делители $n$

Значит степень хотя бы одного из делителей превышает $2$

$^p\sqrt{k-l}\geq q$

$q^p \mid a, q^{p+1} \nmid a$

Допустим:

$p\times {^p\sqrt{k-l}} \geq k-2l$

$p^p(k-l)\geq (k-2l)^p$

$k-l\geq (\frac{k-2l}{p})^p$

$p\leq\sqrt{k-l},n\geq 32$

$a^2\leq2^a \rightarrow a\geq 4$

$k-l \geq (\frac{k-2l}{p})^p > (\sqrt{k-l}-\frac{l}{\sqrt{k-l}})^p>(\sqrt{k-l}-1)^p$

$p=2$

$k-l=x$

$l<\frac{k-l}{3} \rightarrow 4x\geq (x-l)^2 > (\frac{2x}{3})^2 \rightarrow \varnothing$

Т.к. $\frac{x}{9}> 1 \rightarrow \frac{4x^2}{9} > 4x$

Поскольку:

$c^px=a,x\geq 1 \rightarrow c\leq ^p\sqrt{a} \rightarrow cp<k-2l$

$(c$ - любой простой делитель числа $a,$ $p$ его степень$)$

Для $n=28,30$

$k=14,15,16$

Во всех случаях $(n-k)!$ будет содержать числа:

$4,5,6,7$

Ч.Т.Д.