[일반] 퀴즈2(블록쌓기)

[□(112.170)]

p,q,r은 서로 다른 소수이다.

당신은 어쩌다가 가로 p, 세로 q, 높이 r인 나무블록을 엄청 많이 갖게 되었다.

이걸 갖고 뭘 할수 있을까 생각하던 당신은 이 블록을 쌓아서 큰 직육면체를 만들려면 부피가 pqr의 배수여야 한다는 것을 1초 뒤에 깨달았다.

퀴즈 : 역으로 각 변의 길이가 충분히 큰 정수이고 부피가 pqr의 배수인 임의의 직육면체를 저 나무블록들로 쌓을 수 있음을 보여라.

Hint : 2차원부터 생각하면 쉬울지도?

[익명(45.64)]

Case 1. 세 변이 각각 p의 배수, q의 배수, r의 배수라면 자명.

[익명(45.64)]

Case 2. 세 변이 각각 pq의 배수, 적당히 큰 수 L (i.e. (p-1)(q-1) 이상), r의 배수인 경우. 임의의 (p-1)(q-1) 이상의 자연수는 p와 q의 음이 아닌 정수 선형결합 (i.e. 0 이상의 정수 m,n에 대해서 np+mq꼴의 자연수)으로 표현할 수 있으므로, 이를 이용하면 세 변의 길이가 pq, L, r인 직육면체를 나무블록으로 만들어낼 수 있음을 쉽게 확인할 수 있고, 따라서 마찬가지로 해결됨.

[익명(45.64)]

Case 3. 세 변이 각각 pqr의 배수, 적당히 큰 수 L1, L2인 경우 (i.e. L1과 L2는 적당히 편의상 (p-1)(q-1)(r-1) 이상), 윗 댓글의 방식을 이용하면 pqr은 pq의 배수이므로 (1) 세 변의 길이가 pqr, L1, r인 직육면체를 나무블록을 이용해서 만들수 있고, 마찬가지로 pqr은 pr의 배수이므로 (2) 세 변의 길이가 pqr, L1, q인 직육면체를 나무블록을 이용해서 만들수 있음. L2는 (q-1)(r-1) 이상이므로, 마찬가지로 L2를 p와 q의 음이 아닌 정수 선형결합으로 표현가능하므로 따라서 (1)과 (2)를 조합해서 세 변의 길이가 pqr, L1, L2인 직육면체를 나무블록을 사용해서 만들수 있고, 따라서 해결됨.

[□(223.62)]

정답!