Sign in to follow this  
Followers 0
erlang

P3 IMC 2017

2 posts in this topic

Untuk semua bilangan asli $m$, definisikan $P(m)$ sebagai hasil kali semua faktor positif $m$ (e.g. $P(6)=36$). Untuk semua bilangan asli $n$ definisikan barisan $a_1(n)=n$, $a_{k+1}(n)=P(a_k(n))$ untuk $k=1,2,...,2016$. Tentukan apakah untuk semua himpunan $S\subseteq \{1,2,...,2017\}$, terdapat bilangan bulat positif $n$ sehingga kondisi berikut terpenuhi: Untuk setiap $k$ dengan $1\le k\le 2017$, $a_k(n)$ adalah bilangan kuadrat sempurna jika dan hanya jika $k\in S$.

0

Share this post


Link to post
Share on other sites
Spoiler

Ide utamanya sih bikin klaim ambisius kalau $p^a$ itu cukup. Saya pakai banyak waktu explore "nambahin prime" tapi kontrolnya susah gitu jadi gabisa induksi.

 

$p$ prima.

 

Lemma 1:

Untuk setiap $b$ bulat dan $k$ asli, terdapat solusi $a$ asli genap (dan ganjil) sehingga $\frac{a(a+1)}{2}\equiv b \ (mod\ 2^k)$

Bukti:-1

Induksi di $k$. Misalkan benar untuk $k=n$. Berarti untuk setiap $b$ terdapat $a$ sehingga $\frac{a(a+1)}{2}\equiv b \ (mod\ 2^{k+1})$ atau $\frac{a(a+1)}{2}\equiv b+2^k \ (mod\ 2^{k+1})$

Jika $\frac{a(a+1)}{2}\equiv b+2^k \ (mod\ 2^{k+1})$, perhatikan kalau $\frac{a'(a'+1)}{2}-\frac{a(a+1)}{2}=\frac{(a'-a)(a+a'+1)}{2}$ berarti kalau kita pilih $a'$ sehinnga $V_2(a'-a)=2^{k+1}$ diperoleh $\frac{a'(a'+1)}{2}\equiv b \ (mod\ 2^{k+1})$.

 

Lalu jika $a$ solusi, perhatikan kalau $c$ sehingga $2^{k+2}|a+c+1$ juga solusi (dengan cek selisih seperti diatas) dan $a,c$ beda paritas. Maka lemma terbukti.

 

 

Lemma 2:

$P(p^\alpha)=p^{\frac{\alpha(\alpha+1)}{2}}$

Bukti: Itung aja 

 

Sekarang akan dibuktikan kalau klaim di soal benar dan kita hanya butuh $n=p^\alpha$ untuk suatu $\alpha$ asli dengan induksi di $|S|$. (Jadi jika $|S|=n$ kita pasang $S=\{1,...,n\}$)

 

Jelas untuk $n=1$ benar. Misalkan benar untuk $n=m$. Lihat set $|S|=m+1$, Misalkan $H=(S\setminus \{1\})-1$ dimana $T-1$ adalah himpunan dimana semua anggota $T$ dikurang 1.

Perhatikan kalau untuk $H$ dari induksi kita tau bahwa ada $p^\alpha$ yang memenuhi. Jadi $a_i(p^\alpha)$ memenuhi kondisi soal untuk $H$.

 

Pilih $t$ sehingga $2^t>a_{|H|}(p^\alpha)$. Menurut lemma 1,2 kita bisa pilih $a$ (ganjil atau genap, tergantung $1\in S$ atau tidak) sehingga $P(p^a)=p^{j.2^t+\alpha}$. Dengan ineq di eksponen bisa di cek kalau paritas $v_p(a_{l+1}(p^a))$ sama dengan paritas $v_p(a_l(p^\alpha))$. Maka untuk semua $S$ kita punya $p^a$ yang memenuhi kondisi soal. Induksi selesai

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0