| [ QuizWit ] in KIDS 글 쓴 이(By): constell (꺽달이) 날 짜 (Date): 1995년07월11일(화) 02시22분30초 KDT 제 목(Title): 물통 문제의 일반해.. 이건 고등학교 수준의 부정방정식 풀이인데요... ax + by = c, a, b, c 는 상수(정수)라고 하죠. 등식을 만족하는 정수 x, y를 찾는 겁니다. a, b가 mutually relatively prime이면 해 (x, y)가 반드시 존재한다는 건 직관적으로 이해가 가시죠? c = 1인 경우를 생각해 보세요. a, b에다 적당히 몇배씩 하면 합이 1이 되게 만들 수 있잖아요. 그럼 c배만 해 주면 ax + by = c가 되겠죠. 만약 a, b의 GCD가 1보다 크다면? 그럼 c가 그 GCD의 multiple이면 당연 만족되고.. 아니면 불가능한 거죠. 왜 불가능하냐구요? ax + by를 GCD로 나누어 주면 앞에서 말한 것같이 합이 임의의 정수가 되게 할 수 있죠.. (정수가 아닐 수는 없죠?) 거기다 GCD만큼 곱해야 ax + by가 되니까 이건 당연히 GCD의 multiple이죠. 그러니까 불가능..~ 아, 그리고 만약 해가 존재한다면 무한히 많은 해가 존재한다는 것도 당연하죠? 그러니까.. a, b가 두 물통의 크기라 하고, c가 원하는 물의 양이라고 하면 x, y는 우리가 각 물통에 물을 총 몇번 (완전히 빈 것을)꽉 채우느냐(음이면 꽉 채워진 걸 버리느냐)를 뜻하게 되는 것이죠... 문제에서 주어진 5, 3, 4를 볼까요... 5x + 3y = 4 => (x, y) = (-1, 3), (2, -2), ... generally, (x, y) = (3k - 1, -5k + 3), k, l은 정수 자.. 그럼 이중 어느 해를 골라도 4L를 채우는 process에 unique하게 대응시킬 수 있습니다. (-1, 3)의 해를 보면... 가득찬 5L 통의 물을 모두 쏟아내기 한 번, 텅빈 3L 통에 물을 가득채우기 한 번. 을 해야겠죠.. 일단 채우는 것밖에 할 수가 없으니까.. 1) 3L 통에 가득 채운다. 음.. 그러고 보니 할일이 없네요. 3L 통을 버릴 수는 없고. 2) 3L 통의 물을 5L에 몽땅... 5L 통이 가득차지 않았으니 쏟아버릴 수는 없고.. 아, 3L 통이 비었네. 3) 3L 통에 가득 채운다. 또 할일이 없잖아.. 할일이 없을 땐 2)와 같이 옮겨붓는다~ 4) 3L 통의 물을 부어 5L 통을 가득 채운다. (이제 5L, 1L 있음) 이제 할 일이 생겼으니.. 5L 통의 물을 몽땅 쏟아내죠. 5) 5L 통의 물을 모두 쏟아낸다. 음.. 3L 통을 채워야 하는데 이 통이 아직 비어 있지 않죠? 6) 3L 통의 1L 물을 5L 통에 모두 붓는다. 와.. 이제 3L 통에 물을 부을 수가 있게 됐네요... 7) 3L 통에 물을 가득 채운다. 이제.. 5L 통에 1L, 3L 통에 3L니까 합이 4L... 보니까 이건 뫼비우스님의 해와 같군요.(각 물통에 물이 0=>full, full=>0이 되는 수를 세 보면.) 그리구.. 저 위에서 (2, -2)의 해도 있었죠? 이건 저 위의 ziba님의 해이군요. 그리고 무한히 많은 해를 만들 수가 있지요.. 물론, 수백번씩 물을 붓고 버리는 건 바보같은 일이니까 아무도 이렇게는 안 하겠지만 :) .. (3k - 1, -5k + 3) = ..., (-4, 8), (-1, 3), (2, -2), (5, -7), ... 두 해 외에는 그 작업의 수가 12회 이상이 되니까 선뜻 생각하기 어렵겠죠.. :) 매우매우 rough하게 설명을 했지만..(원래 전 이런 설명을 더 좋아하거든요 :>) 아무튼 이런 식으로 하면 임의의 해에 대해 process를 대응시킬 수가 있지요. 그리고 이게 항상 가능합니다.. 음, 그리고 물통이 여러개라도(term의 수만 늘어나겠죠..) 마찬가지로 풀 수 있어요. // 꺽달, KAIST, 94. |