Jump to content
Sign in to follow this  
Adri

International Zhautykov Olympiad 2016, Hari Pertama: No 2

Recommended Posts

Bilangan $a_1, a_2, \cdots, a_{100}$ adalah permutasi dari bilangan $1,2, \cdots, 100$. Misalkan $S_1= a_1$, $S_2=  a_1 +a_2$,  $\cdots$ , $S_{100}= a_1 + \cdots + a_{100}$. Berapakah banyak maksimum bilangan kuadrat sempurna yang berada pada barisan $S_1, S_2, \cdots, S_{100}$ ? 

Share this post


Link to post
Share on other sites

kurang lebih

Spoiler

Ada 71 bilangan kuadrat diantara 1 sampai 5050.

Kita lihat paritas. Misalkan bilangan kuadrat yang kita peroleh $b_1,b_2,...$

kalau kita ambil sehingga $b_i$ dan $b_{i+1}$ paritas sama, maka ada setidaknya satu yang keeleminasi (ada bil kuadrat yang diantara $b_i$ dan $b_{i+1}$ karena paritas mereka sama)

kita bisa nyebrang paritas $50$ kali saja karena hanya ada $50$ bilangan ganjil. 

Berarti kita bisa bikin sehingga ambil berurutan hanya 50 kali (dimulai dari $S_0=0$)

berarti $1*urut+(bil. lebih dari samadengan 2)*loncat \le 71$. urut+loncat maks 50+10. 

konstruksinya $1,3,5,7,9,...,99$ lalu 2 kali masing-masing suku berikut $50,49,3,48,47,11,46,45,19,44,43,27,42,41,35,40,39,21,22,38,37,25,26,36,34,29,31,33,32,30,28,5,6,24,23,20,18,17,16,15,4,1$ sisanya terserah. Ini ada 60 bil kuadrat.

 

Share this post


Link to post
Share on other sites
On 1/15/2016 at 5:45 PM, sayakalah said:

kurang lebih

  Hide contents

Ada 71 bilangan kuadrat diantara 1 sampai 5050.

Kita lihat paritas. Misalkan bilangan kuadrat yang kita peroleh b1,b2,...

kalau kita ambil sehingga bi dan bi+1 paritas sama, maka ada setidaknya satu yang keeleminasi (ada bil kuadrat yang diantara bi dan bi+1 karena paritas mereka sama)

kita bisa nyebrang paritas 50 kali saja karena hanya ada 50 bilangan ganjil. 

Berarti kita bisa bikin sehingga ambil berurutan hanya 50 kali (dimulai dari S0=0 )

berarti 1urut+(bil.lebihdarisamadengan2)loncat71 . urut+loncat maks 50+10. 

konstruksinya 1,3,5,7,9,...,99 lalu 2 kali masing-masing suku berikut 50,49,3,48,47,11,46,45,19,44,43,27,42,41,35,40,39,21,22,38,37,25,26,36,34,29,31,33,32,30,28,5,6,24,23,20,18,17,16,15,4,1 sisanya terserah. Ini ada 60 bil kuadrat.

 

kurang lebih solusi kayak gini yang bikin nilainya kepotong banyak

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  

×