Forum INFOMATH
Vous souhaitez réagir à ce message ? Créez un compte en quelques clics ou connectez-vous pour continuer.
Le deal à ne pas rater :
SSD interne Crucial BX500 2,5″ SATA – 500 Go à 29,99€
29.99 €
Voir le deal

2 petites énigmes

3 participants

Aller en bas

2 petites énigmes Empty 2 petites énigmes

Message par Invité Jeu 22 Nov - 18:25

Démontrez que la somme de 8 nombres dont le plus grand est 5 peut s'écrire
comme la somme de 5 nombres dont le plus grand est 8 scratch



Dessiner
10 triangles avec 5 traits scratch

Renverser le triangle équilatéral
de bas en haut en trois mouvements de pièces

[Vous devez être inscrit et connecté pour voir cette image]

Invité
Invité


Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par methodiX Mar 27 Nov - 0:39

azerty a écrit:Démontrez que la somme de 8 nombres dont le plus grand est 5 peut s'écrire
comme la somme de 5 nombres dont le plus grand est 8 scratch

1er PROBLEME

je crois que c'est évident du moment où on a l'inégalité suivante:

Soit xi, i=1..8, les 8 nombres dont le plus grand est 5.
Donc la somme des xi est inférieure ou égal à 5x8=40.

Soit yi, i=1..5, les 5 nombres dont le plus grand est 8.
Donc la somme des yi est inférieure ou égal à 8x5=40.

les deux sommes sont inférieures à 40.
Ce qui veut dire qu'en choisissant 8 xi <= 5, on pourra construire 5 yi <= 8 qui ont la même somme que celle des xi.

Exemple:
xi = {4, 5, 5, 3, 3, 2, 1, 1} => Total = X = 24

On doit chercher 5 yi <= 8 tels que leur somme soit égale à 24.
C'est simple:
yi = {5, 5, 5, 5, 4}

Il y a plusieurs façons de le faire Wink
methodiX
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7254
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
2 petites énigmes Left_bar_bleue1000/10002 petites énigmes Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par Napoléon Mar 27 Nov - 1:01

Ton raisonnement est logique.
Reste à démontrer que la construction de la somme des xi par des yi vérifiant "yi <= 8" est toujours possible!

Il y a une solution explicite, la voilà:
Si on note X = la somme des xi. On note R = X div 8.
Il suffit de choisir les yi comme suit:

yi = 8, pour tout i de 1 à R.

