Égaliser les six nombres

13»

Réponses

  • Domi
    Modifié (July 2023)
    Somme ou produit, ça n'a pas d'importance, on opère sur des caractères formels. Je pensais que le problème était plus simple à appréhender sous sa forme additive et en fait j'ai embarqué tout le monde dans des calculs vectoriels qui n'auraient peut-être pas été proposés avec l'énoncé initial.
    Domi.
  • Oui, j'aurais pu réfléchir un peu ! Merci pour la réponse.
  • PetitLutinMalicieux
    Modifié (July 2023)
    Comme nous sommes dans le sous-forum "Combinatoire et graphes", nous pouvons nous permettre un petit dénombrement discret. Nous avons démontré que nous pouvions égaliser les cases d'une zone de 2n réels en une quantité finie d'opérations. Super. Combien ? Combien faut-il d'opérations élémentaires pour égaliser le champ complet ? J'appelle $(U_n)$ la suite numérique qui donne le nombre optimal de sommes élémentaires. La précaution consiste à parler de fonctions plutôt que du nombre d'étapes. Car, comme il existe plusieurs méthodes, on a vite fait de donner le même nom à des valeurs complètement différentes.
    • Le rejet
      $U_{2n+1},n\in \mathbb{N^*}$ est indéfini.
      Dans la suite nous calculerons $U_{2n},n\in \mathbb{N^*}$
    • Les puissances de 2
      On commence par un raccourci évident. Si la zone a une taille égale à une puissance de 2, on peut définir la fonction p telle que $p(2^k)=k2^{k-1}$. En effet, à chaque étape, toute case s'additionne avec une case de zone différente, mais de même taille.
      $U_{2n}=k2^{k-1},si\ 2n=2^k, k\in \mathbb{N^*}$
    • Le doublement
      Plus généralement, si 2 zones de même taille "m" ont déjà été égalisées, il peut être préférable d'associer chaque case de la première zone avec une case de la seconde zone, plutôt que d'avancer pas à pas. On peut définir la fonction d telle que $d(2m)=2*U_m +m$.
    • Les doublements
      Par extension, si on a une zone d'une taille égale à une puissance de 2 fois une taille pour laquelle le nombre d'étapes est connu, on a : $d(2^km)=2^kU_m+m(k2^{k-1})$.
      Il est à noter que si m=2, on retrouve la formule des puissances de 2 déjà identifiée.
    • Le petit pas
      Lorsqu'il n'y a pas de raccourci, galériens, nous devons faire un petit pas comme pour le cas des 6 réels. J'appelle f la fonction qui donne le nombre d'étapes. Pour 2n éléments, on a ces étapes :

      o U(2(n-1)) (pour fabriquer la collection de "b")
      o 1 (pour fabriquer les 2 "a")
      o 2n-4 (pour préparer la liste à plier)
      o 1 (pour ajouter le deuxième "a")
      o 2 (pour consommer les 2 derniers "b")
      o n-2 (pour plier en deux la liste)

      Résultat : $f(2n)=U_{2(n-1)} +3n-2$
    • Les petits pas
      Par extension, si on doit faire un ensemble de petits pas consécutifs, on trouve :
      $f(2n)=f(2(n-1)) +3n-2$
      $f(2(n-1))=f(2(n-2)) +3n-5$
      $f(2(n-2))=U_{2(n-3)} +3n-8$
      $f(2n)=U_{2(n-3)} +3n-2$

      En généralisant, $f(2n)=U_{2(n-k)} +3kn-\frac{k(3k+1)}{2}$
    • Le cas 80
      Calculons A, la quantité d'étapes a priori nécessaire pour égaliser 80 cases. 80 n'est pas une puissance de 2. On va égaliser 64 cases et finir en petits pas.
      $U_{64}=U_{2^6}=6*2^5=192$
      $A=f(80)=f(2*40)=U_{2*(40-8)}+3*8*40-100=192+860=1052$

      On aurait tort de croire que c'est le résultat final. Pourquoi ne pas égaliser des zones de 10, et les regrouper par doublement ?
      $U_{10}=U_8+15-2=12+13=25$
      $d(80)=d(2^3*10)=2^3U_{10}+10*(3*2^2)=8*25+12*10=200+120=320$.

      Ce chemin demande beaucoup moins d'étapes. Ce n'est pas étonnant. "m" dans la formule de d(2m) est égal à 2n. Alors qu'avec un petit pas f(2n), on ajoute 3n. Les petits pas sont plus laborieux que le raccourci du doublement. Il faudra donc choisir à chaque fois d() ou f(). Mais, en vérité, d() est toujours préférable si elle existe.
    • Les premiers termes de la suite
      2n    $U_{2n}$
      2    1
      4    4
      6    11
      8    12
      10    25
      12    28
      14    47
      16    32
      18    57
      20    60
      22    91
      24    68
      26    105
      28    108
      30    151
      32    80
      34    129
      36    132
      38    187
      40    140
      42    201
      44    204
      46    271
      48    160
      50    233
      52    236
      54    315
      56    244
      58    329
      60    332
      62    423
      64    192
      66    289
      68    292
      70    395
      72    300
      74    409
      76    412
      78    527
      80    320
    • Des formules de tableur (LibreOffice Calc pour moi)
      A3=4
      B3=SI(D3<>"";MIN(C3:D3);C3)
      C3=B2+3*A3/2-2
      D3=SI(E3<>E2;E3*2+A3/2;"")
      E3=RECHERCHE(A3/2;A:A;B:B)
      F3=SI(D3<>"";SI(C3<D3))
      À copier vers le bas évidemment.
    • En image

    OEIS ne connaît pas la suite.
    Voyez-vous d'autres raccourcis ?
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
Connectez-vous ou Inscrivez-vous pour répondre.