하라리의 일반화된 틱택토

Harary의 일반화된 틱택토 또는 동물 틱택토는 게임 틱택토의 일반화로, 게임을 "한 줄로" 구성에 제한되지 않고 다양한 크기의 정사각형 그리드에서 특정 폴리오미노를 완성하는 경주로 정의합니다.1977년 3월 프랭크 해리가 고안했으며, m, n, k 게임의 정의보다 더 넓은 정의입니다.

하라리의 일반화는 대각선 구조가 승리로 간주되지 않기 때문에 틱택토 자체를 포함하지 않습니다.

다른 많은 2인용 게임들처럼, 전략 도용은 두 번째 플레이어가 절대 이길 수 없다는 것을 의미합니다.이제 연구할 일은 첫 번째 선수가 이길 수 있는지, 어떤 보드 크기로 이길 수 있는지, 그리고 몇 번의 동작이 필요한지를 결정하는 것입니다.

결과.

사각형 보드

b를 첫 번째 플레이어가 이길 수 있는 가장 작은 크기의 사각형 보드라고 하고,^[1][2][3] 양쪽의 완벽한 플레이를 가정하여 첫 번째 플레이어가 승리를 강요할 수 있는 가장 작은 수의 움직임이라고 합니다.

• 모노미노: b = 1, m = 1
• domino: b = 2, m = 2
• I-트로미노: b = 4, m = 3
• V-트로미노: b = 3, m = 3
• I-테트로미노: b = 7, m = 8
• L-테트로미노: b = 4, m = 4
• O-테트로미노:첫 번째 선수는 이길 수 없습니다.
• T-테트로미노: b = 5, m = 4
• Z-테트로미노: b = 3, m = 5
• F-펜토미노:첫 번째 선수는 이길 수 없습니다.
• I-펜토미노:첫 번째 선수는 이길 수 없습니다.
• L-펜토미노: b = 7, m = 10
• N-펜토미노: b = 6, m = 6
• P-펜토미노:첫 번째 선수는 이길 수 없습니다.
• T-펜토미노:첫 번째 선수는 이길 수 없습니다.
• U-펜토미노:첫 번째 선수는 이길 수 없습니다.
• V-펜토미노:첫 번째 선수는 이길 수 없습니다.
• W-펜토미노:첫 번째 선수는 이길 수 없습니다.
• X-펜토미노:첫 번째 선수는 이길 수 없습니다.
• Y-펜토미노: b = 7, m = 9
• Z-펜토미노:첫 번째 선수는 이길 수 없습니다.
• 모든 헥소미노는 (현재 미해결 상태인 N-헥소미노를 제외하고, b = 15 및 m = 13일 수 있음):첫 번째 선수는 이길 수 없습니다.
• 모든 헵토미노 이상:첫 번째 선수는 이길 수 없습니다.

레퍼런스

• Beck, József (2008), "Harary's Animal Tic-Tac-Toe", Combinatorial Games: Tic-Tac-Toe Theory, Encyclopedia of Mathematics and its Applications, vol. 114, Cambridge: Cambridge University Press, pp. 60–64, doi:10.1017/CBO9780511735202, MR 2402857
• 가드너, 마틴수학의 거대한 책: 고전 퍼즐, 역설 및 문제: 수론, 대수학, 기하학, 확률, 위상, 게임 이론, 무한대, 그리고 레크리에이션 수학의 다른 주제들.1sted.뉴욕: W. W. 노튼 & 컴퍼니, 2001. 286-311.