灯下 登录
番外 · 题谱 · 2014 · P11

2014 Putnam B5

数论 · P3/P6 · 压轴题

题面据 Putnam 可核档案整理;中文题意为本站自译,公式请以原始来源为准。 PDF:https://kskedlaya.org/putnam-archive/2014.pdf。

Putnam 2014 B5 number-theory

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 n×nn \times n matrices with entries in the field
Z/pZ\mathbb{Z}/p \mathbb{Z} of integers modulo pp, where nn is a fixed positive integer and pp 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 nn and pp.)

在第 75 届年度普特南运动会上,参与者进行数学游戏竞赛。

帕特尼斯和基塔玩一个游戏,轮流选择一个元素

来自可逆 n×nn \times n 矩阵组,其中包含字段中的条目

Z/pZ\mathbb{Z}/p \mathbb{Z}pp 为模的整数,其中 nn 是固定正整数,pp 是固定质数。游戏规则是:

(1)

玩家不能选择任何一个玩家在上一回合中选择过的元素。

(2)

玩家只能选择与所有先前选择的元素可交换的元素。

(3)

无法在回合中选择元素的玩家将输掉游戏。

帕特尼斯先行。哪位玩家有获胜策略?
(您的答案可能取决于 nnpp。)

提示 1

先看同余、整除、最大公因数和 p 进赋值。

提示 2

把整数条件转成同余方程、指数比较或下降过程。

提示 3

若要存在性,用构造;若要唯一性,用最小反例、无限下降或模限制。

完整解答

这页先给题面、题型和提示阶梯,完整证明留给读者逐步展开。2014 年 Putnam B5 可先归入数论:第一步把题设翻成对象、条件、目标三行;第二步沿提示寻找不变量、标准构型或关键变形;第三步补齐边界情形,并回到题目原要求核对。

这题适合先独立想一轮再打开提示。不要急着搜索完整解答,先问自己:题面里最硬的限制是哪一句?