第40届IMO试题要标准答案3. 给定一个n×n的棋盘,n是偶数.如果这个棋盘中的两个不同的小方格有一个公共边就说他们是相邻的,但同一个方格不认为与它自身相邻.试找出最小数目的方格,使得当

来源:学生作业帮助网 编辑:作业帮 时间:2024/05/01 06:20:29

第40届IMO试题要标准答案3. 给定一个n×n的棋盘,n是偶数.如果这个棋盘中的两个不同的小方格有一个公共边就说他们是相邻的,但同一个方格不认为与它自身相邻.试找出最小数目的方格,使得当
第40届IMO试题
要标准答案
3. 给定一个n×n的棋盘,n是偶数.如果这个棋盘中的两个不同的小方格有一个公共边就说他们是相邻的,但同一个方格不认为与它自身相邻.试找出最小数目的方格,使得当它们被标记之后,棋盘上每一个方格都至少与一个标记过的方格相邻.

第40届IMO试题要标准答案3. 给定一个n×n的棋盘,n是偶数.如果这个棋盘中的两个不同的小方格有一个公共边就说他们是相邻的,但同一个方格不认为与它自身相邻.试找出最小数目的方格,使得当
n(n+2)/4
将表格二染色,黑白回字相间,最外面为黑,易知黑色有n(n+2)/2,每个标记方格恰与两个和色方格相邻,所以标记格不小于n(n+2)/4
又从第1行第1列开始,逆时针标上1,1,2,2...n-2,n-2去掉外面两层回字后继续标记,依此下去,将奇数号方格作为标记格即可.