퀴즈 393 풀이 및 일반화

avatar
(Edited)

퀴즈 393 7개의 방과 10명의 손님


7개의 방이 있는 호텔에 10명의 손님이 찾아왔다. 이 10명 중 어떤 7명을 선택해도 그 사람들이 서로 다른 7개의 방에 들어갈 수 있도록 전체 10명의 사람들에게 열쇠를 나누어 주고 싶다.

이 때 열쇠는 최소 몇개가 필요할까?


풀이

28개, 사실 이 문제에서 28개가 나오는 것은 쉽게 구할 수 있는데, 문제는 이 28개가 최소임을 보이는 것이다. 하나씩 차분히 해보자.

먼저 방이 7개니까 7명에게 각 방 하나씩 열쇠를 주었다고 가정하자. 그리고 남은 3명을 생각해보자. 남은 3명을 어떻게 열쇠를 주어야 이 10명중 임의로 7명을 뽑았을 때 모든 방을 열 수 있을까?

image.png

예를 들어 A에서 6명을 뽑고 B 에서 1명을 뽑았을 때 모든 방의 열쇠를 들어가게 하려면 B 에서 뽑은 그 한명은 7개의 열쇠를 가지고 있어야 한다. 이 3명을 뽑는 경우는 임의의 경우이니까 각각 7개씩 3개 총 B 그룹에는 21개의 열쇠가 들어가게 되고 전체 필요한 열쇠의 갯수는 7+21=28 개가 된다.

최소임을 보이라고 했으니 27개는 이 경우를 만족하지 않는다는 것을 보이면 된다. 자 7개의 방 중 하나를 선택 했을 때, 그 방(편의상 그 방을 x라 하자)의 열쇠를 가진 사람이 많아야 3명인 방이 존재한다. [열쇠의 갯수가 27개이고 이를 7로 나누면 몫이 3이다.] 즉 어떤 특정 방 x 의 열쇠를 가지고 있는 사람은 많아야 3명이다. 그럼 그 방 x 의 열쇠를 가지고 있지 않은 사람은 (10-3=7)명이 되는데 이 경우 이 7명을 뽑았을 때 x 방을 들어가지 못하므로 모순이 생긴다.

즉 27은 불가능하다.

일반화

이 문제를 일반화해보자

m 개의 방이 있고 n 명 (n>m) 의 손님이 있다. 이 때 n 명중 임의의 m 명을 선택해도 그 사람이 서로 다른 m 개의 방에 들어갈 수 있도록 n 명에게 열쇠를 주고 싶을 때 최대, 최소 몇개의 열쇠가 필요할까?

답은 최대는 mn, 최소는 m(n-m+1) 개가 될 것이다.



0
0
0.000
3 comments
avatar
(Edited)

이렇게 어려운 문제 말고 넌센스도 좀 내주세요. 수포자들 생각해서.... ㅋㅋ

0
0
0.000
avatar

Congratulations @beoped! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

You published a post every day of the week

You can view your badges on your Steem Board and compare to others on the Steem Ranking
If you no longer want to receive notifications, reply to this comment with the word STOP

To support your work, I also upvoted your post!

Do not miss the last post from @steemitboard:

SteemFest⁴ - Meet the Steemians Contest
Vote for @Steemitboard as a witness to get one more award and increased upvotes!
0
0
0.000
avatar

Hi @beoped!

Your post was upvoted by @steem-ua, new Steem dApp, using UserAuthority for algorithmic post curation!
Your UA account score is currently 3.734 which ranks you at #5471 across all Steem accounts.
Your rank has not changed in the last three days.

In our last Algorithmic Curation Round, consisting of 82 contributions, your post is ranked at #52.

Evaluation of your UA score:
  • You're on the right track, try to gather more followers.
  • The readers like your work!
  • Try to work on user engagement: the more people that interact with you via the comments, the higher your UA score!

Feel free to join our @steem-ua Discord server

0
0
0.000