[대학교이상] 비둘기집원리 질문입니다

[익명(115.21)]

Show that whenever 25 girls and 25 boys are seated around a circular table there is always a person both of whose neighbors are boys.

이 문제이고 사진이 해설인데

잘 이해가 안 갑니다.. 비둘기집 원리는 어디서 쓰인건지 모르겠습니다

- dc official App

[익명(61.81)]

홀수번호가 적힌 자리25개에 13명을 앉게하면 적어도 두명은 연속된 홀수번호를 가진다는거 여기에 비둘기집 쓰였음 - dc App

[익명(116.41)]

[25/13]=2이라서 그런건가? 근데 이거면 상자가 사람이란건데 비둘기집원리 그대로 따라가면 적어도 한명은 2개의 홀수번호를 가진다로 되버리는데 - dc App

[익명(61.81)]

사람이 비둘기고 의자가 상자임 연속된 홀수번호를 가지지 않는다고 가정하면 50이하의 홀수에대해 적어도 13명의 학생이 앉기위해 간격이 2보다 크게 이루어진 홀수가 필요한데 50이하에서 그걸 구성하면 mod4에 대해 1과 합동인 수가 필요하고 50이하에는 총 12개가 존재하지 그럼 12명까지는 연속된 홀수번호를 가지지않게 앉을수있지만 - dc App

[익명(61.81)]

나머지 한명은 앉을 자리가 없게되니까 적어도 두명은 연속된 홀수번호를 가지는거지 - dc App

[익명(116.41)]

내가 알던 비둘기집 원리는 상자 하나에 비둘기가 몇개 이상 들어간다로 아는데 여기선 왜 비둘기인 사람이 상자에 해당하는 의자 하나가 아닌 두개에 들어가는거지..? 뭔가 왜 비둘기집원리가 쓰인건지 낯선데 - dc App

[익명(61.81)]

한 의자에 2명이 앉는게 아니라 번호가 연속되게 두자리에 두명이 앉는다고 - dc App

[익명(116.41)]

그런 결과가 비둘기집에서 나올 수 있었나..? 정의랑은 다른데 - dc App

[익명(61.81)]

비둘기집이 꼭 어딘가에 누가들어갈때 2명이 들어가는집이 생긴다는게 아니라 마지막 1명은 어쩔수없이 기존의 사람이랑 중복되는 성질을 가진다는거지 예를들면 1월에 생일인 사람이 32명있으면 1월은 31일까지니까 적어도 2명은 생일이 겹치는것처럼 - dc App

[익명(116.41)]

근데 애초에 여기서 사람이 비둘기면 보통 비둘기가 상자보다 많은경우에서 발생하는데 이건 비둘기가 상자보다 적은데..? - dc App

[익명(116.41)]

그리고 첫항 1 공차 4인 등차수열 생각해보면 50이하로 13개 나오는데.. - dc App

[익명(211.36)]

1번자리랑 50번이랑 붙어있으니까 초항1 공차4등차수열로 생기는 49번에 앉히면 이미 1번이랑 연속된 홀수번호잖아 그리고 비둘기집역할을 하는 의자는 mod4에대해 1하고 합동인 홀수번호의 의자만 가지고 하는거 그럼 너말대로 13개인데 13군데 다 앉히면 49번이랑 1번사이에 앉은애는 남자애들 사이에 앉는거지 - dc App

[익명(116.41)]

아..무슨말인지는 이해했다. 근데 mod4의 경우만 보여도 되나..? 간격이 2보다 큰 앉는 경우는 여러가지인데..물론 2 다음으론 4이긴 하지만 - dc App

[익명(116.41)]

mod4의 경우 외에는 trivial하게 연속되게 앉는다는걸 알아야 안 보여도 되는거아닌가..? - dc App

[익명(61.81)]

연속된 홀수번호를 가지는지가 논점이니까 만약 가지지 않게 앉는다면 가장 촘촘하게 앉는경우만 생각하면되서 mod4인 경우만 보면될듯 - dc App

[익명(175.223)]

"일반성을 잃지않고 ~ 가정하자" 에서 이걸 가정할 수 있는 이유가 비둘기집 원리 때문임. 25명의 남자가 있고 그들 모두를 홀, 짝이라는 비둘기집에 넣으면 어느 한 집에는 비둘기집 원리에 의해 13명이상이 들어가있겠지

[익명(175.223)]

그리고 윗댓이 단 것처럼 이 13명중 적어도 두명이 연속된 홀수번호를 가진다 것의 이유로 비둘기집 원리가 또 다시 쓰였음 13명의 남자간에 이웃한 두명의 남자의 거리를 각각 a_1, a_2, ... , a_13이라하면

[익명(175.223)]

a_1 + a_2 + ... + a_13 = 50 이니까 이 변수들중 적어도 하나는 비둘기집 원리에 의해 3이하여야하는데 남자들이 모두 홀수번호(일반성을 잃지 않고서 라고 했는데 사실 이 말은 남자들이 짝수번호를 가져도 같은 증명을 댈 수 있다고 보면됨)위에 있으니 a_i들은 모두 짝수이고 따라서 a_i = 2 인 i가 있으며

[익명(175.223)]

이는 거리가 2인 두 남자가 있음을, 다시 말하면 그 사이에 있는 사람은 양옆에 남자 두명을 끼고 앉아 있게 되면서 문제가 말하는 게 성립함을 보여주고 있음

[익명(116.41)]

비둘기집 원리에 의해 변수들 중 하나가 3이하인건 어떻게 나온거지..? - dc App

[그뀨(minkukaa)]

1~49까지의 홀수 25개 중에서, 어떤 두 수도 연속하지 않게 홀수 n개를 선택할 때 n은 13이하임.. 13일때와 12이하일때로 나눠서 상각하면, 13일때는 1과 49가 연속하는 홀수라고 보면 제외해야 하는 경우고, 12이하일때는 13명의 남자들을 거기다 한 명 씩 앉히면 한 명 이상의 사람이 남음(비둘기집 원리)...

[그뀨(minkukaa)]

남은 한 명 이상의 남자랑 나머지 열두명의 남자, 총 13명 이상의 남자들을 1~50까지의 짝수에서 같은 방법으로 앉히면 한 명 이상의 사람이 남음

[그뀨(minkukaa)]

결국 남자가 앉을수 있는 자리를 최대한 많이 선택하려면 연속하지않은 홀수, 연속하지 않은 짝수들을 최대한 많이 선택해야하는데 최대 24자린데 남자는 25명이라 어떤 자리에는 두명 이상의 남자가 앉게됨

[그뀨(minkukaa)]

그럼 다 한명이 될때까지 자리에서 빼내면 한 명 이상의 남자가 빠져나오겠지? 걔는 이제 앉을수가없음 ;;