| [ QuizWit ] in KIDS 글 쓴 이(By): guest (guest) 날 짜 (Date): 1997년07월21일(월) 23시36분54초 KDT 제 목(Title): shuffling 만일 p가 m_1,...,m_r의 인수로서 등장하는 최대의 솟수이면, 그리고 만일 p보다 작은 솟수 a,b가 사용되지 않았다면, p = a + b + (p-a-b) 가 되고 p-a-b개의 1을 동원하면 곱은 p대신 ab로 바뀌는데, 따라서 ab>p인 그러한 비어 있는 쌍이 없어야 함. 최대의 솟수가 29 이상이라고 하자. 만일 2가 없다면 3,5,7,11,13,17,19,23이 있어야 함. 분명히 너무 많으니까, 2는 있어야 한다. 3이 없다면, 2,5,7,11,13,17,19,23이 있어야 한다. 역시 너무 많으므로 3도 있어야 한다. ...이런 식으로 11까지의 모든 솟수가 있어야 한다는 것을 보일 수 있다. 그런데 2+3+5+7+11+29=57. 결국 최대의 솟수는 29 이상일 수 없다. 결국 23 이하의 솟수들인 2,3,5,7,11,13,17,19,23 만이 등장한다. 7 이하만이 등장한다면? 2^x3^y5^z7^w에서, w>1일 수 없다. (7^2=49가 되고, 이것은 쉽게 그보다 더 작은 솟수 두개로 자를 수 있다.) z역시 마찬가지이다. 그러므로 5와 7은 기껏해야 하나씩의 인수밖에는 제공하지 못한다. 3에 대해서는 (3^3=27, 3^4>52) y는 2 이하. 2에 대해서는 (2^5>52), 4 이하이다. 가능한 최대값을 모두 곱해도 lcm은 5040밖에는 나오지 않는다. 위의 논의에서 등장하는 솟수는 23 이하이고, 반드시 11 이상의 솟수가 하나는 등장해야 함을 알 수 있다. 23이 최대인 경우를 생각하자. 역시 같은 테크닉으로 기본으로 2,3,5,7이 등장한다는 것을 알 수 있다. 2+3+5+7+23=40이므로 남은 수는 12이다. 11이 있다면 1+2+3+5+7+11+23으로 분해되고 lcm=53130. 11이 없다면 12는 2,3,5,7들의 파워를 올리는 방법으로 해결된다. 5의 파워를 하나 올리면 최소 20이 증가하므로 그럴 수는 없다. 마찬가지로 7의 파워를 올릴 수도 없다. 3의 파워는 하나까지 올릴 수 있고, 2의 파워는 3으로 올릴 수 있다. 이것이 최적이다. 즉, 8+9+5+7+23으로 분해하는 것. lcm=57960. 이것보다 큰 lcm은 쉽게 찾을 수 있다. 19가 최대인 경우를 생각하자. 2,3,5는 역시 같은 테크닉으로 나와야 된다는 것을 보일 수 있다. 7이 없다면 11이 있어야 한다 2+3+5+11+19=40. 12가 남는다. 이것은 2,3,5,11의 파워를 올리는데서 찾아야 한다. 5와 11의 파워를 올릴 방법은 없으므로 역시 앞에서처럼 8+9+5+11+19로 분해해야 한다. lcm=75240. 7이 있는 경우로 넘어가자. 2+3+5+7+19=36. 남은 것은 16이다. 만일 11이 있다면, 남은 것은 5이고, 이것은 앞의 숫자들의 파워를 올려야 한다. 이번에는 3의 파워조차 올릴 수 없다(3이 9가 되면 6이 증가하니까). 결국은 2를 4로 바꾸고 나머지는 1로 처리하는 수밖에 없다. 1+1+1+4+3+5+7+11+19. lcm=87780. 11이 없다고 하자. 13이 있다면, 남는 것은 3인데, 이때는 역시 2를 4로 바꾸고 1을 더하는, 1+4+3+5+7+13+19가 나온다. lcm=103740. 13조차 없다면 16은 2,3,5,7의 파워를 올려서 처리해야 한다. 5와 7의 파워를 올리는 것은 불가능하다. 3의 파워는 2까지 끌어올릴 수 있고, 2의 파워는 4까지 끌어올릴 수 있다. 시행착오를 좀 해 보면, 3대신 9를, 2대신 8을 쓰고 나머지를 1로 처리하는 1+1+1+1+8+9+5+7+19이 최대이다. lcm=47880. 아 귀찮군요. 이런 식으로 노가다를 하면 된다는 것은 분명한데 여기서부터는 컴퓨터를 쓰는 것이 나을 것 같네요. . |