| [ QuizWit ] in KIDS 글 쓴 이(By): BEAR (곰탱이) 날 짜 (Date): 1998년 5월 15일 금요일 오전 01시 15분 50초 제 목(Title): Re: [문제] 도미노 덮기 성립합니다. 증명 : 만일 역이 성립하지 않으려면 ab = k*n 이 되는 n의 배수가 아닌 a, b가 있어야 합니다. 그림으로 보면 다음과 같은데 <------ b ------> ^ +---------------+ | + + | + + a + + | + + | + + v +---------------+ 이를 조금 변형해서 b를 b'로 조금 키워봅니다. 다음과 같이 <-------- b' -------> 여기서 b'는 b보다 큰 n 배수 중 제일 <------ b ------> 작은 수로 택합니다. ^ +---------------+---+ | + . + | + . + a + . + | + . + | + . + v +---------------+---+ 그리고는 각 cell에 번호를 붙입니다. 다음과 같이.. <-------- b' -------> 즉, 1 부터 n까지 반복해서 쓰는데 ^ +---------------+---+ 각 row마다 하나씩 left shift를 하는 거죠. | +12..n12..n .. 12..n+ | +2..n12..n .. 12..n1+ a +3.n12..n .. 12..n12+ | + ....... + | + + v +---------------+---+ 이제 원래의 보드에서 추가된 부분에 각 숫자들이 몇 개씩 쓰여있는가를 봅시다. b' - b = c 라 하면 c 는 1 <= c < n 이겠죠. 그리고 추가 부분의 크기는 a*c 이고 a mod n = d 라 하면 추가 부분의 (아래 부분)모습은 다음과 같습니다. | 이 부분에 쓰여진 숫자는 c | 1 : d 개 +-----+ 2 : d 개 +12..c+ ... +23 + c : d 개 d +. + (c+1) : (d-1) 개 +. + (c+2) : (d-2) 개 +d + ... -----------------+-----+ d : 1 개 가 됩니다. 자 그럼... 원래 보드에는 몇 개 씩의 숫자가 있을까요. 정확히 안 해봐도 다 똑같지는 않다는 걸 알 수 있죠. 하지만 1xn 도미노는 원래 보드에서 어떻게 배치해도 하나씩의 숫자를 덮으니까, 다 덮히도록 하는 것은 불가능하다는 것을 갈 수 있습니다. 그러므로 앞에서 가정한 a, b 는 존재하지 않습니다. 증명 끝. 이 증명은 원래 1x2 도미노와 체스판 문제 증명의 확장 정도? o- /\/\ ------------------------------------------------------------------- |\/\/ / \/ Kyongil Yoon E-mail: kiyoon@cs.umd.edu / _.__0/ Dept of Computer Science Tel: 301-422-3505(H) 301-405-2715(O) __/ \_// U. of MD at College Park 3429 Tulane Dr. #12, Hyattsville, MD 20783 |