初中竞赛每日一题 第两百二十八题的解答
本题目选自 2020欧洲女子数学奥林匹克土耳其代表队选拔赛
解：最小值为2.
构造如下：最左侧的那列和最下方的那行为红色格，其他单元格均为白色格.
下面证明同色组个数至少为2.
注意到交换任意两行的位置, 不会改变同色组的个数, 也不会改变"对于任意两个和两列,它们相交组成的4个单元格中, 至少有两个同行或同列的单元格同色"这一属性, 故对于符合条件的染色方法, 我们可以任意的交换其中任意两行的位置, 同理,也可以交换任意两列的位置.
那么我们按如下规则进行交换:
首先, 我们将红色格子最多的那行交换至最下面那行, 然后将除此之外红色格子最多的那行移至除此之外的最下面那行...以此类推, 直到对任意两行, 上方的那行的红色格子个数都不多于下方那行为止.
然后, 我们将红色格子最多的那列交换至最左侧那列,然后将除此之外红色格子最多的那行移至除此之外最左侧那列...以此类推, 直到对任意两列, 靠右的那列的红色格子个数都不多于靠左那列为止.
此时, 对任意一个红色单元格, 它的左侧没有白色单元格, 下方也没有白色单元格.
假设红色单元格A下方有白色单元格B, 对任意一列, 若A所在那行为白色单元格, B所在那行为红色单元格, 那么这两个单元格与A,B组成的单元格不满足条件, 矛盾!
故对任意一列, A所在那行的红色单元格个数不少于B所在那行.
而A本身为红色,B为白色, 故A所在那行的红色单元格个数一定比B所在那行多, 而A在B上方,矛盾!
因此, 对任意一个红色单元格, 它的下方没有白色单元格.
同理, 对任意一个红色单元格, 它的左侧没有白色单元格.
此时我们考虑左起第一列. 若该列全为红, 则我们有一个同色组. 否则, 该列最顶端为白. 由于对任意一个红色单元格, 它的左侧没有白色单元格, 故最上方那行为全白, 我们有一个同色组.
故最左侧那列和最上方那行中至少有一个同色组.
同理, 最下面那行与最右侧那列中至少有一个同色组, 故该染色方法中至少有2个同色组.
由于我们做的交换不改变同色组的个数,故原染色方法中也至少有2个同色组.
证毕.
应读者要求，把公众号菜单的一些功能也做了关键词，现在输入关键词，不仅可以下载资料，还可以查看本公众号的专题文章了！
输入 KEYWORDS
可查看关键词可下载资料
输入 初中竞赛每日一题
可查看初中竞赛每日一题合集
输入 TRANSLATION
可查看本公众号翻译文章合集
输入 鸟人的足迹
可下载赵力老师文章合集
输入 IZHO2020
可下载2020年第十六届国际ZhautyKov奥林匹克试题及官方解答
输入 CanadaMC
可下载加拿大数学竞赛合集（感谢赵江睿提供）
输入 AustraliaMO
可下载2016-2020澳大利亚数学奥林匹克及其解答
输入 MPFG
可下载2014-2019MPFG试题及官方解答合集
输入 APMO
可下载2004-2019亚太地区数学奥林匹克合集
输入 USMC
可下载美国数学竞赛合集（感谢赵江睿提供）
输入 USAMO
可下载2000-2019USAMO解答合集
输入 USAJMO
可下载2014-2019USAJMO解答合集
输入 ARML
可下载2017-2019ARML试题及官方解答合集
输入 AMC
可下载2000-2019AMC试题及解答合集（非官方，无答案）
输入 AIME
可下载2000-2019AIME试题（非官方，无答案）
输入 Putnam
可下载2017-2019普特南数学竞赛试题及部分官方解答
输入 USMCA
可下载2020年及2019年美国USMCA试题及官方答案
输入 ELMO
可下载2013-2019ELMO数学竞赛官方解答
输入 ISL
可下载2009-2018IMO预选题官方解答合集
输入 USAMTS2019
可下载2019年度USAMTS三轮官方答案
输入 PUMAC2019
可下载2019普林斯顿数学竞赛试题及官方答案
输入 BMT2019
可下载2019伯克利数学竞赛春季赛试题及官方答案
输入 BMMT2019
可下载2019伯克利数学竞赛秋季赛试题及官方答案
输入 EMC2019
可下载2019数学欧洲杯试题及官方答案
输入 EMC
可下载第1-8届数学欧洲杯试题及官方答案合集
输入 UKMC
可下载2000-2019英国数学竞赛合集（感谢赵江睿提供）
输入 CRUX2019
可下载2019年度CRUX杂志电子版合集
输入 CRUX2018
可下载2018年度CRUX杂志电子版合集
输入 CRUX2017
可下载2017年度CRUX杂志电子版合集
输入 CRUX2016
可下载2016年度CRUX杂志电子版合集
输入 CRUX2015
可下载2015年度CRUX杂志电子版合集