【原创】同色矩形的充分条件

104384 · 发表于 2019-11-15 05:59:51

一个组合学问题：
在n行n列的表格A^i_j中填入0和1，证明n大于等于5是存在顶点同色矩形的充分条件。（其实是个开放性问题，我找到了一个对n行n列的和n行m列的，都是充分条件，如果你能找到充要条件的话就更厉害了，那样的话请务必告诉我

61774 · 发表于 2019-11-15 15:07:39

原谅我不知道什么是同色矩形

78603 · 发表于 2019-11-15 20:49:18

不懂rmmm看不明白

22568 · 发表于 2019-11-15 21:06:37

I.
若存在某行有至少四个同色,不妨设11,12,13,14为红.
若不存在红矩形,21,22,23,24中至少三个蓝,31,32,33,34中也至少三个蓝,其中至少有两对同列从而构成蓝矩形.

II.
若不存在某行有至少四个同色,则每行均为三红两蓝或两红三蓝.
不妨设前三行均有三个红.
若不存在红矩形,则前两行恰有一列同为红.不妨设11,12,13,21,24,25为红.
第三行有三个红,要么31,32,33中至少两个红从而与第一行对应列构成红矩形,要么24,25,34,35为红矩形.

106383 · 发表于 2019-12-28 02:39:47

充分不必要，充分有人证明过了，从矩阵角度出发也可以很快得到答案，至于必要性很显然是不必要的，2×2 0矩阵也是顶点同色，所以不必要

[数学趣题] 【原创】同色矩形的充分条件