les yi restants (s'ils existent) les remplir comme suit:
a. le premier yi = X mod 8
b. les autres yi = 0.

Code:
Application:
Soit xi = {5, 5, 4, 3, 3, 2, 2, 2, 1}
donc X = 27.
donc R = 27 div 8 = 3.

les yi sont:

y1 = 8
y2 = 8
y3 = 8

y4 = 27 mod 8 = 3
y5 = 0

soit yi = {8, 8, 8, 3, 0}
Napoléon
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7872
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
2 petites énigmes Left_bar_bleue999/10002 petites énigmes Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par manianis Mar 27 Nov - 13:51

La réponse est assez simple :
5 * 8 = 8 * 5

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 6255
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
2 petites énigmes Left_bar_bleue999/10002 petites énigmes Empty_bar_bleue  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par Napoléon Mar 27 Nov - 14:14

manianis a écrit:La réponse est assez simple :
5 * 8 = 8 * 5

oui manianis, ça c'est simple.
Mais il faut montrer qu'on peut toujours construire les 5 nombres.
Napoléon
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7872
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
2 petites énigmes Left_bar_bleue999/10002 petites énigmes Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par Invité Mar 27 Nov - 16:44

alors vous oubliez les deux autres énigmes tongue

la première est trop facile elle est démontrée même graphiquement en dessinant des traits, mais il vous reste deux autres énigmes qui sont 10 fois plus
Difficiles lol!


Invité
Invité


Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par manianis Mer 28 Nov - 10:45

Admin a écrit:
manianis a écrit:La réponse est assez simple :
5 * 8 = 8 * 5

oui manianis, ça c'est simple.
Mais il faut montrer qu'on peut toujours construire les 5 nombres.

Je n'ai pas encore terminé :

Le nombre maximal qui découle de la somme de 8 entiers avec 5 est le plus grand est 40.
Le nombre maximal qui découle de la somme de 5 entiers avec 8est le plus grand est 40.

Le nombre minimal qui découle de la somme de 5 entiers est 5, le nombre minimal qui découle de la somme de 8 entiers est 8.

La résolution de cet exercice consistera à chercher une renrésentation des nombres n. (avec 8 <= n <= 40 sous la somme de 8 entiers et la somme de 5 entiers)
8 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
8 = 4 + 1 + 1 + 1 + 1
--------------------------------
9 = 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1
9 = 5 + 1 + 1 + 1 + 1
--------------------------------
10 = 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1
10 = 5 + 2 + 1 + 1 + 1
Et ainsi de suite.

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 6255
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
2 petites énigmes Left_bar_bleue999/10002 petites énigmes Empty_bar_bleue  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par Napoléon Mer 28 Nov - 11:53

j'ai pas bien compris le principe Sad

Posons la question autrement:

Si on vous demande d'écrore un programme qui saisit 8 nombres inférieurs ou égaux à 5. On note S leur somme. On vous demande ensuite de trouver (et afficher) 5 nombres inférieurs ou égaux à 8 tels que leur somme est S.

Comment vous faites?
Napoléon
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7872
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
2 petites énigmes Left_bar_bleue999/10002 petites énigmes Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par Invité Mer 28 Nov - 12:42

nous avons un nouveau verbe dans la langue française le verbe ercrore du troisième groupe
il faut signaler l'académie française pour qu'elle l'officialise hah ha h ah ah ah ah lol!

Invité
Invité


Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par Invité Mer 28 Nov - 12:43

Admin a écrit:
Si on vous demande d'écrore un programme qui saisit 8 ...
Comment vous faites?
Wink

Invité
Invité


Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par Napoléon Mer 28 Nov - 14:04

azerty a écrit:nous avons un nouveau verbe dans la langue française le verbe ercrore du troisième groupe
il faut signaler l'académie française pour qu'elle l'officialise hah ha h ah ah ah ah lol!


lol!lol!lol!lol!lol!
Napoléon
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7872
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
2 petites énigmes Left_bar_bleue999/10002 petites énigmes Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par manianis Mer 28 Nov - 14:33

J'espère que ce programme fera l'affaire :

Code:
program sommation;
type tab = array [1..8] of integer;
var i : integer;
    p, n : tab;
    i1, i2 : integer;
   
procedure Affiche(n : integer ; t : tab);
var i, s : integer;
begin
    s := 0;
    for i:=1 to n do begin
        if (i > 1) then Write('+');
        Write(t[i]);
        s := s + t[i];
    end;
    Writeln('=', s);
end;

procedure incr_case(n : integer ; var t : tab ; var p : integer ; max : integer );
begin
    t[p] := t[p] + 1;
    while (p < n) and (t[p] > max) do begin
        t[p] := max;
        p := p + 1;
        t[p] := t[p] + 1;
    end;
end;

begin
    for i:=1 to 8 do begin
        p[i]:=1;
        if (i <= 5) then n[i]:=1;
    end;
    n[1]:=n[1]+3;
   
    i1 := 1; i2 := 1;
    for i:=8 to 40 do begin
        Writeln;
        Writeln('i = ', i);
        Affiche(8, p);
        Affiche(5, n);
       
        incr_case(8, p, i1, 5);
        incr_case(5, n, i2, 8);
    end;
   
    Readln;
end.

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 6255
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
2 petites énigmes Left_bar_bleue999/10002 petites énigmes Empty_bar_bleue  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par Napoléon Mer 28 Nov - 15:09

ça marche manianis!
vraiment Félicitations !

de ma part, je vais essayer de proposer une version plus courte Wink
Napoléon
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7872
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
2 petites énigmes Left_bar_bleue999/10002 petites énigmes Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par Napoléon Mer 28 Nov - 23:17

Voilà une solution systématique au problème (1):

Code:
program sommation;
uses wincrt;
const
  MAX_IN  = 8;
  MAX_OUT = 5;
VAR
  IN_  : array[1..MAX_IN] of integer;
  OUT_ : array[1..MAX_OUT] of integer;
  S, Q, R: integer;
  i,j: integer;

BEGIN
  {SAISIE DU TABLEAU ***************** }
  S := 0;
  for i:=1 to MAX_IN do
  begin
    repeat
      write('ENTREE N°',i,'/',MAX_IN,
            '(inférieur à ',MAX_OUT,') = ');
      readln(IN_[i]);
    until (IN_[i]<=MAX_OUT) and (IN_[i]>=0);
    S := S + IN_[i];
  end;
  { CONSTRUCTION DU TABLEAU **********}
  Q := S div MAX_IN;
  R := S mod MAX_IN;

  for i:=1 to Q do OUT_[i] := MAX_IN;
  if (i<MAX_OUT) then
  begin
    OUT_[i+1] := R;
    j := i+2;
    for i:=j to MAX_OUT do OUT_[i] := 0;
  end;
  { AFFICHAGE DU TABLEAU FINAL ******}
  writeln(' --> La somme est ',S);
  for i:=1 to MAX_OUT do
      writeln('SORTIE N°',i,'/',MAX_OUT,' = ',OUT_[i]);
END.

Des commentaires?
Napoléon
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7872
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
2 petites énigmes Left_bar_bleue999/10002 petites énigmes Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par manianis Jeu 29 Nov - 0:06

Ce programme est bien oganisé.

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 6255
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
2 petites énigmes Left_bar_bleue999/10002 petites énigmes Empty_bar_bleue  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par methodiX Jeu 29 Nov - 23:48

Je ne sais pas comparer la "complexité" des deux solutions proposées, mais je pense qu'elles sont bien rédigées toutes les deux.
methodiX
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7254
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
2 petites énigmes Left_bar_bleue1000/10002 petites énigmes Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par manianis Sam 1 Déc - 1:33

Je crois que Nabil doit nous donner quelques petites notes sur le calcul de Complexité. Moi, j'ai quelques notions trés vagues sur ce type de calcul car je ne m'en suis jamais servi.

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 6255
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
2 petites énigmes Left_bar_bleue999/10002 petites énigmes Empty_bar_bleue  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par Napoléon Sam 1 Déc - 1:37

D'accord, j'ai posté depuis quelques jours un Topic sur la complexité des algorithmes... tu l'as vu manianis?
Napoléon
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7872
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
2 petites énigmes Left_bar_bleue999/10002 petites énigmes Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par manianis Sam 1 Déc - 15:34

D'accord je vais le chercher... Merci.

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 6255
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
2 petites énigmes Left_bar_bleue999/10002 petites énigmes Empty_bar_bleue  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

2 petites énigmes Empty Re: 2 petites énigmes

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum