Problem: Alice and Bob play a game with a string of n digits, each of which is restricted to be 0, 1, or 2. Initially all the digits are 0. A legal move is to add or subtract 1 from one digit to create a new string that has not appeared before. A player with no legal move loses, and the other player wins. Alice goes first, and the players alternate moves. For each n ≥ 1, determine which player has a strategy that guarantees winning. Both the problem and solutions are available at https://kskedlaya.org/putnam-archive/.

Game to graph

To avoid excessive visual clutter in the solution graph, I choose
n=4
for visualization.
“... a game with a string of n digits, each of which is restricted to be 0, 1, or 2” is equivalent to using Tuples to generate all 4-element ordered sets excluding {0,0,0,0}
In[]:=
nodes=Rest@Tuples[{0,1,2},4];
Count the number of nodes:
In[]:=
len=Length[nodes]
Out[]=
80
Create two dynamic array objects to store adjacent nodes. If two nodes differ by exactly one unit in exactly one position, draw an edge connecting them; for example, {1, 1, 2, 1} is linked to {2, 1, 2, 1}. By contrast, no edge is drawn between {1, 1, 1, 1} and {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}]
Create edge list for the graph:
In[]:=
el=Thread[dy1["Elements"]dy2["Elements"]];
Count the number of edges:
In[]:=
Length[el]
Out[]=
212
Visualize the graph:
In[]:=
g=Graph[el]
Out[]=
Distribution of the vertex degree:
In[]:=
Histogram[VertexDegree[g]]
Out[]=
Automorphism and its group order:
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
Compute closeness centralities and highlight:
In[]:=
HighlightGraph[g,VertexList[g],VertexSize->Thread[VertexList[g]->Rescale[ClosenessCentrality[g]]]]
Out[]=

Graph perfect matching

The key step for computation is to recognize that the perfect matching set always exists for the graph. To find the proper set, use the following function:
In[]:=
inEset=FindIndependentEdgeSet[el];
Highlighting the edges from the pairs above:
In[]:=
op=Transpose[Outer[#1->#2&,inEset,{Directive[StandardOrange,Thickness[0.01]]}]][[1]];
In[]:=
Graph[el,EdgeStyle->op]
Out[]=
Let’s come back the original question: If Alice choose any vertex in the graph, Bob chooses the vertex linked by the orange line. So Bob has a winning strategy.

OEIS A224327

Set
n=4,5,6,7
, the number of edges in the graph is
212,805,2910,10199
:
In[]:=
ResourceFunction["OEISLookup"][{212,805,2910,10199}]
Out[]=
A224327OEISLookup
Name: Number of idempotent n X n 0..2 matrices of rank n-1.
Sample: {1,10,51,212,805,2910,10199,10,4649045850,14721978563,46490458660,146444944821,460255540910,1443528741991,4518872583672}
Sequence: {1,10,51,212,805,2910,10199,34984,118089,393650,1299067,4251516,13817453,44641030,143489055,459165008,1463588497,4649045850,14721978563,46490458660,146444944821,460255540910,1443528741991,4518872583672}

The closed form solution is
In[]:=
a[n_]:=n*(2*3^(n-1)-1)
In[]:=
Array[a,10]
Out[]=
{1,10,51,212,805,2910,10199,34984,118089,393650}
From the point of combinatorics the closed form formula is supported by the following argument:
◼
  • One has
    n
    position to choose exactly one digit to flip
    • ◼
  • Say we choose the first position there are two options {0, X, X, X,...,X} <->{1, X,X,X,...,X} and {1,X,X,X,...,X} <->{2,X,X,X,...,X}, in total
    2·
    n-1
    3
    and we have to remove {0,0,0,...,0} with
    n
    zeros.

    • Adjacency matrix

    Visualize the adjacency matrix of the graph

    CITE THIS NOTEBOOK

    Visual explanation of the problem Putnam 2025 A3​
    by Shenghui Yang​
    Wolfram Community, STAFF PICKS, December 28, 2025
    ​https://community.wolfram.com/groups/-/m/t/3598035