Olympiade de maths: Opérations sur un ensemble d'entiers

On écrit sur un tableau les nombres 1, 2, . . . , n.
On fait l’opération suivante :

• on choisit deux nombres du tableau, on les efface et on écrit sur le tableau leur différence (le plus grand moins le plus petit).
  
• On répète cette opération jusqu’à ce qu’il reste un seulnombre sur le tableau. On se demande si ce nombre peut être 2.
  

(a) Démontrer que c’est possible si n = 8.
(b) Démontrer que c’est impossible si n = 9.
(c) Que peut-on dire si n = 100 ? Et si n = 2006 ?


Essayer de résoudre ce problème.

par exemple, si j'ai dans mon tableau 1,2,3,4,5,6
si je choisis les deux nombres 2 et 5 ==> différence=3
où mettre 3? à la place de 2 et 5?

mosa a écrit:par exemple, si j'ai dans mon tableau 1,2,3,4,5,6
si je choisis les deux nombres 2 et 5 ==> différence=3
où mettre 3? à la place de 2 et 5?

oui, exactement!

J'ai fait le programme suivant et il indique qu'il est possible d'obtenir 2 lorsque n = 9 :

Code:

program olympiade00;

const NMAX = 20;

type tab = array [1..NMAX] of integer;

procedure remplir_tab(n : integer; var t : tab);
var i : integer;
begin
    for i:=1 to n do begin
        t[i] := i;
    end;
end;

function fin_traitement(n : integer ; var t : tab):boolean;
var i : integer;
    v : boolean;
begin
    v := True;
    i := 1;
    while (v) and (i < n) do begin
        v := (t[i+1] = t[i]);
        i := i + 1;
    end;
    fin_traitement := v;
end;

procedure traitement(n : integer ; var t : tab);
var i, a, b : integer;
begin
    repeat
        a := random(n) + 1;
        b := random(n) + 1;
        // Writeln(a, ', ', b);
        t[a] := abs(t[a] - t[b]);
        t[b] := t[a];
    until (fin_traitement(n, t));
end;



var n : integer;
    t : tab;
begin
    randomize;
    repeat
        Writeln('Entrer n <=', NMAX, ' : ');
        Readln(n);
    until (n <= NMAX) and (n > 0);
   
    repeat
        remplir_tab(n, t);
        traitement(n, t);
        Writeln(t[1]);;
    until (t[1] = 2);
   
    Readln;
end.

Je suppose que je n'ai pas compris l'énoncé.

Merci manianis. Le code source est très lisible et très bien rédigé. Mais le seul problème qu'avec des programmes informatiques, on ne peut pas affirmer que le problème n'a pas de solutions lorsque n=9.

Donc il faut un raisonnement mathématique pur, et surtout que dans la question 3), il est demandée de vérifier l'existence d'une solution dans une instance de taille 100 et 2006. Ce qui n'est pas du tout faisable numériquement (on peut même considérer des instances de tailles 999999999)

Ton programme me donne des idées sur la résolution récursive du problème (recherche exhaustive de toutes les possibilités)!