[TMI] Square Packing

Question

한 변의 길이가 1인 단위 정사각형 n개를 더 큰 정사각형 상자 안에 넣으려 합니다. (쌓기 X, 겹침 X, 2D)

이때 정사각형 상자의 한 변의 길이의 최솟값을 n에 따라 구하는게 문제입니다. 어떻게 하면 단위 정사각형 n개를 가장 효율적으로 배치할 수 있는지의 문제죠.

n이 제곱수일 때는 답이 루트(n)임이 자명합니다. n = 3일 때는, 직관적으로 ㄴ자 모양으로 배열한 것이 가장 효율적임을 알 수 있고, 이때의 답은 2입니다. (증명도 가능합니다.)

그럼 n = 17일 때는 어떻게 될까요?

이렇게 하면 될 것 같죠?

아닙니다.

현재까지 발견된 가장 효율적인 배치이고, 그 차이는 아래 그림의 아주 좁은 간격입니다.

아래는 일부의 n값에 대한 최적화 예시입니다.

Proved라고 된 것은 수학적으로 엄밀하게 증명된 것들이고, found는 현재까지 발견된 예시 중 가장 효율적인 것이므로 아직은 최적화 상태가 아닙니다.

.

불연속미분가능 · Accepted Answer

신기하네요...역시 수학은 경이롭다

houmo · Answer

그런데 저런 효율적인 배치는 어떻게 수학으로 찾는건가요? 막 틀어지고 빈틈있고 이런 사소한 부분들이요

최근 게시글 · 더보기