Re: Le Challenge des énigmes

[Rêveur]

J'suis qu'un nuuuuull...mes énigmes sont nuuuullles !

246 pour la 1

Même pas d'abord , et pis t'es très loin  d'abord, et c'est bien fait pour toi !

[Bergame]

3047 ?

[Rêveur]

Vous n'avez pas compris ce que sous-entend ce message : << Proposez votre démonstration, quid ! >> ?
Le plus important est le smiley...
Désolé Bergame, merci d'avoir participé et désolé de vous avoir soupçonné de donner des réponses au hasard alors qu'en fait vous faisiez n'importe quoi de votre mieux.
Et d'ailleurs, je vais rédiger un message officiel :

Le Challenge des énigmes avril 2015 est terminé.
Toutes mes, toutes nos félicitations à notre grand gagnant, quid, qui a brillamment résolu l'énigme que j'avais proposée. Bravo, quid ! Nous lui demandons maintenant d'éclairer les autres participants en leur dévoilant sa démonstration.
Félicitations également à kercoz, qui le premier a résolu la seconde question ;
félicitations enfin à l’opiniâtreté, la détermination, la patience de Bergame qui a passé des nuits blanches à compter ces foutus rectangles et à appliquer des formules farfelues qui ne fonctionnaient jamais . Nous sommes désolés pour lui et espérons le retrouver à la prochaine session.
De même bien sûr pour les deux autres tous ceux qui ont participé.
Et merci à vous !

Rêveur

[kercoz]

T' as l' air en colère , Reveur. Perso j' ai débuté le comptage , mais c'est trop lourd comme boulot...La 2e enigme est plus simple et montre qu'il faut trouver une méthodologie de type série.
Je commence par un coin , et tente de bosser en diagonale. sur 4 carrés , je peux faire 4 rectangles de 2. .......Je passe à 9 carrés. ( 3x3). Ca se complique. j' ai des rectangles de 2 carrés , de 3 carrés , et de 2 sur 3......En prenant la patience de faire le décompte,...on peut espérer trouver une progression logique par rapport au carré de 4 carrés....mais pour la confirmer il me faudrait passer au carré de 16 carrés ...et là je craque !

[Rêveur]

Ça, c'est la méthode classique, par laquelle j'ai moi-même commencé. Mais au lieu d'essayer directement l'échiquier - ce serait bien trop fastidieux -, j'ai compté les rectangles de plus petites surfaces (1x1, 1x2, 2x2 etc.). J'ai vite trouvé une formule générale, ai passé une matinée à la démontrer, et ai dès lors été capable de compter rapidement le nombre de rectangles sur n'importe quel rectangle, y compris l'échiquier.
J'attends que quid donne la formule ; sinon, je la donnerai moi-même.

T' as l' air en colère , Reveur.

Non non, pas du tout. J'utilise en effet le vert quand je m'énerve, un peu comme neo avec : << Signé Furax >>, mais également dans d'autres cas. C'est comme si j'ajoutais : << Signé Rêveur >>. C'est une manière...d'insister sur ce que j'écris... Je l'utilise entre autres pour mes messages d'<< organisateur >> d'une section ou autre, comme ici.

[poussbois]

Ah du temps de Magni, les énigmes, pardon, c'était autre chose !

Yep, moi aussi je rejoins le banc des papys atrabilaires...
Mais c'est super dur de faire des énigmes qui ne soient pas des casse-têtes mathématiques. Je le sais, j'avais essayé de lui prendre la main quelquefois avec beaucoup moins de succès. Magni avait le talent des conteurs populaires, des griots africains. Bon, Rêveur est bien parti également, il faut juste qu'il sorte un peu des mathématiques et je suis sûr qu'on arriverait à quelque chose.

Les deux seules énigmes de Magni dont je me souvienne : "-chacun la sienne"
"-la clef de voute de l'empire"

[Rêveur]

Magni, c'était un participant de PhiloForum ?

[neopilina]

