퀴즈 325 3 쇼핑몰

스팀시티에 100명의 방문객이 찾아왔다.

그들은 지역 명물인 A,B,C 쇼핑몰에서 기념품을 샀다.

누구든지 반드시 한 곳은 갔고, 제일 많이 간 친구는 2곳을 갔다고 한다.

그러면 적어도 몇 명이 완전히 같은 장소를 방문했는가

이 문제는 쉽게 일반화가 가능하다.

---

풀이

바로 일반화를 해보자. n명의 방문객이 있고, A,B,C 3 곳의 쇼핑몰을 들리며

각 방문객은 적어도 반드시 한 곳을 갔고, 제일 많이 간 방문객은 2곳이라고 할 때,

몇명이 완전히 같은 장소를 방문했는지를 알고 싶다.

[완전히 같은 장소란 말은, 완전히 같은 루트를 택했단 말이 된다. 예를 들어 방문객 1 이 A,B 를 들렸을 때, 완전히 같은 루트란 다른 방문객 역시 A,B 를 선택한 경우를 말한다. ]

자 방문객이 갈 수 있는 모든 경우를 생각해보자. {A,B,C} 를 두고, 해당 지역을 방문 햇으면 1 을 방문하지 않으면 0 을 주자.

가능한 경우의 수는

{1,0,0}, {0,1,0}, {0,0,1} , {1,1,0}, {1,0,1} , {0,1,1}

이렇게 6가지가 된다. 즉 n 명은 적어도 이 6개의 경우 안에 들어가게 된다. [비둘기 집의 원리]

즉 [n/6]+1 만큼 같은 장소를 방문하게 된다.

즉, 100명의 경우 16+1=17 명이 같은 장소를 방문하게 된다.

---

_{Sponsored ( Powered by dclick )}

Steem Hedge Token

^{Get Steem Hedge on the Steem-Engine Market Today!}