임의의 양의 정수 N, M, L에 대하여, 각 변의 길이가 N, M, L로 주어진 직육면체 모양의 무가 있다. 이 무를 각 변의 길이가 1인 정육면체 모양으로 자르고 싶다.(한번 자른 것을 겹쳐서 다시 자르는 것을 허용한다.)
1. 주어진 N, M, L에 대해 자르는 방법 중, 칼질을 가장 적게 하는 경우를 공식으로 표현할 수 있는가?
2. 만약 1이 불가능하다면, N, M, L에 적당한 조건을 주는 경우에는 가능한가?
이 문제를 해결하면, 깍뚜기 담글때 효율적으로 써는 방법을 찾아낼 수 있다.
특수한 경우의 예로, N=M=L=1인 경우, 0번의 칼질로 해결된다.
N=M=1, L=2인 경우 1번의 칼질로 해결된다.
…등등.
그래서 2가 밑인 로그식으로 정리되고
칼질에 대해 줄어드는 변량이 한 축이므로 칼질는 횟수를 더하게 된다.
그 같은 식의 총 합이 공식설정 됨.
그래서 2가 밑인 로그식으로 정리되고
칼질에 대해 줄어드는 변량이 한 축이므로 칼질는 횟수를 더하게 된다.
그 같은 식의 총 합이 공식설정 됨.
1. [log2 ([L-1][M-1][N-1])]+3
[X]=x이하의 최대의 정수.
L M N 은 2이상의 실수.
또는 분해하여 [log2 ([L-1])+1]+[log2([M-1])+1]+[log2 ([N-1])+1]
2는 1해결.
칼 자르기는 문제 조건에 의해 한 좌표방향의 길이와 수직, 나머지 두 방향은 평행
그러므로 절단의 기여는 한 방향의 길이만 줄어듬. 길이가 자연수이므로 절단 길이의 최대는 변수의 절반 이하의 자연수. 겹치고 절단이 허용되므로 가장 길게 자르는 것이 최소 횟수. 즉 2진수로 해결가능
ex. 7은 3과4. 겹치고 1 2 2 2로 자르고 나머지 2 2 2를 1 6개로
한 길이가 31이면 16 15. 8 8 8 7만들고 4 4 4 4 4 4 4 3. 그다음 2 15개와 1하나. 2는 1 1 로 마무리.
32인경우 16 8 4 2 1 ? 절단.
33인경우 17 16 같은방법으로 위 공식과 같이 확인됨.
자연수가 아닌 수는 좀 못생긴 깍두기.
증명은 언젠가 해보죠 머 ㅋㅋ
이런 어처구니 없는 실수를!
최대공약수죠, 하하 ^^;;
재밌는 문제입니다.
제 생각에 최소공약수를 구하는 방법대로 자른 다음 짝수 자르기를 한 뒤에 체 거르기(m을 m+1 위에 놓고 쑥덕)를 하고 나면 쉽게 깍두기를 먹을 수 있지 않을까 하는(…) 느낌이 드네요. 뭐, 제가 증명에는 일가견이 있지 않아 모 과목들은 패스해 버렸지만(미적분 따위!) 한번 해 보심이 ^^
이렇게 해 보니 6, 8, 10의 무는 10번 걸리네요. 그런데 써 놓고 보니 저 체 거르기라는 용어가 상당히 거슬리는(…) 그럼 이만 총총.
1번이 가능할 것 같기는 한데…. 귀찮…^^; (이라고 하면 거짓말이고 어렵네요. 하지만 가능할 것 같기는 해요.)
M=2^m, N=2^n, L=2^l`(1과의 구분을 위해서..),(M≥N≥L)이라 하면 한 번에 자르는 면적이 최대가 되기 위해서 길이가 M인 모서리를 지면에 수직하게 세워놓고 자르는 면과 길이가 N인 면이 평행하게 자르는 것을 반복하면 한 모서리의 길이가 M,N,1인 직육면체가 (L-1)개 나오고이 과정에서의 필요한 최소한의 칼질은 총(1`)번이 필요하구요(정확히 반으로 자른 후 이 두 직육면체를 지면에 수직하게 겹쳐 다시 절반으로 자르는 것을 반복하면)이 잘려 생긴 직육면체들을 높이가 M 되도록 겹쳐서 세워놓고 자르는 면과 길이가 L인 면을 평행하게 놓고 자르고 자른 것을 겹쳐서 자르는 것을 반복하면 이 과정에서 필요한 칼질은 n번이네요. 이 과정이 끝나면 M,1,1의 직육면체가 (L-1)x(N-1)개가 나오고 다시 앞의 과정을 반복하면 자르는 횟수는 m번이 되면서 (L-1)x(N-1)x(M-1)개의 정육면체가 나오는데 칼질을 모두 더하면 m+n+l`인데.. 이건 어떻게 자르던 자르는 방법만 동일하게 유지하면 칼질의 횟수는 일정하네요.. 앞의 조건이 너무 많아서 그런듯싶네요.. 다시 풀어보고싶은데….학교가 웬수죠ㅋㅋㅋㅋㅋㅋㅋㅋㅋ좋은해법이 있기를……
좋은 해법 부탁드립니다. 🙂
심심할때 푸세요~
계속 문제를 보다보니까 생각이 났는데 M,N,L중에 하나가 2의 제곱수라면 뭔가 실마리를 잡기에 편리해질 것 같은데요 길이가 2의 제곱수인 면을 보이게 세워놓고 그 면을 자르는 면과 평행하게 해서 딱 반으로 자르고, 그거를 위아래고 겹쳐서 다시 딱 반으로 자르고, 반복하면 1,M,L의 직육면체가 (N-1)개 나오니까.. 여기서부터 시작하면 완전 대책없어 보이던 게 약간이나마 희망이 보이는듯 싶기도…ㅎㅎ
그래서 2번 문제가 있는 겁니다. 🙂
일단 M,N,L 을 상수로 보면 어떻게 자르던 결과는 부피가 1인 정육면체가 일정 갯수 나오게 되어있으니까, 곧 칼질을 다한 후에 칼질로 인해 잘라진 면적은 일정한데 자르는 방향과 평행향 쪽의 길이가 길어야 한번에 짜르는 면적이 넓어지는걸 생각하면 지면에 수직하게 세웠을 때 높이가 가장 길게 만든 후에 자르는 것으을 반복하면 될 것 같은데 이걸 어떻게 공식으로 만들죠… 음…-_-;;; 이게 공식으로 만드는게 가능할까요 경우의 수가 심각하게 복잡해질 것 같은데.. 자르고 나서 생기는 직육면체의 모양이 너무나 다양해져서 ..
아.. 지나가다 들른 물리학도지망생1人이요..