구데기컵 2018 빙고의 풀이를 공유하고자 한다.
어차피 solved.ac 레이팅도 안 주는 문제더라.
목차
문제
맞는 말은 체크(클릭)해서 배경을 검은색으로 만들고,
틀린 말은 체크를 안 해서 흰색으로 만들면 된다.
맞는 말인데 흰색이거나, 틀린 말인데 검은색인 칸이 있으면 안 된다.
사실 이 문장은 참이다같은 말은 맞다면 맞고, 틀렸다면 틀린 말이라...
어떻게 가정하든 모든 칸에 모순이 하나도 없으면 된다.
모순이 있는 칸에는 주황색 안쪽 테두리가 칠해질 것이다.
풀이 {explanation}
일단 이 두 칸은 반드시 참일 수밖에 없다.
- B1: 거짓이라고 가정하면 빙고 줄의 일부여야 하는데, 빙고 줄의 일부라면 거짓일 수 없으므로 모순 발생, 그러므로 항상 참
- C3: 거짓이라고 가정하면 빙고 줄의 일부여야 하는데, 빙고 줄의 일부라면 거짓일 수 없으므로 모순 발생, 그러므로 항상 참
확실히 참인 칸은 파란색 테투리를 칠하겠다.
추가로, A열, B열, C열은 빙고 줄이 될 수 없다.
- A열은 A4와 A2 중 하나만 참일 수 있기 때문에 빙고 줄이 될 수 없고,
- B열은 B1이 참이기 때문에 빙고 줄이 될 수 없고,
- C열은 빙고줄이려면 C4가 참이 되어야 하지만, 그러면 C열은 빙고 줄이 될 수 없으므로 빙고 줄이 될 수 없다.
D3이 참이라고 가정하자. 그럼 반드시 D열, E열이 빙고 줄이 된다.
- A5 역시 E5에 의해 참이 된다.
- B4 역시 D열에 의해 참이 된다.
- A1은 A5~E1에 의해 거짓이 된다.
- C1은 A1에 의해 거짓이 된다.
참이라고 가정한 칸은 초록색, 거짓이라고 가정한 칸은 노란색 테두리를 칠할 것이다.
대각선 빙고 줄이 있다가 참이 되어야 하기 떄문에 대각선 줄 둘 중 하나는 반드시 참이다.
A1~E5가 빙고 줄이면 A5~E1이 빙고 줄일 수 없기 떄문에 빙고 줄은 반드시 한 개이다.
일단 A5가 참이니 B4를 참이라고 가정해보자.
그럼 이제 E2에 모순이 생기는데, 이를 해결하려면 빙고 줄이 더 필요하다.
세로나 대각선의 빙고 줄은 더 이상 나올 수 없으므로 가로 빙고 줄이 하나 이상 있다는 의미가 된다.
그렇다면 B2도 참이 된다.
아무튼 E2의 모순을 해결하려면 가로 빙고 줄을 추가해서 빙고 줄의 일부인 칸의 개수를 2n+1개 늘려야 하는데,
- 3열, 4열, 5열은 빙고줄이 되더라도 빙고 줄의 일부인 칸의 개수가 2n개 늘기 때문에,
- 1열은 A1과 C1 때문에 빙고 줄이 될 수 없다.
그렇다면 2열은 반드시 방고 줄일 수밖에 없다.
그럼 E3이 모순이 되며, 이를 해결하려면 참이 아닌 말을 늘려야 되는데, 그건 불가능하다.
그러므로 D3는 거짓이라는 것을 확실하게 알 수 있다.
확실히 거짓인 칸에는 빨간 바깥 테두리를 칠할 것이다.
중간에 정리를 하자면 빙고 줄이 될 수 없는 줄은 다음과 같다:
- 1행(B1), 3행(D3)
- A열(A2, A4), B열(B1), C열(C4), D열(D3)
C3의 모순을 해결하려면 대각선 빙고 줄이 필요하다는 것을 알 수 있다.
우선 A1~E5가 빙고 줄이라고 가정해보자. 그러면 B2에 의해 E열은 빙고 줄이 되고, C1, D1은 각자의 조건에 의해 참이 된다.
그럼 이번에는 B1에 해결할 수 없는 모순이 생긴다.
그러므로 A1~E5는 빙고 줄이 될 수 없고, 반드시 A5~E1이 빙고 줄이 된다.
- 그러면 B4에 의해 (D열은 빙고 줄이 될 수 없으므로) 2행이 빙고 줄이 되고,
- 그러면 B2에 의해 (다른 열은 빙고 줄이 될 수 없으므로) E열이 빙고 줄이 되며,
- D5는 그 조건에 따라 참이 된다.
그럼 일단 C4에 모순이 생기는데, 이는 쉽게 해결할 수 있다.
C열에 이미 1개는 확실히 거짓이고 2개는 확실히 참이기 때문에, C4가 거짓이 되려면 C4와 C5가 참이 되어야 하는데, 그럴 수는 없으니 모순이 된다.
그러므로 C4는 참일 수밖에 없고, 그럼 C5가 참이 되면 다시 C4에 모순이 생기므로 C5는 거짓이다.
A3은 참이 될 수 없다. A열과 3행이 모두 빙고 줄이 될 수 없기 때문에.
이제 아직 모르는 칸이 4개 남았다.
이번에는 D1과 D4가 모두 참이라고 가정해보자.
B3의 모순을 해결하기 위해 B3이 참이라고 하면, D2가 모순이 되며, 이는 해결할 수 없다.
그러므로 D1과 D4 역시 거짓.
마지막으로, B3가 참이라고 가정하면...
더 이상 만들 수 있는 변수가 B5밖에 없는데, B5가 참이든 거짓이든 B3는 모순이 된다.
그러므로 B3 또한 거짓.
마지막으로 남은 아직 모르는 칸은 B5 뿐이다.
두가지 경우가 남았다.
- 이 문제의 정답은 1개가 아니다. (B5는 참)
- 이 문제의 정답은 1개이다. (B5는 거짓)
이 문제의 정답이 1개가 아니라고 가정하자.
그러면 B5는 참이 된다.
그런데, B5마저 참이라는 것을 확실히 알 수 있게 되면 이 문제의 정답은 1개가 된다.
그러므로 B5는 참이 될 수 없다.
그러므로 이게 최종 정답이다.