| [ QuizWit ] in KIDS 글 쓴 이(By): noir (김 희연) 날 짜 (Date): 1995년10월23일(월) 14시56분42초 KST 제 목(Title): 답 이건 정신병자에 대한 답입니다. 이문제는 람지의 정리와 밀접한 관계가 있습니다. 그리고 무져교수란분이 여기에관한 정리를 하나 만든것으로 알고있습니다만 이문제는 불가능합니다. 그 첫번째 이유는 칸수가 너무 작습니다. 보드가 이것보다 더크면 즉 4줄이 아니라 5줄이면 가능합니다. 글쎄 세로로 7줄은 만약 가로로 5줄로 늘어나면 더늘어나야하는지는 확실하지 않군요. 증명법? 논리적 유추를 쓰면 됩니다. 우선 5명이 만약 가로로 2줄에만 있다고 가정하면 반드시 2 + 3 명으로 파티션이 되야하고 그경우 3명은 한줄에 있으니깐 안니다. 그럼 3줄에 있다고 가정하면 1 + 2 + 2 인데 이경우 한줄에 있는 두명은 반드시 서로 옆에 붙어있어야 합니다. 그러면 결론은 2 + 2 는 두명씩 짝을 지어 분포하는걸로 만약 이 두쌍이 최소한 가로로 두줄이상의 간격이 벌어지면 역시 안됩니다. 왜냐면 이건 mod 로 이븐 오드 해보면 쉽게 알수있습니다. 여기서 바로 왜 세로칸수가 7이 나오는지 알수있을것입니다. 만약 8칸이었다면 당연히 되지요. 그런데 또문제는 두쌍이 윗줄 아랫줄 그런식으로 있으면 나머지 한명을 결코 놓을수없습니다. 그러면 결론은 뭐지요? 4줄에 다들어가야 한다는걸로 1 + 1+ 1 + 2 입니다. 그럼 이두명은 옆에 붙어있어야하고 그렇다면 나머지 3명의 포지션만 구하면 됩니다. 그러나 세로에서도 가로에서 적용한 원리가 충분히 다시 어플라이됩니다. 즉 세로에서도 최소한 4줄이상을 써야하고.. 말하자면 체스보드의 8퀸 문제랑 비슷한 스타일의 문제로 전환합니다. 해보면 알겠지만 보드가 너무 작아서 불가능해집니다. 증명법에 대한 대강의 스텝이니깐 나머지는 여러분이 fill in 하겠지요. 논리의 디덕션에 관한 문제였군요. |