Probleme OIM 2011 ziua 1

[muscapaul]

Problema 1.
Pentru orice mulµime formata din patru numere naturale nenule distincte
A = {a1, a2, a3, a4} notam cu S(A) suma a1 + a2 + a3 + a4. Fie N(A) numarul de perechi (i, j) cu
1$\le$ i <j $\le$4, pentru care ai + aj divide S(A). Determinati multimile A pentru care N(A) ia valoarea
maxima.
Problema 2.
Fie S o multime finita de puncte din plan ce contine cel puµin doua puncte, astfel
încât oricare trei puncte nu sunt coliniare. Prin moara de vânt definim urmatorul proces. Consideram
o dreapta l ce trece printr-un singur punct P din S. Dreapta l se roteste în sensul acelor de ceasornic
în jurul punctului pivot P pâna întâlneste pentru prima data un alt punct Q aparµinînd mulµimii
S. Punctul Q devine noul pivot în jurul caruia dreapta l continua sa se roteasca în sens orar, pâna
va întâlni din nou pentru prima data un punct din multimea S. Procesul continua indefinit, pivotul
fiind de fiecare data un punct din S.
Demonstrati ca exista un punct P din S si o dreapta initiala l ce contine P, astfel încât moara de
vânt sa treaca de o infinitate de ori prin fiecare punct din S.
Problema 3. Fie f : R -> R o functie cu proprietatea
f(x + y) $\le$ yf(x) + f(f(x))
pentru orice numere reale x si y. Demonstrati ca f(x) = 0 pentru orice numar x $\le$ 0.

[mihai miculita]

subiecte in format pdf in lb.romana

[andreiteodor]

Problema 1:


Presupunem $a_1<a_2<a_3<a_4$.
Nu putem avea $a3+a4|S_A$(deoarece am obtine $a_3+a_4|a_1+a_2$ , ceea ce este fals , deoarece $0<a_3+a_4<a_1+a_2$) si analog nici $a_2+a_4|S_A$ . Atunci cel mult 4 din toate cele 6 sume $a_i+a_j$ pot divide $S_A$ , deci $\,\;max n_A=4$.(aceasta valoare se obtine eventual pentru multimea $\{1;5;7;11\}$)
Cautam deci multimile $\{a_1;a_2;a_3;a_4\}$ pentru care $a_1+a_2|S_A;a_1+a_3|S_A;a_1+a_4|S_A$ si $a_2+a_3|S_A$. Avem :
$a_1+a_4|a_2+a_3$ si $a_2+a_3|a_1+a_4$ , deci $a_1+a_4=a_2+a_323\implies a2-a1=a4-a3=d , d \in \Bbb{N}$.
$a_2=d+a_1;a_4=a_3+d$.
Mai avem $a_1+a_3|a_2+a_4$ si $a_1+a_2|a_3+a_4$ , adica $2a_1+d|2a_3+d$ si $a_1+a_3|2d$. Notam $a_3-a_1=k , k>d$. Obtinem :
$2a_1+d|2k$ si $2a_1+k|2d$.
Fie m,n naturale nenule astfel incat $m(2a_1+d)=2k ; n(2a_1+k)=2d$ . Daca m;n>1 , avem :
$2k \ge 2(2a_1+d)$
$2d\ge 2(2a_1+k)$
Adunand relatiile , avem $8a_1 \le 0$, imposibil .
Distingem 2 cazuri :
i)m=1$\implies$2a1+d=2k$\implies$k=$\frac{2a1+d}{2}$
Deducem ca 6a1+d|4d , deci 6a1+d$\le$4d , adica 2a1$\le$d. Dar k>d , de unde , inlocuind, 2a1>d , contradictie .
ii)n=1$\implies$2a1+k=2d , deci k=2d-2a1
Inlocuind , ontinem 2a1+d|4d-4a1, de unde 2a1+d|6d . Fie u naural nenul astfel incat :
u(2a1+d)=6d .
Avem ud<6d , deci u<6 . Daca u=1 , obtinem 2a1+d=3d , adica d=a1 si k=0 , imposibil. Daca u=2 , obtinem 4a1+2d+3d , deci d=4a1 si k=6a1. Daca u=3 , obtinem 6a1+3d=6d , deci d=2a1 si k=2a1 , contradictie. Daca u=4 , obtinem 8a1+4d=6d si iarasi obtinem o contradictie. Daca u=5 , obtinem 10a1+5d=6d, de unde d=10a1 si k=18.
Deci multimile cerute sunt de forma {a;5a;7a;11a} si {a;11a;19a;29a} , cu a natural nenul.

[Moldovan Bogdan]

Mai sunt multimile de forma {$k,11k,19k,29k$} cu k natural oarecare
La problema 2.raspuns(nu demonstratie):
avem 2 cazuri :
1.punctele multimii S formeaza un poligon convex; atunci orice varf al poligonului poate fi luat ca start al morii de vant( pt. o intelegere mai usoara cosiderati ca punctele formeaza un poligon regulat)
2.punctele multimii S nu formeaza un poligon convex ; atunci le consideram ca si varfuri ale unor poligoane convexe interioare unul altuia, astfel ultimele puncte "din interior" care pot forma un triunghi sau segment sau poate fi unul singur sunt bune pentru startul morii de vant

[Laurențiu Ploscaru]

