[11월의 퍼즐] 해파리 가족의 힐베르트 호텔 바캉스

이번 문제는 특정 출처로부터 영감을 받아 만들어졌다. 스포일러 방지를 위해 그 출처는 해설에 공개하기로 하고, 지금은 아래 대화풍의 문제를 바로 만나보자.

컨시어지: 힐베르트 호텔에 오신 걸 환영합니다. 어떻게 도와드릴까요?

해파리: 먼저 저희 가족부터 소개해야겠네요, 저희는 단일한 선조로부터 출아법을 거듭해 태어났습니다. 모두 똑같이 생겼지만, 다행히 가족 전체가 수학을 연구한 덕에 규칙에 따라 번호를 붙여 서로를 구분하고 있습니다. 최초의 선조는 1번입니다. 1번의 j번째 자손은 1-j번이 되고, 1-j번의 k번째 자손은 1-j-k번이 되는, 그런 규칙입니다. 물론 쌍둥이는 없습니다.

컨시어지: 혹시 무한 수열을 번호로 갖는 분들이 무한히 계신지요? 저희 힐베르트 호텔은 무한히 많은 자연수 객실이 있지만, 경우에 따라 호텔에 방이 부족할 수 있습니다.

해파리: 아, 저희 인원은 유한합니다. 모두 유한 수열을 번호로 가지고 있구요. 문제는 따로 있어요. 저희 가족은 특별한 수학적 풍습이 있습니다.

두 해파리가 직계관계일 경우 머무는 객실 번호끼리 2 이상의 공약수가 있어야 해요. 반대로 방계일 경우 객실 번호끼리 서로소 관계여야 합니다.

인원이 상당히 많은데, 전부 1인실을 쓸 수 있을까요?

컨시어지: (잠시 생각한 다음) 조건에 맞게 배정 가능합니다. 마침 모든 방이 비어있으니 제 요청에 따라 움직여주시면 감사하겠습니다.

컨시어지가 생각한 방법은 무엇일까?

보너스 문제 (어려운 버전)
해파리 가족의 풍습이 위와 반대였다고 가정하자. 즉,
–두 해파리가 직계관계일 경우 머무는 객실 번호끼리 서로소 관계여야 한다.
–두 해파리가 방계관계일 경우 머무는 객실 번호끼리 2 이상의 공약수가 있어야 한다.
이 경우에도 컨시어지는 조건에 맞게 방을 배정할 수 있을까?