灯下 登录
番外 · 闲灯 / IMO Shortlist / C2 · combinatorics

2024 IMO Shortlist C2

题面据 IMO Shortlist 可核档案整理;中文题意为本站自译,公式请以原始来源为准。 PDF:https://www.imo-official.org/problems/IMO2024SL.pdf。

IMO Shortlist 2024 C2 combinatorics

Let nn be a positive integer. The integers 1,2,3,,n21,2,3,\ldots,n^2 are to be written in the cells of an n×nn\times n board, each integer in exactly one cell and each cell containing exactly one integer. For every integer dd with dnd\mid n, the dd-division of the board is the division of the board into (n/d)2(n/d)^2 nonoverlapping sub-boards, each of size d×dd\times d, such that each cell is contained in exactly one d×dd\times d sub-board.

We say that nn is a cool number if the integers can be written on the n×nn\times n board such that, for each integer dd with dnd\mid n and 1<d<n1<d<n, in the dd-division of the board, the sum of the integers written in each d×dd\times d sub-board is not a multiple of dd.

Determine all even cool numbers.

nn 为正整数。将整数 1,2,3,,n21,2,3,\ldots,n^2 写入一个 n×nn\times n 棋盘的格子中,每个整数恰好写入一个格子,每个格子也恰好含有一个整数。对每个满足 dnd\mid n 的整数 dd,棋盘的 dd-划分指把棋盘分成 (n/d)2(n/d)^2 个互不重叠的 d×dd\times d 子棋盘,且每个格子恰好属于一个这样的子棋盘。

若可以这样填写 n×nn\times n 棋盘,使得对每个满足 dnd\mid n1<d<n1<d<n 的整数 dd,在棋盘的 dd-划分中,每个 d×dd\times d 子棋盘内所写整数之和都不是 dd 的倍数,则称 nn 是 cool number。

确定所有偶数 cool number。

提示 1

先决定对象是什么:集合、图、排列、颜色、路径,还是一次操作后的状态。

提示 2

找一个极端对象、双计数式、不变量,或把限制转成图上的局部条件。

提示 3

把局部限制累加成全局矛盾,或给出覆盖全部情形的构造。

完整解答

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

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