Non non, pas du tout. J'utilise en effet le vert quand je m'énerve, un peu comme neo avec : << Signé Furax >>,

Houlà ! Malentendu ! Le " signé Furax " caractérise une ( insupportable ? ) bonne humeur, gaieté radicale, un enthousiasme débordant, chavirant. Oui, oui, la connaissance peut provoquer ce genre d'état second ! En signant " Signé Furax ", je ne renvoie pas au personnage Furax, le méchant, mais bien à l'esprit génialement loufoque, délirant, du feuilleton qui est intitulé " Signé Furax ", nuance !

[Bergame]

Bon alors puisque j'ai gagné, c'est à moi de proposer une énigme, non ? (en tout cas, c'était comme ça du temps béni de Magni )

Alors attention, énigme : Je suis un homme, mais je ne suis pas un homme.

[Rêveur]

1) Je la connais déjà (malheureusement, c'est souvent le cas).
2) Normalement, les règles du Challenge des énigmes ne sont pas les mêmes que celles de ma rubrique d'énigmes, où celui qui a résolu l'énigme est invité à en proposer une à son tour.
Pour le Challenge des énigmes, j'invente (promis, elles seront toutes de moi) des énigmes complexes et les écris, et le premier qui la résous a gagné. Mais vous pouvez toujours proposer de nouvelles règles. Sinon, vous n'avez qu'à proposer vos énigmes sur https://digression.forum-actif.net/t946-paradoxes-enigmes-et-recreations-mathematiques.
3) C'est moi qui ai résolu l'énigme en premier !

[Bergame]

Non, bon, les gars, un peu de discipline s'il vous plait, une seule réponse à la fois.

En plus, Rêveur, il n'y en a pas une seule de bonne.

[Rêveur]

Non, bon, les gars, un peu de discipline s'il vous plait, une seule réponse à la fois.

C'est peut-être votre forum, mais ici c'est ma rubrique.

En plus, Rêveur, il n'y en a pas une seule de bonne.

Je sais. J'écrivais que je connaissais déjà l'énigme, pas la solution.
Je connais deux réponses que je vais vous envoyer par mp, pour éviter d'enlever toute dignité à votre énigme en la résolvant en un clin d’œil devant tout le monde.
Ceci dit, s'il y a plus de deux réponses, je ne les connais pas toutes.

[quid]

J'attends que quid donne la formule ; sinon, je la donnerai moi-même.

Je prépare une explication, j'essaye de la poster rapidement, mais je ne veux pas trop bacler   .

[Rêveur]

C'est tout à votre honneur.

poussbois, pourriez-vous nous écrire les énigmes de Magni dont vous vous souvenez sur la rubrique consacrée ?

[quid]

Bon je vais essayé de faire à la fois concis mais clair.

Pour le problème du nombre de rectangles différents possibles dans un carré à 8 côtés, j'ai vite vu que cela devait être un nombre relativement important, et qu'il fallait une méthode.

Vu le nombre, j'ai cru bon d'essayer une méthode récursive, en ramenant l'expression de la solution à des solutions plus petites identiques, pour obtenir par itération, la résolution.

Je me suis donc mis en tête de trouver une résolution du cas général, quelque soit le nombre de carrés unitaires « n » pour le côté du grand carré, et de découper ce carré à l'aide de carrés de côtés « n-1 », résolvant un maximum de cas, et réduisant les cas non couverts qu'il faudrait trouver.

J'ai donc dessiner cette figure :

On voit que les deux carrés de côté « n-1 » (de couleur verte) comprennent une grande partie des cas du carré de côté « n » (de couleur rouge), et donc, si l'on connaît les solutions des carrés de côté « n-1 », ainsi que les cas restant non couverts, on peut ensuite découper à leur tour, chaque carré de côté « n-1 » de la même manière, et ainsi de suite.

Si ensuite on connaît des solutions de base avec peu de carrés, on peut par itération retrouver la solution pour un carré plus grand.


