| [ QuizWit ] in KIDS 글 쓴 이(By): pomp (위풍당당) 날 짜 (Date): 1997년07월16일(수) 00시00분51초 KDT 제 목(Title): Re: [답] 정사각형 맞추기 우와~ 엄청난 풀이로군요. 감탄, 감탄, 감탄. 이 문제는 Conway의 "prime dissection of squares"의 한 예입니다. 일반적인 문제는, 정사각형을 쪼개되, 작은 정사각형들의 변의 길이들의 최대공약수가 1이 되게 하는 것입니다. 13인 경우는 이런 제한이 있으나마나죠. 일반적인 nxn 정사각형에 대해 필요한 정사각형이 최소 몇 개인가 하는 것은 아직 open problem인 걸로 알고 있습니다. Conway를 비롯한 몇 사람이 그 lower/upper bound를 구한 게 있을 뿐입니다. 몇 개의 n에 대한 풀이가 알려져 있는데, Conway 말로는 41x41에 대한 풀이인 15 개를 찾는 게 아주 어려운 일이라고 하는군요. +---+---+---+---+---+---+---+---+---+---+---+---+---+ | | | + + + | | | + + + | | | + + 6 + | 7 | | + + + | | | + + + | | | + +---+---+---+---+---+---+ | | 1 | | | +---+---+---+---+---+---+---+---+ + 2 + | | | 3 | | + + 2 + +---+---+ | | | | | + +---+---+---+---+---+ 2 + | | | 1 | | + 6 + +---+---+---+ | | | | + + 4 + + | | | 3 | + + + + | | | | +---+---+---+---+---+---+---+---+---+---+---+---+---+ ... & circumstance |