정사각형 채우기

정사각형 채우기는 합동인 정사각형을 더 큰 모양(대개 정사각형이나 원) 안에 얼마나 많이 채울 수 있는지 결정하는 것을 목표로 하는 채우기 문제이다.

 정사각형 안에 정사각형 채우기 
정사각형 안에 정사각형 채우기는 한 변의 길이가 인 더 큰 정사각형 안에 최대 몇 개의 단위정사각형 (변의 길이가 1인 정사각형)을 채울 수 있는지 결정하는 문제이다. 만약 가 정수이면 답은 이지만, 임의의 정수가 아닌 수 에 대한 채워지지 않은 공간의 정확한, 또는 심지어 점근적인 해답을 구하는 문제마저 전부가 해결되진 않은 열린 문제이다.

개의 단위정사각형을 채울 수 있는 큰 정사각형의 한 변의 길이 의 최소값은 이 완전 제곱수일 때 (임), 2, 3, 5, 6, 7, 8, 10, 13, 14, 15, 24, 34, 35, 46, 47, 48일 때 알려져 있다. 이들 대부분의 숫자 (5와 10을 제외하고)에 대해 채우기는 한 축에 정렬된 정사각형을 사용하는 자연스러운 방식이며, 는 인데, 여기서 는 올림 함수이다.
다음 그림은 기울어진 정사각형을 포함하는 최적의 채우기가 필요한 가장 작은 두 수인 5개와 10개 정사각형에 대한 최적 채우기를 보여준다.

가장 작은 수의 미해결 예시는 이다. 11개의 단위정사각형은 보다 작은 변의 길이를 가진 정사각형에 채울 수 없다는 것이 알려져 있다. 이와 대조적으로, 11개의 정사각형에 대해 알려진 가장 조밀한 채우기는 월터 트럼프가 발견한 약 3.877084의 변 길이를 가진 정사각형 안에 있다.2000년 버전의 는 이 변 길이를 3.8772로 기재했다. 여기에 언급된 더 엄격한 하한은 

세 가지 다른 각도의 정사각형을 포함하는 최적의 채우기를 가지는 가장 작은 경우는 이다. 이는 하와이 대학교의 학부생인 존 비드웰이 1998년에 발견했으며, 변의 길이는 이다.

다음은 까지의 값에 대한 최소 해이며, 의 경우는 아직 해결되지 않았다.
단위정사각형 개수 큰 정사각형의 최소 변 길이 1122324252.707...63738393103.707...113.877... ?124

 점근적 결과 

섬네일|upright=0.6|귀퉁이가 잘린 체스판에서 개의 정사각형에 대한 최적 채우기

변 길이 가 더 큰 값일 때,  정사각형을 채울 수 있는 단위정사각형의 정확한 개수는 아직 알려져 있지 않다.
항상 축에 정렬된  단위정사각형 셀을 채울 수 있지만, 이것은 약 의 큰 영역을 덮지 않은 채로 낭비하게 만든다. 대신, 에르되시 팔과 로널드 그레이엄은 기울어진 단위정사각형으로 다른 방식으로 채우면 낭비되는 공간을  (여기서는 작은 o 표기법으로 표기됨)으로 현저히 줄일 수 있음을 보여주었다.
이후, 그레이엄과 판 청은 낭비되는 공간을 로 추가적으로 줄였다.
그러나 클라우스 로스와 밥 본이 증명했듯이, 모든 해는 최소한 의 공간을 낭비해야 한다. 특히, 가 반정수일 때 낭비되는 공간은 최소한 그것의 제곱근에 비례한다. 반정수 변 길이에 대해서도 낭비되는 공간의 정확한 점근적 성장률은 여전히 열린 문제이다.

일부 단위정사각형의 개수는 채우기에서 최적의 개수가 될 수 없다. 특히,
 크기의 정사각형이 개의 단위정사각형을 채울 수 있다면, 이어야 하며
개의 단위정사각형을 채우는 것도 가능하다.

 원 안에 정사각형 채우기 
원 안에 정사각형 채우기는 가능한 한 작은 반지름을 가진 원 안에 n개의 단위정사각형을 채우는 문제이다. 이 문제에 대해서는 n이 35까지의 좋은 해가 알려져 있다. 다음은 까지의 최소 알려진 해이다 (단, 과 의 경우만 최적임이 알려져 있다).

정사각형 개수원의 반지름1234561.688...781.978...910112.214...12

 다른 모양에 채우기 
다른 모양에 정사각형을 채우는 것은 높은 계산 복잡도를 가질 수 있다. 주어진 수의 축과 평행한 단위정사각형이 주어진 다각형에 들어맞는지 테스트하는 것은 NP-완전 문제이다. 이는 단순 다각형 (구멍이 없는)이며 직교 볼록이고, 축에 평행한 변을 가지며, 반정수 꼭짓점 좌표를 가진 경우에도 NP-완전 문제로 남아있다.

 같이 보기 
 정사각형 안에 원 채우기
 정사각형을 정사각형으로 나누기
 직사각형 채우기
 소파 옮기기 문제

 각주 

 외부 링크 

분류:채우기 문제
분류:기하학의 미해결 문제