- La solution serait donc la somme des cas couvert par les deux solutions de côté « n-1 », à laquelle il faut retrancher un fois les solutions de leur intersection, car elles auront été comptées deux fois. Cette intersection est la solution pour « n-2 ».

Si l'on pose « f(n) » la fonction retournant la solution recherchée pour un carré de côté « n », on a pour l'instant et temporairement :

f(n) = 2f(n-1) – f(n-2)

- Mais il faut également ajouter les cas qui ne sont pas dans les deux carrés de côté « n-1 », et il y a parmi ceux-ci, tous les cas qui comprennent les deux coins opposés non couvert :

Pour un coin, et pour un carré de coté « n », le nombre de ces cas correspond au nombre de combinaisons possibles de longueur et de largeur pour des valeurs allant de 1 à « n », c'est à dire « n au carré ».
Pour les deux coins, il faut doubler cette valeur, mais il faut retrancher le seul cas qui comprend à la fois ces deux coins, car il aura été comptabilisé deux fois et qui correspond au carré de coté « n » en entier.

Ce nombre de cas supplémentaires pour un carré de côté « n » est donc de :

(2n² – 1)

- A ce stade, j'avais oublié certains cas qui sont les bandes transversales (ici en rose), qui ne comprennent ni les coins, ni ne sont couvertes par les solutions des deux carrés de côté « n-1 » :

Il y a deux séries, une verticale et une horizontale.

Pour une série et pour un carré de côté « i=8 », cela forme un côté de « 6 » de long, dans lequel il faut compter les bandes transversales.

Il y a 6 bandes transversales de largeur 1, 5 de largeur 2, 4 de largeur 3, 3 de largeur 4, 2 de largeur 5 et 1 de largeur 6.

En nombre, cela correspond à la somme des entiers allant de 1 à 6.

La formule de la somme des entiers allant de 1 à « n », est (n(n+1)/2)

Le nombre de cas dans ces deux séries, horizontale et verticale est donc :

