[Proposed] Un exercice de la Shorttlist C1.



  • 0_1480685995519_upload-408860ab-a8cf-464e-8118-a48189dd7367



  • Essayez de chercher un invariant qui ne change pas pendant tout le processus.



  • Considerons les entiers suivants à l'étape 1 (a1,a2,a3,.....................,an)(a_1,a_2,a_3,.....................,a_n)
    Remarquons que max(ai)max(a_i) ne change pas .
    L'idée serait donc de trouver une suite croissante strictement durant cette itération et qui est bornée par le maximum.
    Considérons la suite Sn=a1+a2+.......+an S_n=a_1+a_2+.......+a_n
    On a Sn+1Sn=x1yS_{n+1}-S_n=x-1-y ou =1=1 Mais x1yx-1-y est plus grand que 0 mais pas strictement donc notre suite n est pas croissante strictement.....
    Mais la on remarque que l on n a pas utilisé la condition que xx est a drroite de y y
    Considérons cette fois ci la suite Sn=a1+2a2+3a3+.........+nanS_n = a_1+2a_2+3a_3+.........+na_n
    Et soit ii la position de yy
    Alors Sn+1Sn=i+1S_{n+1}-S_n= i+1 >00 ou bien Sn+1Sn=(i+1)(x1y)+i(xy)S_{n+1}-S_n=(i+1)(x-1-y)+i(x-y)>00
    Donc SnS_n est une suite crroissante strictement
    Hors Snn(n+1)max(ai)2 S_n \leq \frac{n(n+1)max(a_i)}{2} DoncSn S_n est bornée et strictement croissante dans NN.
    Donc Alice peut faire seulement un nombre fini d'itérations.
    CQFDCQFD
    Un tres bel exercice qui utilise non pas le fait qu il n existe pas une suite infinie décroissante strictement dans N mais qu il n existe pas une suite infinie croissante strictement dans NN et bornée


Log in to reply
 

Looks like your connection to Expii Forum was lost, please wait while we try to reconnect.