题面据 Putnam 可核档案整理;中文题意为本站自译,公式请以原始来源为准。 PDF:https://kskedlaya.org/putnam-archive/2014.pdf。
In the 75th annual Putnam Games, participants compete at mathematical games.
Patniss and Keeta play a game in which they take turns choosing an element
from the group of invertible matrices with entries in the field
of integers modulo , where is a fixed positive integer and is a fixed prime number. The rules of the game are:
(1)
A player cannot choose an element that has been chosen by either player on any previous turn.
(2)
A player can only choose an element that commutes with all previously chosen elements.
(3)
A player who cannot choose an element on his/her turn loses the game.
Patniss takes the first turn. Which player has a winning strategy?
(Your answer may depend on and .)
在第 75 届年度普特南运动会上,参与者进行数学游戏竞赛。
帕特尼斯和基塔玩一个游戏,轮流选择一个元素
来自可逆 矩阵组,其中包含字段中的条目
以 为模的整数,其中 是固定正整数, 是固定质数。游戏规则是:
(1)
玩家不能选择任何一个玩家在上一回合中选择过的元素。
(2)
玩家只能选择与所有先前选择的元素可交换的元素。
(3)
无法在回合中选择元素的玩家将输掉游戏。
帕特尼斯先行。哪位玩家有获胜策略?
(您的答案可能取决于 和 。)
提示 1
先看同余、整除、最大公因数和 p 进赋值。
提示 2
把整数条件转成同余方程、指数比较或下降过程。
提示 3
若要存在性,用构造;若要唯一性,用最小反例、无限下降或模限制。
完整解答
这页先给题面、题型和提示阶梯,完整证明留给读者逐步展开。2014 年 Putnam B5 可先归入数论:第一步把题设翻成对象、条件、目标三行;第二步沿提示寻找不变量、标准构型或关键变形;第三步补齐边界情形,并回到题目原要求核对。
这题适合先独立想一轮再打开提示。不要急着搜索完整解答,先问自己:题面里最硬的限制是哪一句?