폴리매스

슬기로운 수학생활 20번

책상 위의 점

문제 출제자 : 백진언 미시간 대학교 수학과 박사과정생

===========================================================================================

* 수정사항 알림(2022.04.08)

마지막 문단 중 

그렇다면 이 배치를 무작위로 둘 때 한 점이 덮힐 확률은 약 9.31%일 것이다.

=> 그렇다면 이 배치를 무작위로 둘 때 한 점이 덮이지 않을 확률은 약 9.31%일 것이다.

===========================================================================================

책상 위에 점이 N개 찍혀 있다. 반지름 1인 동전들을 서로 겹치지 않게 올려서 모든 N개 점들을 덮으려고 한다. 편의상 책상이 충분히 넓고, 동전의 갯수는 제한이 없다고 가정해서 아래의 문제를 풀어보자.

문제1. 어떤 점들의 배치에 대해서도 동전으로 항상 덮을 수 있는 점의 갯수 N은 얼마일까? 이를테면 N=1이면 점이 한 개 밖에 없으니까 동전 하나로 아무렇게나 덮을 수 있다. N=2일 땐 경우를 조금 나눠야 하지만 동전 두개를 두 점의 중점에 대칭되게 잡으면 덮는 방법이 존재한다. N의 값이 클 수록 더 좋은 답이 된다. 서로 아이디어를 공유해서 더 큰 N에 대해 항상 점들을 덮을 수 있음을 증명해보자.

문제2. 동전들로 덮을 수 없는 특정한 N개 점 배치가 있는 N의 값은 무엇일까? N의 값이 작을 수록 더 좋은 답이 된다. 충분히 큰 N부터 먼저 증명하고, 그 다음 아이디어를 공유해 함께 이 N의 값을 낮춰보자.

‘문제1’의 최대 가능한 답 즉, 덮여지는 점들의 최대 갯수와 ‘문제2’의 최소 가능한 답 즉, 안 덮여지는 점들의 최소 갯수는 딱 1차이가 날 것이다. 다 같이 협력해 ‘문제1’의 답과 ‘문제2’의 답 사이의 차이를 최대한 줄여보자!

백진언 연구원의 팁

‘문제1’에 대해선 다음 방법이 가능하다. 동전 하나를 책상 위에 무작위 위치로 놓자. 두 번째 동전을 첫 번째 동전의 정확히 오른쪽에 접하게 두고, 나머지 동전들은 서로 각도가 60도가 되게 두어 책상 위를 꽉 채우자. 이때 점 하나가 동전으로 덮힐 확률은 얼마일까? 모든 점이 동전으로 덮히는 확률이 양수가 되는 n을 찾아보자.

백진언 연구원의 두 번째 팁

여러분께서 너무 어려워하는 것 같아서 두 번째 힌트를 요청했습니다. 힌트는 아래와 같습니다. 

그림처럼 무한개의 동전으로 책상을 꽉 채우는 배치를 생각하자. 이 배치는 평면의 약 90.69%를 차지한다. 그렇다면 이 배치를 무작위로 둘 때 한 점이 덮이지 않을 확률은 약 9.31%일 것이다 (여기서 사실 '무작위'의 의미가 무엇인지 확실히 해야 하는데, 이는 독자 여러분께 맡기겠다). 이제 n개의 점을 아무렇게나 잡자. 이 배치를 무작위로 둘 때 모든 n개 점이 모두 덮힐 확률은 얼마일까? 확률값이 정확히 얼마인지는 몰라도, 만약 0보다 크다면 어떤 배치 하나는 모든 n개 점을 덮을 것이다.