Explication visuelle du problème de Putnam 2025 A3
Explication visuelle du problème de Putnam 2025 A3
par Shenghui Yang
Problème : Alice et Bob jouent à un jeu avec une chaîne de n chiffres, chacun étant limité à 0, 1 ou 2. Initialement, tous les chiffres sont 0.
Un coup légal consiste à ajouter ou soustraire 1 à un chiffre afin de créer une nouvelle chaîne qui n’est pas apparue auparavant.
Un joueur qui n’a aucun coup légal perd, et l’autre joueur gagne. Alice commence, et les joueurs alternent les coups. Pour chaque n ≥ 1, déterminez quel joueur possède une stratégie garantissant la victoire. Le problème ainsi que les solutions sont disponibles sur https://kskedlaya.org/putnam-archive/.
Un coup légal consiste à ajouter ou soustraire 1 à un chiffre afin de créer une nouvelle chaîne qui n’est pas apparue auparavant.
Un joueur qui n’a aucun coup légal perd, et l’autre joueur gagne. Alice commence, et les joueurs alternent les coups. Pour chaque n ≥ 1, déterminez quel joueur possède une stratégie garantissant la victoire. Le problème ainsi que les solutions sont disponibles sur https://kskedlaya.org/putnam-archive/.
Le jeu en forme de graphe
Le jeu en forme de graphe
Pour éviter un encombrement visuel excessif dans le graphe de la solution, je choisis pour la visualisation.
n=4
« … un jeu avec une chaîne de n chiffres, chacun étant limité à 0, 1 ou 2 » est équivalent à l’utilisation de Tuples pour générer tous les ensembles ordonnés à 4 éléments en excluant {0,0,0,0}
In[]:=
nodes=Rest@Tuples[{0,1,2},4];
Comptez le nombre de nœuds :
In[]:=
len=Length[nodes]
Out[]=
80
Créez deux objets de tableau dynamique pour stocker des nœuds adjacents. Si deux nœuds diffèrent d’exactement une unité dans exactement une position, tracez une arête les reliant ; par exemple, {1, 1, 2, 1} est relié à {2, 1, 2, 1}. En revanche, aucune arête n’est tracée entre {1, 1, 1, 1} et {2, 2, 2, 2}.
In[]:=
Once[dy1=CreateDataStructure["DynamicArray"];dy2=CreateDataStructure["DynamicArray"];]
In[]:=
dy1["DropAll"];dy2["DropAll"];
In[]:=
Do[With[{res=Abs[nodes[[i]]-nodes[[j]]]},If[Total[res]==1,dy1["Append",nodes[[i]]];dy2["Append",nodes[[j]]];]],{i,1,len-1},{j,i+1,len}]
Créez la liste des arêtes pour le graphe :
In[]:=
el=Thread[dy1["Elements"]dy2["Elements"]];
Comptez le nombre d’arêtes :
In[]:=
Length[el]
Out[]=
212
Visualisez le graphe :
In[]:=
g=Graph[el]
Out[]=
Répartition du degré des sommets :
In[]:=
Histogram[VertexDegree[g]]
Out[]=
Automorphisme et l’ordre de son groupe :
In[]:=
GraphAutomorphismGroup[g]
Out[]=
PermutationGroup[{Cycles[{{4,5},{7,8},{11,12},{14,15},{17,18},{19,20},{21,22},{23,24},{25,53},{26,54},{28,55},{30,56},{32,57},{34,58},{36,59},{38,60},{40,61},{42,62},{44,63},{45,64},{46,65},{47,66},{48,67},{49,68},{50,69},{51,70},{52,71}}],Cycles[{{3,4},{6,7},{9,25},{10,26},{12,27},{13,28},{15,29},{16,30},{18,31},{19,32},{20,44},{21,34},{22,45},{23,36},{24,46},{39,47},{41,48},{43,49},{57,63},{58,64},{59,65},{60,72},{61,73},{62,74},{69,75},{70,76},{71,77}}],Cycles[{{1,9},{2,10},{4,11},{5,12},{6,13},{7,19},{8,20},{17,21},{18,22},{28,32},{29,33},{30,38},{31,39},{36,40},{37,41},{45,47},{46,50},{49,51},{55,57},{56,60},{59,61},{64,66},{65,69},{68,70},{73,75},{74,78},{77,79}}]}]
In[]:=
GroupOrder[%]
Out[]=
24
Calculez les centralités de proximité et mettez-les en évidence :
In[]:=
HighlightGraph[g,VertexList[g],VertexSize->Thread[VertexList[g]->Rescale[ClosenessCentrality[g]]]]
Out[]=
Couplage parfait de graphe
Couplage parfait de graphe
L’étape clé du calcul consiste à reconnaître que l’ensemble de couplage parfait existe toujours pour le graphe.
Pour trouver l’ensemble approprié, utilisez la fonction suivante :
Pour trouver l’ensemble approprié, utilisez la fonction suivante :
In[]:=
inEset=FindIndependentEdgeSet[el];
Mettez les arêtes en évidence à partir des paires ci-dessus :
In[]:=
op=Transpose[Outer[#1->#2&,inEset,{Directive[StandardOrange,Thickness[0.01]]}]][[1]];
In[]:=
Graph[el,EdgeStyle->op]
Out[]=
Revenons à la question originale : si Alice choisit n’importe quel sommet du graphe, Bob choisit le sommet relié par la ligne orange.
Bob a donc une stratégie gagnante.
Bob a donc une stratégie gagnante.
OEIS A224327
OEIS A224327
Pour , le nombre d’arêtes dans le graphe est :
n=4,5,6,7
212,805,2910,10199
In[]:=
ResourceFunction["OEISLookup"][{212,805,2910,10199}]
Out[]=
A224327OEISLookup
La solution sous forme fermée est :
Du point de vue de la combinatoire, la formule sous forme fermée est étayée par l’argument suivant :
Matrice d’adjacence
Matrice d’adjacence
Visualisez la matrice d’adjacence du graphe.
CITER CE NOTEBOOK
CITER CE NOTEBOOK
Explication visuelle du problème de Putnam 2025 A3
par Shenghui Yang
Communauté Wolfram, CHOIX DE L’ÉQUIPE, 28 décembre 2025
https://community.wolfram.com/groups/-/m/t/3598035
par Shenghui Yang
Communauté Wolfram, CHOIX DE L’ÉQUIPE, 28 décembre 2025
https://community.wolfram.com/groups/-/m/t/3598035