Sau:
Am ajuns la $m(2a_1+d)=2k$ și $n(2a_1+k)=2d$ și că unul dintre $m$ și $n$ este $1$ ca mai sus.
Dar $\left\{\begin{array}{l} m(2a_1+d)=2k \\ n(2a_1+k)=2d \end{array}\right.$
Cum $k>d$ ne iese imediat că $m>n$. Astfel $n=1$. Deci $2a_1+k=2d$.
Înlocuind $2d$ în $4ma_1+2dm=4k$ obținem $6ma_1=k(4-m)$.
Cum $6ma_1>0$, avem $4>m$, dar $m>n$, adică $m>1$. Deci $m\in \{2,3\}$.
Pentru $m=2$ avem $k=6a_1$ și deci $d=4a_1$ (am înlocuit în $2a_1+k=2d$). Obținem soluția $\{a,5a,7a,11a\}$.
Pentru $m=3$ avem $k=18a_1$ și deci $d=10a_1$ (am înlocuit în $2a_1+k=2d$). Obținem soluția $\{a,11a,19a,29a\}$.

[Stefan Spataru]

Pentru problema 3(schitarea pasilor)

Demonstram$f(x) \leq 0$ pentru orice x. Pentru aceasta observam ca $f(x) \leq xf(0) +f(f(0))$, $f(x) \leq f(f(x))$ si $f^2(x) \geq xf(x)$,pentru orice x. Mai departe, consideram toate cele cazuri determinate de ordinea dintre $f(0) si 0$.

Pentru finalizare, avem 2 cazuri : exista un $c$ pentru care$f(c)=0$, obtinand $f(0)=0$, si de aici este usor.

Pentru cel de-al doilea caz, utilizam $f^2(x) \geq xf(x)$, si cum nu exista $f(c)=0$ atunci $f(x) \leq x$,si deci $f(f(x)) \leq f(x)$. Dar la inceput am obtinut aceasta inegalitate invers. Obtinem $f(f(x))=f(x)$ pentru orice $x$. Inlocuind, obtinem $f(x+y) \ge (y+1) f(x+y)$ pentru orice $x,y$. adica $y \ge 0$ pentru orice y real, evident fals, deci acest caz nu se poate atinge.

[Laurențiu Ploscaru]

Problema 2:
Fie $n$ numărul de puncte din $S$. Dăm o direcţie dreptei $l$ pentru a putea avea noţiunile stânga şi dreapta. Acum vom considera că dreapta $l$ se află în stânga ei.
Să observăm că numărul de puncte din stânga dreptei este constant. (dacă dreapta se roteşte în jurul lui $P$, când va întâlni $Q$, care nu era în stânga, $Q$ va trece în stânga şi va ieşi $P$)
Deci la fiecare morişcă vom avea $k$ puncte în stânga dreptei. Va trebui să găsim o valoare convenabilă a lui $k$.
Luăm o dreaptă oarecare $d$ care trece prin $P$ şi să presupunem că avem $s$ puncte în stânga ei. Rotim dreapta cu $180^\circ$ şi vom avea $n-s$ puncte în stânga.
Se observă că în timpul rotaţiei toate valorile dintre $s$ şi $n-s$ vor fi atinse. Deci $k\in [n,n-s]$. Dar $[\frac{n}{2}]$ verifică această condiţie. Deci $k=[\frac{n}{2}]$.
Evident există o dreaptă $g$ care trece prin $P$ şi care are $[\frac{n}{2}]$ puncte la stânga. Acum să demonstrăm că morişca trece prin toate punctele lui $S$ de o infinitate de ori.
Există o infinitate de momente în care $l\parallel g$, şi amândouă vor avea $k$ puncte în stânga, deci $l=d$ (se demonstrează prin reducere la absurd).
Repetând raţionamentul pentru toate punctele din $S$, obţinem concluzia.

[andreiteodor]

Solutia mea (problema 3):

Aratam ca $f(x)\le 0\,\; (*)$, oricare ar fi $x\in \Bbb{R}$. Luand $y=0\Rightarrow f(x)\le f(f(x))$. Inlocuind in relatia data $\Rightarrow f(x+y)\le yf(f(x))+f(f(x))$. Punem $y=-1\Rightarrow f(x-1)\le 0$, deci am demonstrat $(*)$.
Daca exista $a\in\Bbb{R}$, cu $f(a)=0\Rightarrow f(0)\ge 0$, deoarece $f(f(x))\ge f(x)$. Conform celor aratate anterior, $f(0)=0\Rightarrow -xf(x)+f(f(x))\ge 0$. Evident, pentru $x<0\Rightarrow f(x)=f(f(x))=0$ si am terminat.
Sa presupunem $f(x)<0$, oricare ar fi $x\in\Bbb{R}$. Punem in relatia data $y=f(x)-x\Rightarrow f(x)[f(x)-x]\ge 0\Rightarrow$$f(x)\le x\Rightarrow f(f(x))\le f(x)\Rightarrow f(f(x))=f(x)$. Fie $a\in \Bbb{R}$ oarecare. Luam $x=0;y=f(a)\Rightarrow f(a)\le \dfrac{f(0)}{1-f(0)}$. Folosind si relatia data $\Rightarrow f(x+y)\le \dfrac{f(0)}{1-f(0)}*(y+1)$. Fixand $x+y\Rightarrow y+1\le \dfrac{f(x+y)*(1-f(0))}{f(0)}$, evidnent absurd. Deci acest caz este imposibil si concluzia este indeplinita.