이건노 [thisknow] 13-05-09 15:24

 

878687858786878 이 가장 큰 수가 되네요. 15자리 수 이군요.

* 2 와 8 은 동일한 역할을 한다.
* 소인수는 2, 3, 5, 7 만 고려하면 된다.
* 비둘기집의 원리를 이용하여 15자리를 넘을 수 없음을 설명한다.
* 해밀턴 경로를 이용하여 15자리 최대 자연수를 찾는다.

정원용 [areekaree] 13-05-13 21:47

 

조금만 더 자세히 설명해주세요.

정원용 [areekaree] 13-07-01 20:02

 

이건노님

다시 한 번 조금만 더 자세히 설명부탁드립니다.

이건노 [thisknow] 13-07-13 13:15

 

몇 달에 한 번 가끔 들리는지라 댓글을 못봤네요.

*  2 와 8 은 동일한 역할을 한다.

8 과 2 는 4배차이 이므로 제곱수 차이입니다. 따라서 8 자리에 2 가 있으나, 2 자리에 8 이 있으나
마찬가지입니다. 즉, 큰 자연수를 만드는 것이 목적이므로 2 를 사용하지 않고 8 만 쓰는 것이 좋습니다.
즉, 자연수를 만들 때 사용해야 하는 수는 3, 5, 6, 7, 8 이 됩니다.

* 소인수는 2, 3, 5, 7 만 고려하면 된다.

3, 5, 6, 7, 8 을 사용하여 곱한 수는 소인수분해 했을 때 소인수가 2, 3, 5, 7 만 나옵니다.
따라서 연속된 몇 자리 수를 곱해서 만든 수는 ( 2 ^ s ) × ( 3 ^ t ) × ( 5 ^ u ) × ( 7 ^ v ) 의 형태입니다.
여기에서 s, t, u, v 는 모두 음이 아닌 정수입니다.

* 비둘기집의 원리를 이용하여 15자리를 넘을 수 없음을 설명한다.

자연수가 십진법으로 ABCDEFG 라고 해 봅시다. 이 때, 7 개의 수의 곱
A, A×B, A×B×C, A×B×C×D, A×B×C×D×E, A×B×C×D×E×F, A×B×C×D×E×F×G
에는 소인수분해 했을 때 s, t, u, v 값이 서로 홀짝이 같은 것이 없어야 하고, 모두 짝수이어도 안됩니다.
예를 들어, A×B×C 와 A×B×C×D×E×F 의 s, t, u, v 값이 서로 홀짝이 같으면,
D×E×F 가 제곱수가 되어버립니다.
s, t, u, v 값이 서로 홀짝이 다른 쌍의 개수는 총 16가지 이므로, 모두 짝수인 것을 제외하면 15가지이죠.
즉, 자연수가 16자리 이상이면, 비둘기집의 원리에 의해 s, t, u, v 값이 서로 홀짝이 같은 것이
반드시 존재하게 되고, 문제의 조건을 충족시킬 수 없게 됩니다.

* 해밀턴 경로를 이용하여 15자리 최대 자연수를 찾는다.

맨 앞자리에 오는 수는 8 일 것이고, 이 때 (s,t,u,v)=(홀,짝,짝,짝)입니다.
두 번째 자리는 8이면 8×8 이 (s,t,u,v)=(짝,짝,짝,짝)이 되므로 안됩니다. 따라서 7을 넣습니다.
이 때, 8×7 은 (s,t,u,v)=(홀,짝,짝,홀)이 됩니다.
이와 같이 s, t, u, v 의 홀짝쌍이 같아지거나 모두 짝이 되지 않도록 숫자를 채워가면 되는데,
해밀턴 경로는 설명이 어려우므로 생략하겠습니다.