[일반] 17x17 problem

[0xrgb(0xrgb)]

17x17 격자판을 4가지 색깔로 칠할건데

직사각형을 이루는 네 점 (기울어지지는 않고)을 어떻게 잡아도 네 점의 색깔이 동일하지 않게 색칠할 수 있는가? 라는 문제임

예를 들어서 3x3 격자판을 2가지 색깔로 칠하면

112
121
211

이렇게 칠하면 직사각형이 생기지 않음. 만약,

121
122
121

이렇게 칠하면 네 꼭지점의 1이 직사각형을 이루기 때문에 실패임

---

만약 이러한 해가 존재한다면 보이고, 존재하지 않는다면 증명하시오

[하루룽(ailedear)]

애매하게 17인 이유는 16x16은 가능한데 17x17은 불가능해서가 아닐까

[하루룽(ailedear)]

In 2012, along with Christian Posthoff, he solved a 4-coloring of 17x17 grids without monochromatic rectangles. 이미 누가 풀었네 ㅅㅂ

[ㄴㄹㄴㅎㅅ지(117.111)]

비둘기 푸드덕푸드덕

[ㄴㄹㄴㅎㅅ지(117.111)]

인줄 알았는데 해가 있구나