Putnam 2025 A3 문제의 시각적 해설
Putnam 2025 A3 문제의 시각적 해설
이 노트북은 다음 Wolfram 블로그 글을 LLM 도구를 사용해 한국어로 번역한 버전입니다 .
Wolfram 블로그–"Visual explanation of the problem Putnam 2025 A3" (2025 년 12월 28일)
Wolfram 블로그–"Visual explanation of the problem Putnam 2025 A3" (2025 년 12월 28일)
문제: Alice와 Bob은 길이가 n인 숫자 문자열을 사용하여 게임을 진행합니다. 각 자릿값은 0, 1, 2 중 하나로 제한되며, 초기 상태에서는 모든 자리가 0입니다. 한 번의 합법적인 수란 임의의 한 자릿값을 1만큼 증가시키거나 감소시켜, 이전에 한 번도 등장하지 않았던 새로운 문자열을 만드는 것입니다. 더 이상 합법적인 수를 둘 수 없는 플레이어는 패배하고, 상대 플레이어가 승리합니다. Alice가 선공하며, 두 사람은 번갈아 가며 수를 둡니다. 각 n ≥ 1에 대해, 반드시 승리할 수 있는 전략을 보유한 플레이어가 누구인지 판별합니다. 문제와 해설은 다음 링크에서 확인하실 수 있습니다.
게임을 그래프로 표현하기
게임을 그래프로 표현하기
해설 그래프에서 시각적 복잡성을 줄이기 위해, 여기서는 시각화 대상으로 를 선택합니다.
n=4
“... 각 자릿값이 0, 1, 2로 제한된 길이 n의 숫자 문자열로 이루어진 게임”은 {0,0,0,0}을 제외한 모든 4원 순서쌍을 Tuples를 사용해 생성하는 것과 동치입니다.
In[]:=
nodes=Rest@Tuples[{0,1,2},4];
노드 개수를 계산합니다.
In[]:=
len=Length[nodes]
Out[]=
80
인접 노드를 저장하기 위해 두 개의 동적 배열 객체를 생성합니다. 두 노드가 정확히 한 위치에서만 1만큼 차이가 날 경우, 해당 노드를 연결하는 간선을 그립니다. 예를 들어, {1, 1, 2, 1}은 {2, 1, 2, 1}과 연결됩니다. 반면, {1, 1, 1, 1}과 {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}]
그래프의 간선 목록을 생성합니다.
In[]:=
el=Thread[dy1["Elements"]dy2["Elements"]];
간선 개수를 계산합니다.
In[]:=
Length[el]
Out[]=
212
그래프를 시각화합니다.
In[]:=
g=Graph[el]
Out[]=
정점 차수 분포를 만듭니다.
In[]:=
Histogram[VertexDegree[g]]
Out[]=
자기동형사상과 그 군의 차수를 알아봅니다.
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
근접 중심성 계산 및 강조를 표시합니다.
In[]:=
HighlightGraph[g,VertexList[g],VertexSize->Thread[VertexList[g]->Rescale[ClosenessCentrality[g]]]]
Out[]=
그래프의 완전 매칭
그래프의 완전 매칭
계산의 핵심 단계는 그래프에서 항상 완전 매칭(perfect matching) 집합이 존재함을 인식하는 것입니다. 적절한 집합을 찾기 위해 다음 함수를 사용합니다.
In[]:=
inEset=FindIndependentEdgeSet[el];
위에서 정의한 쌍으로부터 간선을 강조 표시합니다.
In[]:=
op=Transpose[Outer[#1->#2&,inEset,{Directive[StandardOrange,Thickness[0.01]]}]][[1]];
In[]:=
Graph[el,EdgeStyle->op]
Out[]=
이제 위의 문제로 돌아가 보면, Alice가 그래프에서 임의의 정점을 선택하면, Bob은 주황색 선으로 연결된 정점을 선택합니다. 따라서 Bob은 승리를 보장하는 전략을 가집니다.
OEIS A224327
OEIS A224327
n=4,5,6,7
212,805,2910,10199
In[]:=
ResourceFunction["OEISLookup"][{212,805,2910,10199}]
Out[]=
A224327OEISLookup
닫힌 형태의 해는 다음과 같습니다.
조합론적 관점에서, 위 닫힌 형태 공식은 다음과 같은 논리로 뒷받침됩니다.
인접 행렬
인접 행렬
그래프의 인접 행렬을 시각화합니다.
이 노트북 인용 방법
이 노트북 인용 방법
Putnam 2025 A3 문제의 시각적 해설
저자 Shenghui Yang
Wolfram 커뮤니티, STAFF PICKS, 2025년 12월 28일
https://community.wolfram.com/groups/-/m/t/3598035
저자 Shenghui Yang
Wolfram 커뮤니티, STAFF PICKS, 2025년 12월 28일
https://community.wolfram.com/groups/-/m/t/3598035