2((n-2)((n-1)/2) =  (n²-3n+2)

- Si l'on pose « g(n) » la fonction qui renvoi le nombre de ces cas supplémentaires non couverts par les deux carrés de côté « n-1 », alors :

g(n) = (2n² – 1) + (n²-3n+2) = (3n²-3n+1)

- Au final on a alors :

f(n) = 2f(n-1) – f(n-2) + g(n)

A ce stade, si l'on développe un peu cette formule, cela donne ceci :

Pour un carré de côté 1, « f(1) = 1 »
Pour un carré de côté 2, « f(2) = 9 »

f(3) = 2f(2) – f(1) + g(3)

f(4) = 2f(3) – f(2) + g(4)
= [4f(2) - 2f(1) + 2g(3)] – f(2) + g(4)
= 3f(2) – 2f(1) + g(4) + 2g(3)

f(5) = 2f(4) – f(3) + g(5)
= [6f(2) - 4f(1) + 2g(4) + 4g(3)] – [2f(2) – f(1) + g(3)]  + g(5)
= 4f(2) – 3f(1) + g(5) + 2g(4) + 3g(3)

Si l'on continue le développement, on arrive à :

f( 8 ) = 7f(2) – 6f(1) + g( 8 ) + 2g(7) + 3g(6) + 4g(5) + 5g(4) + 6g(3)

Normalement, en remplaçant les termes de cette formule, on doit pouvoir calculer le résultat pour un carré de côté 8 :

f( 8 ) = (7*9) – (6*1) + (3*64 – 3*8 + 1) + 2(3*49 – 3*7 + 1) + 3(3*36 – 3*6 +1) + 4(3*25 – 3*5 +1) + 5(3*16 – 3*4 +1) + 6(3*9 – 3*3 +1)
= 63 – 6 + 169 + 254 + 273 + 244 + 185 + 114
= 1296


La formule générale pour tout « n » est la suivante :

f(n) = (n-1)f(2) – (n-2)f(1) + Somme pour a€[1..n-2] (a.g(n-a+1))

ou encore

f(n) = (n-1)f(2) – (n-2)f(1) + S_n-2(a.g(n-a+1))


Rapidement, le développement de S_n-2(a.g(n-a+1)) est le suivant :

Cela utilise les 3 résultats suivants :

La somme des « n » premiers entier : S_n(a) = n(n+1)/2
http://www.les-suites.fr/somme-des-n-premiers-entiers.htm

La somme des « n » premiers carrés : S_n(a²) = n(n+1)(2n+1)/6
http://www.les-suites.fr/somme-des-n-premiers-carres.htm

La somme des « n » premiers cubes : S_n(a³) = n²(n+1)²/4
http://www.les-suites.fr/somme-des-n-premiers-cubes.htm

S_n-2(a.g(n-a+1))
= S_n-2( a (3(n-a+1)² – 3(n-a+1) + 1) )
= 3.S_n-2(a(a² + (n+1)² - 2(n+1)a – (n+1) + a) ) + S_n-2(a)
= 3.S_n-2(a(a² + n(n+1) - (2n+1)a) + S_n-2(a)
= 3.S_n-2(a³ – (2n+1)a² + n(n+1)a) + S_n-2(a)
= 3S_n-2(a³) – 3(2n+1)S_n-2(a²)  + 3n(n+1)S_n-2(a) + S_n-2(a)
= 3(n-2)²(n-1)² /4 - 3(2n+1)(n-2)(n-1)(2(n-2)+1)/6  + 3n(n+1)(n-2)(n-1)/2 + (n-2)(n-1)/2
= (n-2)(n-1)[3(n-2)(n-1) /4 - 2(2n+1)(2(n-2)+1)/4  + 6n(n+1)/4 + 2/4]
= (n-2)(n-1)[3(n-2)(n-1) - 2(2n+1)(2n-3)  + 6n(n+1) + 2]/4
= (n-2)(n-1)[3(n² – 3n + 2) - 2(4n² – 4n – 3)  + (6n² +6n) + 2]/4
= (n-2)(n-1)(n² + 5n + 14)/4

f(n) = 9(n-1) – (n-2) + (n-2)(n-1)(n² + 5n + 14)/4

Pour le problème du nombre de triangles, le principe est le même, la figure découpée ressemble alors à cela :



La formule suivante reste la même :

f(n) = (n-1)f(2) – (n-2)f(1) + Somme pour a€[1..n-2] (a.g(n-a+1))

Il faut trouver « g(n) » qui est en fait égal à 1 : Il n'y a que le triangle complet en supplément.

S_n-2(a.g(n-a+1)) est donc égal à S_n-2(a), soit la somme des « n-2 » premiers entiers  :

g(n) = (n-2)(n-1)/2.

Pour le demi-carré coupé en diagonal, le nombre de triangles inscrits est :

f(n) = (n-1)f(2) – (n-2)f(1) + (n-2)(n-1)/2

avec :
Pour un triangle de côté 1, f(1)=1
Pour un triangle de côté 2, f(2)=3

Au final :

f(n) = 3(n-1) – (n-2) + (n-2)(n-1)/2

et

f( 8 ) = 3*7 - 6 + 6*7/2 = 36

[Rêveur]

GUUUHH !!!??!!?!?! MAIS QU'EST-CE QUE C'EST QUE CE TRUC ?!?!?!
Vous êtes complètement malade !
...Bon, je vais lire ça en détails.

[quid]

Tiens, je n'avais pas fait la simplification de la fonction pour le carré :

f(n) = 9(n-1) – (n-2) + (n-2)(n-1)(n² + 5n + 14)/4

au final, cela donne  :

f(n)=n²(n+1)²/4

Soit la somme des n premiers cubes : S_n(a³)

[Rêveur]

C'est une solution intéressante - et amusante... Mais à lire un tel paquet, les autres participants vont croire que c'est une énigme extrêmement compliquée, avec peu de subtilité et peu d'intérêt...
J'en ai une plus simple :

Les rectangles sont formés par une combinaison de colonnes successives et une combinaison de lignes successives. Par exemple, le rectangle du dessus est formé par la seconde ligne et les 3e et 4e colonnes. Pour toutes les combinaisons, il existe un rectangle. Par exemple, il existe un rectangle formé par les 4e, 5e et 6e lignes et les 7e et 8e colonnes, un par les etc.
Comme chaque combinaison de lignes peut s'associer avec toutes les combinaisons de colonnes, le nombre de rectangles est le produit du nombre de combinaisons << horizontales >> par le nombre de combinaisons << verticales >>.

Une ligne de 1 a une seule combinaison. Celle de 2 a toujours cette combinaison, plus les combinaisons avec cette nouvelle case, qui peut être toute seule ou s'associer avec la case précédente. La ligne de 3 a les trois combinaisons précédentes, plus les associations de la troisième case avec les autres : avec elle-même, avec celle précédente, avec toutes.
1 ; 1 + 2 ; 1 + 2 + 3 ...
Le nombre de combinaisons d'une ligne de n cases est 1 + 2 + 3 + 4 + ... + n
Le nombre de rectangles dans un rectangle de m x n cases est (1 + 2 + 3 + ... + m) (1 + 2 + 3 + ... + n)

Le nombre de rectangles sur un échiquier de 8 x 8 cases est ( 1 + 2 + 3 + ... + 8 ) ( 1 + 2 + 3 + ... + 8 ) = 36 x 36 = 2196.

[Rêveur]

Moi aussi, j'ai oublié de faire une simplification :
1 + 2 + 3 + ... + n = ⁿ⁽ⁿ⁺¹⁾/₂  C'est une formule classique, que je peux démontrer à ceux qui le souhaitent.

Le nombre de rectangles dans un rectangle de m x n cases est donc ^{m(m+1) x n(n+1)}/₄. Dans le cadre du carré, on obtient la formule de quid.

[Rêveur]

J'oubliais les triangles.

Les triangles sont tous formés par des arêtes de cube et une fraction de la fissure. Pour chaque fraction, il n'existe que deux triangles, un en bas (ou à gauche), l'autre en haut (ou à droite). Le nombre de triangles est donc le double du nombre de combinaisons sur la ligne qu'est la fissure, soit 2 x ( 1 + 2 + 3 + ... + 8 )= 2 x 36 = 72

[quid]

à Rêveur.

A je comprends, c'est parce-que je n'aime pas les combinatoires, et je me doutais bien qu'il y avait bien une solution plus simple, mais bon, une fois parti dans ma logique, voyant que cela pouvait aboutir, j'ai poursuivi.

Sinon, c'est quand j'ai cru comprendre que pour le triangle j'avais juste, que je me suis remis au carré et que j'ai vu qu'il me manquait les cas des "bandes roses" dans mas fonction g(n).  

Et effectivement, je n'avais pas non plus, fait la simplification de la fonction pour le triangle :

f(n) = 3(n-1) – (n-2) + (n-2)(n-1)/2

au final, cela donne  :

f(n)=n(n+1)/2

Soit la somme des n premiers entiers : S_n(a)

[Rêveur]

Moi, c'est le contraire : j'obtiens la somme des n premiers entiers, et en déduis n(n+1)/2 ...

[Bergame]

Bon ben personne n'a trouvé mon énigme, hein.

[neopilina]

Serait-ce une femme ?

[Rêveur]

J'ai déjà proposé cette solution.

Bon ben personne n'a trouvé mon énigme, hein.

J'comprends paaas, c'est trop duuuur !

[Bergame]

Ah ! AH !!!!

"Oui, bof, j'la connais, c'est facile..." Hin hin.

C'est sûr que c'est plus compliqué que des problèmes de baignoires qui débordent, hein !?
Faut faire marcher la tête, là.
Hin hin.  

[Contenu sponsorisé]