Rješenja zadatka "IMO Shortlist 2001 problem C1" korisnika "lkkraljevic"

Točno

13. ožujka 2018. 22:02 (7 godine, 8 mjeseci)

Korisnik: lkkraljevic
Zadatak: IMO Shortlist 2001 problem C1 (Sakrij tekst zadatka)

Let $A = (a_1, a_2, \ldots, a_{2001})$ be a sequence of positive integers. Let $m$ be the number of 3-element subsequences $(a_i,a_j,a_k)$ with $1 \leq i < j < k \leq 2001$ , such that $a_j = a_i + 1$ and $a_k = a_j + 1$ . Considering all such sequences $A$ , find the greatest value of $m$ .

Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.

Prvo izaberemo prvih $667$ članova kao $a$ sljedećih toliko sa $a+1$ i zadnjih $667$ sa $a+2$ , ovom konstrukcijom uviđamo da je $m \geq 667^3$
Uočimo da su u tročlanom podskupu svi elementi različiti modulo $3$ to nas motivira da posmatramo neki skup $A$ sa $x$ brojeva kongruentni $0$ modulo $3$ , $y$ brojeva kongruentni $1$ modulo $3$ i $z$ brojeva kongruentno $2$ . Uočimo da vrijedi slijedeća tvrdnja
$-\enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace \enspace\enspace \enspace \enspace \enspace m \leq \#($ podskupova $(x,y,z)$ gdje su $x,y,z$ u parovima različti $mod \enspace 3 \enspace) \leq xyz \leq (\frac{x+y+z}{3})^3\leq 667^3$
Kombiniranjem konstrukcije i gornje ograde na $m$ zaključujemo da $m=667^3$

Školjka

Ocjene: (1)