| [ QuizWit ] in KIDS 글 쓴 이(By): guest (guest) 날 짜 (Date): 1997년07월15일(화) 21시37분52초 KDT 제 목(Title): [답] 정사각형 맞추기 11개의 솔루션이 있습니다. A A A A A A A B B B B B B A A A A A A A B B B B B B A A A A A A A B B B B B B A A A A A A A B B B B B B A A A A A A A B B B B B B A A A A A A A B B B B B B A A A A A A A C C D D D D E E E E E E F C C D D D D E E E E E E G G G D D D D E E E E E E G G G D D D D E E E E E E G G G H I I I E E E E E E J J K K I I I E E E E E E J J K K I I I 10개짜리가 없다는 것을 보이면 됩니다. 근본적으로는 어떻게 쪼개지는 수밖에 없는지 후보를 적게 추려낸 뒤에 이제 걔내들을 가지고 '직접' 13*13을 맞추는 것을 시도하는 방식인데, 어떻게 쪼개지는지 알아내는데는 컴퓨터의 도움을 받았습니다. 그렇다고 무작정 시도하는 것은 우습고, 이런 사전작업이 가능하죠: 우선, 너무 큰 정사각형을 하나 사용해 버리면, 이제 그 '가장자리'를 메우기 위해서는 작은 정사각형이 많이 필요하게 되기 때문에 정해진 갯수내에 끝낼 수가 없게 됩니다. 쉽게 8개 이상의 정사각형을 사용하면 10개 이내에 끝낼 수 없다는 것을 보일 수 있습니다. 순 case-by-case로 하는 지저분한 증명이지만요. 다음으로, 별 것 아니지만, 어떤 가로줄이 서로 다른 정사각형을 동시에 지나가면, 어떤 세로줄도 그들을 동시에 지나가지 않습니다. 당연하죠? 제곱수들은 4로 나누면 0 또는 1이 됩니다. 근데 169는 4로 나누었을 때 1이기 때문에, 홀수 변을 갖는 정사각형는 1번, 5번, 혹은 9번 쓰일 수 있습니다. 그런데 1번 쓰인다는 것은 말도 안 되지요. 왜냐하면 13보다 작은 사각형을 쓰기 때문에, 어느 가로줄인가는 그 홀수 사각형이 걸쳐있지 않은 곳이 있는데, 여기서는 13을 짝수들의 합으로 나타내야 하기 때문입니다. 이제 9번 쓰이는 경우를 생각합시다. 제곱수는 8로 나누면 0,1,4중 하나이기 때문에, 그리고 169를 8로 나누면 1이기 때문에, 그 짝수 제곱수는 8의 배수여야 합니다. 그런 것에는 0,4,8,12의 제곱이 있습니다. 근데, 위에서 말한 이유로 0 또는 4만 가능하지요. 0인 경우를 생각합시다. 와, 이때는 단 9개의 홀수 정사각형만으로 되는 경우이군요. 이제 어떤 임의의 가로줄이 5개로 메워진다고 가정합시다. 그것을 왼쪽부터 a,b,c,d,e라고 하기로 하죠. 이제 맨 왼쪽의 세로줄은 최소 3개의 홀수 정사각형으로 메워지는데, 이중 하나는 a겠죠? 나머지를 f,g라고 합시다. 이제 맨 오른쪽의 세로줄 역시 비슷하게 e,h,i에 의해 메워집니다. 이 a,b,c,d,e,f,g,h,i는 분명히 서로 다른 9개의 정사각형이므로, 이것이 전부여야 합시다. 이제 a,b,c,d,e는 한 가로줄을 공유하니까, 어떤 최소한 하나의 가로줄은 a,b,c,d,e를 모두 비껴갑니다. 이것을 메우기 위해 동원될 수 있는 사각형은 f,g,h,i뿐, 근데 이중 세 개가 이 가로줄을 덮는 방법은 없죠. 따라서, 임의의 가로줄은 3개의 홀수 정사각형으로 메워져야 합니다. 마찬가지로 임의의 세로줄도 3개의 홀수 정사각형으로 메워져야 하죠. 이것이 불가능하다는 것은 쉽게 해 볼 수 있습니다. 다른 경우는 한 개의 길이 4인 정사각형과, 나머지 9개의 홀수 정사각형으로 메우는 경우인데, 이때는 그 짝수 정사각형을 지나가는 임의의 가로줄에는 이제 9개의 칸이 남고, 이것은 세 개의 홀수 정사각형이 메워야 합니다. 뭐 이런 식으로 또 처음의 짝수 정사각형을 지나는 가로줄도 똑같이 생각하다보면 홀수 정사각형이 차지할 수 있는 위치에 큰 제약을 받게 되는데, 여기서부터는 다시 쉽게 할 수 있다는 핑계를 대도록 하겠습니다. ^_^ 뭐 그래서 홀수 정사각형의 갯수는 정확히 5개여야 합니다. 1,3,5,7중에서요. 또한 짝수 정사각형의 갯수는 5개여야 하는데, 홀수 제곱이 5개면 mod 8로 1이니까, 짝수 정사각형의 넓이의 합은 mod 8로 0이어야 하죠. 따라서 mod 8로 4인 것들, 즉 한 변의 길이가 2,6인 것은 1개, 3개, 5개가 있을 수 있습니다. 즉, {2,6}중에서 각각 1,3,5개를 갖고, {0,4}중에서 각각 4,2,0개를 갖습니다. 여기서 컴퓨터의 힘을 빌려, 홀수 정사각형의 가능한 넓이의 합, 짝수 중 mod 8로 0인 것의 합, mod 8로 4인 것의 합을 계산해 보면, 다음의 것들이 있습니다: (21,0,148),(29,32,108),(45,16,108),(53,0,116),(61,0,108), (61,32,76),(69,64,36),(77,16,76),(85,0,84),(85,48,36), (93,0,76),(93,32,44),(101,32,36),(101,64,4),(109,16,44), (117,0,52),(117,16,36),(117,48,4),(125,0,44),(125,32,12), (133,0,36),(133,32,4),(141,16,12),(149,0,20),(149,16,4), (157,0,12),(165,0,4) 만일 5이거나 7짜리 정사각형이 없다고 합시다. 그럼 홀수 정사각형의 넓이의 합은 5*3^2=45 이하가 됩니다. 그러한 것으로는 3개가 있군요. (21,0,148)은 1+1+1+9+9+4+36+36+36+36에 해당하며, (29,32,108)은 1+1+9+9+9+16+16+36+36+36, (45,16,108)은 9+9+9+9+9+0+16+36+36+36에 해당합니다. 근데 사실 한 가로줄의 길이가 13이기 때문에, 임의의 가로줄에는 최소한 한 개의 홀수 정사각형이 얹혀져 있어야 합니다. 근데 위의 세개 중에서 앞의 두 개는 홀수 정사각형의 변의 총 합이 12 이하이지요. 또한 나머지 역시 길이 6인 정사각형이 3개가 등장하는데, 이것이 실격이라는 것은 분명합니다. 따라서 5, 7중 하나가 반드시 필요합니다. 이제 7이 하나 있다고 합시다. 쉽게 5가 없다는 것을 보일 수 있습니다. (5가 있다면 그 5와 7은 어떤 가로선도 세로선도 공유하지 못하기 때문에). 따라서 1과 3의 갯수의 총합이 4입니다. 1이 3개 3이 1개인 조합은 (61,0,108), (61,32,76)의 두 개가 있습니다. 이들은 각각 49+1+1+1+9+0+0+36+36+36, 49+1+1+1+9+16+16+36+36+4에 해당합니다. 이들은 둘 다 7 하나, 6 2개를 포함하고, 이것은 불가능합니다. 1이 2개 3이 2개인 조합은 (69,64,36)인데, 이것은 49+1+1+9+9+16+16+16+16+36입니다. 1이 1개 3이 3개인 조합은 (77,16,76)이 유일하고, 이것은 49+1+9+9+9+16+0+36+36+4입니다. 이것 역시 7 하나 6 2개를 포함하니까 불가능합니다. 따라서 7이 있는 경우에 가능한 방법은 49+1+1+9+9+16+16+16+16+36 뿐입니다. 이제 7은 없고 5는 있는 경우를 생각합시다. 5가 4개 이상 있을 수 없다는 것은 분명합니다. 5가 3개 있으려면, 가능한 후보는 (77,16,76)과 (85,0,84) 뿐인데, 이들의 경우 6을 포함합니다. 따라서 불가능하죠. 그러므로 5는 기껏해야 2개밖에는 있을 수 없습니다. 5가 2개 있는 경우, (77,16,76)과 (69,64,36), (61,32,76),(61,0,108),(53,0,116)이 가능한데, 이중 6을 2개 포함하지 않은 녀석은 (69,64,36)이 유일하죠. 이것은 25+25+9+9+1+16+16+16+16+36입니다. 마지막으로, 5가 하나 있으려면 홀수 정사각형의 합은 61 이하입니다만, 이중 6이 3개 이상 있는 것을 모두 제외하면 (61,32,76)만이 남습니다. 이것은 25+9+9+9+9+16+16+36+36+4에 해당합니다. 결국, 가능한 모든 경우는, 49+1+1+9+9+16+16+16+16+36과 25+25+9+9+1+16+16+16+16+36, 그리고 25+9+9+9+9+16+16+36+36+4의 세 가지입니다. 이중 마지막의 것은 6을 2개나 포함하고 5를 하나를 포함하므로, 쉽게 불가능하다는 것을 확인할 수 있습니다. 그리고 나머지도 이리저리 해 봐도 잘 안되는군요. ^_^ |