4 색에 4 색 교차가 있음을 증명 $100×100$ 그리드 [중복]
ㅏ $100×100$그리드는 네 가지 색상으로 채색됩니다. 모든 행과 열에는 각 색상의 정확히 25 개 블록이 있습니다. 교차하는 네 개의 블록이 모두 다른 색상을 갖도록 두 행과 열 사이에 교차점이 있음을 증명합니다.
불변성을 사용하여 이것을 증명하려고합니다. 하지만 어떻게해야할지 모르겠습니다. 나는 또한 이것이 올바른 접근 방식인지 알지 못하므로 어떤 아이디어라도 감사드립니다.)
답변
거기에 주목하십시오 $\binom{4}{2} \cdot 25^2$ 각 행에 서로 다른 색상 쌍이 있으므로 $100 \cdot \binom{4}{2} \cdot 25^2$총 같은 행에있는 서로 다른 색상의 쌍. 이제$100 \cdot \binom{4}{2} \cdot 25^2 > 75 \cdot \binom{100}{2}$. 따라서 일반화 된 pigeonhole 원칙에 따라 두 개의 열이 있습니다.$>75$같은 행에있는 서로 다른 색상의 쌍. 같은 행에 76 쌍의 서로 다른 색상이 있다고 가정 해 보겠습니다. 색상의 이름이 세트에 있다고 말해$\{0,1,2,3\}$. 이제 그 주장이 사실이 아니라면$\{0,1\}$, $\{0,2\}$, $\{0,3\}$ 또는 $\{0,1\}$, $\{0,2\}$, $\{1,2\}$ 우리가 이것을 커버하기 위해 사용할 수있는 가능한 쌍은 $2$열 (WLOG). 첫 번째 경우는 한계가 있기 때문에 분명히 불가능합니다.$25$ 각 색상에 대해 두 번째 경우는 불가능합니다. $3$ 색상은 전체를 덮기에 충분하지 않습니다. $76 \cdot 2=152$블록. 그래서 그 주장은 사실입니다.
편집 : "같은 행에있는 서로 다른 색상의 쌍"이 의미하는 바를 이해할 수없는 경우 @Mike의 아래 설명을 참조하십시오.