Le Puzzle de l'Avent 2019
Posté le 01/12/2019 11:47
Bienvenue à tous dans la période de l'Avent. Pour vous aider à attendre Noël, Planète Casio vous propose son calendrier aux 24 problèmes mathématiques et informatiques. 
Le Puzzle de l'Avent de cette année est un jeu dans lequel vous devez résoudre des petits problèmes mathématiques et informatiques. Chaque jour, je vous donnerai des pièces du puzzle codées par un
code couleur. Votre tâche est de retrouver le code de chaque image et de les décoder ! À la fin du mois, les pièces se combineront pour former une
image de Noël.
J'ai demandé une Graph 35+E II à Casio pour récompenser la première personne qui résoud le puzzle. Casio a confirmé qu'ils sont d'accord, je pourrai donc envoyer le lot dès que je l'aurai reçu.
Voici l'énoncé précis du jeu !
Le but du jeu est de reconstituer intégralement l'image de Noël. Il s'agit d'une image de 128x64 pixels en quatre niveaux de gris (noir, gris foncé, gris clair, blanc). Il y a 128 pièces à ce puzzle, que je distribuerai tous les jours jusqu'à Noël.
Pour participer, envoyez-moi un MP avec votre image. La personne qui aura reconstitué le plus fidèlement l'image le 24 Décembre à 23h59 remportera le Puzzle et aura le titre de
Maître du Puzzle.
Toutes les personnes qui m'auront envoyé une participation ayant plus de 90% de pixels justes (soit 7372 sur 8192) auront également le titre.
Les pièces sont réparties en quatre cadrants comme ceci :
Contrairement à l'année dernière, les indices ne sont pas cachés, donc vous pouvez poser des questions et je vous répondrai dans une certaine mesure (sans révéler les résultats). Donc n'hésitez pas à demander dans les commentaires si vous avez du mal, je donnerai des explications !
Tous à vos postes, on commence maintenant !
Notes du futur.
• Le 23 Décembre, Filoji a reconstitué l'intégralité de l'image !
• La solution des problèmes est disponible au format PDF !
Liste des indices et pièces de l'image
1er Décembre
Pour les premiers jours, on va se concentrer sur le code couleur. Toutes les images, sauf la première, ont été un peu modifiées et bougées. Le
carré code à droite de chaque image indique quelle opération j'ai faite.
Les pièces ont été agrandies fois 2 (elles font 16x16 pixels au lieu de 8x8), je vous conseille de les réduire avant de commencer à travailler avec.
2 Décembre
Contrairement à hier, aujourd'hui les transformations se marchent un peu sur les pieds. Il faut donc trouver la bonne façon de les combiner...
Sinon le principe est exactement comme hier. Si vous avez déjà utilisé des couleurs en programmation, ça vous posera pas de problème.
3 Décembre
Il n'y a rien de vraiment nouveau, mais parfois durant les problèmes j'aurai besoin de transformer les pièces plusieurs fois.
4 Décembre
Vous avez déjà tous les éléments concernant le fonctionnement du code couleur. Désormais, on va jouer un peu avec des problèmes de maths et d'informatique.
Attention, ne vous précipitez pas car j'ai
mélangé les carrés codes.
Pour retrouver qui va avec qui, voici une aide. L'image ci-dessous représente un
graphe, avec des
noeuds (les ronds) et des
arêtes (les traits). Les noeuds de gauche représentent les pièces d'aujourd'hui, les noeuds de droite représentent les carrés codes mélangés.
J'ai fait en sorte que chaque pièces à gauche soit reliée par une arête à son carré code à droite. Mais j'ai aussi rajouté des arêtes inutiles pour vous embêter.
Votre tâche est de retrouver l'unique façon de faire correspondre les pièces avec les carrés codes par des arêtes. Ça s'appelle un
couplage parfait.
5 Décembre
Cette fois, j'ai
mélangé les pièces. Pour retrouver l'ordre correct, vous devez trier les nombres inscrits à gauche des pièces par ordre de qui se divise le mieux. L'image à côté du nombre qui se divise le moins bien se décode par le carré code
#. L'image à côté du nombre qui se divise le mieux se décode par le carré code
O. Tout le reste est dans l'ordre, vous verrez qu'il n'y a pas d'ambiguité.
6 Décembre
Aujourd'hui, j'ai encodé toutes les pièces avec
le même carré code. Pour trouver lequel, utilisez le programme Python suivant. Vous devez chercher
n et
m de sorte que la fonction
A renvoie 61. Caclulez alors
n*m%6 et vous aurez le numéro du carré code à utiliser. (Ils sont numérotés de 1 à 6 de haut en bas).
def A(m, n):
if m == 0:
return n+1
elif n == 0:
return A(m-1, 1)
else:
return A(m-1, A(m, n-1))
7 Décembre
Là encore j'ai été sympa, j'ai tout codé avec le même carré code. Pour savoir lequel, utilisez le graphe ci-dessous. Dans ce graphe, il y a des
arêtes pleines et des
arêtes pointillées, et un noeud marqué par un double trait. Je prétends qu'il existe une suite de "plein" et de "pointillé" telle que peu importe d'où vous partez, si vous suivez des arêtes du type indiqué par la suite, vous arriverez toujours au noeud marqué.
Le numéro du carré code à utiliser aujourd'hui est la longueur de la plus petite séquence de "plein" et "pointillé" qui a cette propriété.
Cela s'appelle un
mot synchronisant.
8 Décembre
Pas d'indice, vous devriez trouver tous seuls quelle pièce a été encodée comment.
9 Décembre
Je continue sur mon format simple pour l'instant, j'ai tout encodé avec le même carré code (j'espère que ça vous simplifie un peu le travail). Lequel ? Tout est inscrit dans le graphe ci-dessous.
Ce graphe contient un certain nombre de
cliques. Une clique, c'est k sommets différents qui sont totalement reliés entre eux. Cela signifie que si vous regardez deux des sommets, il y a forcément une arête entre les deux. Pour avoir une clique de taille k, il faut donc que chacun des sommets soit directement reliés aux k-1 autres !
La taille de la plus grande clique dans ce graphe est le numéro du carré code à utiliser aujourd'hui. Et pour votre information, ce problème de la
clique maximale est très difficile à résoudre (on ne connaît pas d'algorithme rapide qui trouve la plus grande clique d'un graphe).
10 Décembre
Comme d'habitude, un des carrés codes a été utilisé pour coder toutes les image. Pour retrouver lequel, déterminez le chiffre des dizaines dans le prochain élément de cette suite suite relativement connue.
18, 9, 28, 14, 7, 22, 11, 34, 17, ?
11 Décembre
Le programme ci-dessous affiche le numéro (toujours entre 1 et 6) du bon carré code... si vous arrivez au bout.
def h(x):
return not not x and g(x - (not not x))
def g(x):
return not x or h(x - (not not x))
a = 67091015026795951534974163063551679485
b = 14869428421844477043415143396333267370
c = 18130045244705851716678308487239340348
d = 27737016800392073340078206984446832421
e = 27050830777865150327799699254308046502
f = 31380753929535438225805729259152129373
print(h(a) + g(b) + h(c) + g(d) + h(e) + g(f))
12 Décembre
Comme d'habitude, un seul carré code a été utilisé pour tout encoder. Aujourd'hui, ils sont numéros de 0 (le plus haut) à 5 (le plus bas). Pour savoir quel carré j'ai utilisé, trouvez un chemin le plus long possible de s à t dans le graphe ci-dessous, et calculez sa longueur modulo 6.
13 Décembre
Les pièces sont de nouveau numérotées de 0 à 5. Trouvez p et q non triviaux tels que p×q = 142941853471579. Le numéro de la pièce aujourd'hui est égal au modulo 6 de p. Pour vous aider, sachez que le modulo 6 de q doit désigner la même pièce.
14 Décembre
Comptez le nombre de triangles dans le graphe du 9 Décembre. Un triangle, c'est quand trois noeuds sont complètement reliés entre eux (une clique de taille 3). Le résultat modulo 6 est le numéro du carré code permettant de décoder les pièces d'aujourd'hui, comptées de 0 à 5.
Pour les gens très chauds type
Dark Storm : Compter le nombre de mineurs isomorphes à K₃. Programme fortement conseillé.
15 Décembre
Comptez le nombre de façons différentes d'obtenir 15 par somme de 5, 2, 1 (sans prendre l'ordre en compte). Par exemple, 5+5+2+2+1, ou 2+2+2+2+2+2+1+1+1. Le nombre de façons modulo 6 est le numéro du carré code d'aujourd'hui.
Pour les gends très chauds type
Dark Storm : Compter le nombre de façons, toujours sans prendre l'ordre en compte, mais avec le parenthésage. Par exemple, ((5+5)+(2+2))+1 ou ((5+5)+2)+(2+1).
16 Décembre
Les carrés code sont encore numérotés de 0 à 5. Pour trouver le bon, déterminez le nombre d'arêtes minimum qu'il faut enlever pour couper la grille de taille 5 (ci-dessous) en deux parties :
Ça s'appelle une
coupe minimum.
Pour les gens très chauds type
Dark Storm : Trouver la coupe minimum du tore n×n pour tout n.
17 Décembre
Prenez la liste [7,4,2,5,1,3,6]. Elle n'est pas croissante, mais en supprimant des éléments on peut la rendre croissante. Par exemple, si je supprime 7, 4, 5 et 1, il me reste [2,3,6] qui est croissante. On appelle ça une sous-liste croissante (rien de surprenant ici).
Comptez le nombre de sous-listes croissantes de [7,4,2,5,1,3,6].
Pour les gens très chauds type
Dark Storm : Caractériser le nombre de sous-listes croissantes de taille 2 dans la liste [σ(i) : 1 ≤ i ≤ n] pour σ ∈ Sn (permutations de {1..n}).
18 Décembre
Aujourd'hui on ne fait pas très intellectuel, voici les pièces et leurs carrés codes associés, comme les premiers jours. Rassurez-vous, c'est pas aussi méchant.
19 et 20 Décembre
Pas de codage pour aujourd'hui. On arrive à la fin !
21 Décembre
Comptez le nombre de faces de la rosace au dos de la Graph 35+E II !
Il s'agit du nombre de face sur la rosace complète (la Graph 35+E II étant rectangulaire, elle n'est pas imprimée entièrement). Vous pouvez le faire sans quitter votre chaise, y compris si vous n'avez pas de Graph 35+E II.
Calculez le nombre de faces modulo 157, 97, 79 et 71. L'un de ces modulos a une parité différente des autres, et il correspond au carré code à utiliser pour déchiffrer les 8 pièces centrales.
22 Décembre Il y a des schémas de la rosace dans le manuel.
23 Décembre À cause des symétries de la rosace, il suffit de compter environ 4% des faces.
Fichier joint
Citer : Posté le 12/12/2019 21:45 | #
Parce que c'est une 4-clique ! L'image illustre la recherche d'une 4-clique et tous les schémas en bleu n'en sont pas. Celui en rouge en est une !
Citer : Posté le 12/12/2019 21:46 | #
Ah non (toujours rien pigé je vais chercher ce week-end
Citer : Posté le 13/12/2019 12:11 | #
Je suis vraiment en retard cette année...
Citer : Posté le 13/12/2019 21:46 | #
Moi aussi. Vraiment désolé...
Donc soit dit en passant, tout comme l'histoire de la fonction A, il y a des choses à dire sur la suite du 10 Décembre !
Voilà les pièces pour hier.
Comme d'habitude, un seul carré code a été utilisé pour tout encoder. Aujourd'hui, ils sont numéros de 0 (le plus haut) à 5 (le plus bas). Pour savoir quel carré j'ai utilisé, trouvez un chemin le plus long possible de s à t dans le graphe ci-dessous, et calculez sa longueur modulo 6.
Ajouté le 13/12/2019 à 21:48 :
Et pour aujourd'hui.
Les pièces sont de nouveau numérotées de 0 à 5. Trouvez p et q non triviaux tels que p×q = 142941853471579. Le numéro de la pièce aujourd'hui est égal au modulo 6 de p. Pour vous aider, sachez que le modulo 6 de q doit désigner la même pièce.
Citer : Posté le 14/12/2019 09:21 | #
On peut trouver sans faire le problème :eyes:
Citer : Posté le 14/12/2019 09:23 | #
Je sais... je peux pas être méchant tout le temps non plus...
Je vous ai pas donné n'importe quoi à factoriser non plus (48 bits). Il faut coder si vous voulez le faire à la main.
Citer : Posté le 14/12/2019 10:33 | #
Pour le plus long chemin, on peut passer plusieurs fois par un même sommet mais chaque arête doit être parcourue qu'une unique fois ? Et la distance se compte en nombre d'arêtes parcourues ?
Parce que sinon +∞ mod 6 je sais pas combien ça fait
Citer : Posté le 14/12/2019 10:35 | #
Oui. Un "chemin", par définition, ne passe qu'une seule fois par chaque arête, et on compte la distance en nombre d'arêtes.
Le plus court chemin est de longueur 4, par exemple (par en bas).
Ajouté le 14/12/2019 à 18:25 :
Voilà, j'ai repris un peu d'avance et je suis dans les temps. On passe aux pièces d'aujourd'hui.
Comptez le nombre de triangles dans le graphe du 9 Décembre. Un triangle, c'est quand trois noeuds sont complètement reliés entre eux (une clique de taille 3). Le résultat modulo 6 est le numéro du carré code permettant de décoder les pièces d'aujourd'hui, comptées de 0 à 5.
Pour les gens très chauds type Dark Storm : Compter le nombre de mineurs isomorphes à K₃. Programme fortement conseillé.
Ajouté le 15/12/2019 à 15:41 :
Et c'est parti pour aujourd'hui !
Comptez le nombre de façons différentes d'obtenir 15 par somme de 5, 2, 1 (sans prendre l'ordre en compte). Par exemple, 5+5+2+2+1, ou 2+2+2+2+2+2+1+1+1. Le nombre de façons modulo 6 est le numéro du carré code d'aujourd'hui.
Pour les gends très chauds type Dark Storm : Compter le nombre de façons, toujours sans prendre l'ordre en compte, mais avec le parenthésage. Par exemple, ((5+5)+(2+2))+1 ou ((5+5)+2)+(2+1).
Citer : Posté le 16/12/2019 21:41 | #
Je viens de trouver le nombre de possibilités mais je voulais savoir si une formule existait pour le faire ?
Citer : Posté le 16/12/2019 21:45 | #
Il existe en effet une formule directe, mais pas pour tous les choix de valeurs si je me souviens bien, et elle n'est pas très jolie. On préfère généralement la variante programmation dynamique qui est une expression récursive.
Citer : Posté le 16/12/2019 21:46 | #
Tu m’as perdu...
Citer : Posté le 16/12/2019 21:53 | #
Eh bien, la formule est moche quand elle existe. Donc on préfère dire comme ceci : le nombre de façons de faire 15 par somme de 5,2,1 se calcule de la façon suivante :
• Si on ne prend pas de 5, c'est le nombre de façons de faire 15 par somme de 2 et 1
• Si on en prend un, c'est le nombre de façons de faire 10 par somme de 2 et 1
• etc jusqu'à 3, le maximum.
Et donc le nombre total de façons de faire 15 par somme de 5,2,1 c'est la somme de toutes ces façons.
Comme tu peux le voir, je n'ai pas donné de formule mais j'ai exprimé la solution du problème de comptage en fonction des solutions d'autres problèmes de comptage "plus simples". On appelle ça une définition récursive. C'est très élégant
Ajouté le 16/12/2019 à 22:11 :
Et j'en profite pour envoyer les pièces d'aujourd'hui.
Les carrés code sont encore numérotés de 0 à 5. Pour trouver le bon, déterminez le nombre d'arêtes minimum qu'il faut enlever pour couper la grille de taille 5 (ci-dessous) en deux parties :
Ça s'appelle une coupe minimum.
Pour les gens très chauds type Dark Storm : Trouver la coupe minimum du tore n×n pour tout n.
Au fait, le problème avec les mineurs est vraiment compliqué, je plaisantais quand je l'ai posé. Les autres sont faisables.
Citer : Posté le 17/12/2019 21:53 | #
Pas compris...
Citer : Posté le 17/12/2019 22:05 | #
La grille 5x5 est connectée, dans le sens où tu peux aller de n'importe quel noeud à n'importe quel autre en passant par des arêtes. Le but de cet exercice est de retirer des arêtes pour séparer les noeuds en deux parties, de telle sorte qu'on ne puisse pas voyager entre les deux parties.
Ajouté le 17/12/2019 à 22:10 :
Voici l'exercice d'aujourd'hui, d'ailleurs.
Prenez la liste [7,4,2,5,1,3,6]. Elle n'est pas croissante, mais en supprimant des éléments on peut la rendre croissante. Par exemple, si je supprime 7, 4, 5 et 1, il me reste [2,3,6] qui est croissante. On appelle ça une sous-liste croissante (rien de surprenant ici).
Comptez le nombre de sous-listes croissantes de [7,4,2,5,1,3,6].
Pour les gens très chauds type Dark Storm : Caractériser le nombre de sous-listes croissantes de taille 2 dans la liste [σ(i) : 1 ≤ i ≤ n] pour σ ∈ Sn (permutations de {1..n}).
Citer : Posté le 18/12/2019 08:44 | #
Est-ce que si on a la liste [1,2,3], on doit compter les listes [1,2] et [1,3] comme des listes différentes ?
Citer : Posté le 18/12/2019 09:35 | #
Oui, la liste [1,2,3] contient donc 7 sous-listes croissantes : [1], [2], [3], [1,2], [1,3], [2,3] et [1,2,3].
Citer : Posté le 18/12/2019 10:12 | #
Ok merci
Ensuite il fait faire le résultat modulo 6 n'est-ce pas ?
Citer : Posté le 18/12/2019 10:14 | #
Oui, c'est ça ! Et on compte de 0 à 5.
Ajouté le 18/12/2019 à 22:39 :
Aujourd'hui on ne fait pas très intellectuel, voici les pièces et leurs carrés codes associés, comme les premiers jours. Rassurez-vous, c'est pas aussi méchant.
Ajouté le 20/12/2019 à 22:46 :
Dernière update ! On arrive à la fin.
Comme j'ai trouvé que c'était assez compliqué jusque-là, je vais vous donner les dernières pièces directement. Si vous voulez regarder d'autres problèmes, essayez les versions avancées que j'ai citées pour Darks, vous verrez qu'il y a des choses intéressantes.
Voilà comment va se passer la suite. J'ai déjà donné 120 pièces sur 128 pour reconstituer l'image. Rétrospectivement, je doute que quelqu'un arrive à obtenir l'image parfaite, donc voici comment on va faire.
La personne qui aura reconstitué l'image la plus proche de l'origine le 24 Décembre à 23h59 remportera le puzzle.
Pour participer :
• Envoyez-moi votre image par MP.
• Laissez un message sur ce topic (sans montrer votre image !), auquel je répondrai avec votre score (nombre de pixels justes sur 8192).
J'ai eu la confirmation de Casio pour avoir une Graph 35+E II comme lot, mais pas encore la calculatrice. Donc ça va se faire, il faudra juste être patient.
De plus, toute personne qui aura reconstitué au moins 90% de l'image le 24 Décembre à 23h59 obtiendra le titre de Maître du Puzzle (en plus du gagnant). Cela représente 7372 pixels justes.
Ladies and gentlemen, vous aurez toutes les cartes en main dès demain matin. Let's roll!
Ajouté le 20/12/2019 à 22:49 :
J'ai au passage mis à jour le post principal avec les détails des règles.
Citer : Posté le 20/12/2019 23:55 | #
Je confirme pour les choses intéressantes, Lephe a fait du très bon boulot là dessus.
En allant chercher à droite à gauche, y'a moyen d'apprendre pas mal de trucs en théorie des graphes entre autres. Un poil de dénombrement aussi.
Citer : Posté le 21/12/2019 17:34 | # |
Fichier joint
Comme on m'a demandé de l'aide pour faire le puzzle... voici un indice. C'est le rectangle tout en haut à gauche.
Citer : Posté le 21/12/2019 18:14 | #
Le puzzle a l'air si joli :eyes: