[일반] 비둘기집 원리 문제하나 질문

[ScARfaC..(kayuaao)]

"30명의 남자와 50명의 여자가 일렬로 서있는데 이때 순서가 3 또는 6 차이가 나는 남자 두 명이 존재함을 보여라"

이 문제를 푸는데 a_i를 남자 여자들을 일렬로 세울때 i번째 남자의 순서로 두고 이제 대응관계를 찾아봐야지 하고 찾아보는데 뭔 대응관계를 줘야하는지 a_i-a_j=3또는6인걸 뭐 어떻게 이용해줘야하는지 모르겠음 걍 여기서 제대로 막힘;

일단은 여자들 사이의 공간에 남자들을 대응시키는걸 생각해봤는데 이건 아닌거같음

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[ScARfaCE(kayuaao)]

왜 갑자기 27×3을 생각해주는거야?

[ScARfaCE(kayuaao)]

다른건 다 이해가 가는데 갑자기 27×3이 나오는 이유를 모르겠음

[ScARfaCE(kayuaao)]

i+3,i+6엔 남자가 존재안한다고 가정했으니 (남,여,여),(여,남,여),(여,여,남)이런 (i,i+3,i+6)이라는 순서쌍들이 존재하고 각각 27가지의 경우가 있으니 총 27×3가지의 저런 순서쌍이 존재한단소리니까? 총 순서쌍의 갯수는 원래 각 i에 대해 순서쌍이 존재해야해서 80은 넘을수없는데 그 갯수를 넘어버리니 모순이다? 그래서 남,여,여 같은

[ScARfaCE(kayuaao)]

순서쌍은 존재 못하니 적어도 두 성분에 남자가 있는 i,i+3,i+6라는 순서쌍이 존재한다?

[ScARfaCE(kayuaao)]

첫자리는 왜 남자로 고정되는거야? 상관없지않나?

[ScARfaCE(kayuaao)]

아 남자가 원래 i에 있다고 했었지

[ScARfaCE(kayuaao)]

근데 그러면 27×3인게 더 이해가 안가는데 왜 하필 3을 곱해야해? 분명 뭔가 갯수를 세다보니 저리 나온거같긴한데 좀 뜬금없는거같애

[익명(2.222)]

남자가 i번째에 있을때 (i, i+3, i+6)이 (남,여,여)인 경우 이 (남,여,여)들이 서로 겹칠수 없기 때문에 그럼.

[익명(2.222)]

거의 같은 풀이지만 아래와 같이 생각해도 됨. 1~80 숫자들 중에서 mod 3 기준으로 나머지 0인 숫자들은 26개, 나머지 1인 숫자들은 27개, 나머지 2인 숫자들은 26개임. 예를 들어서 나머지 0인 애들은 3, 6, 9, ... , 78이고 이 위치에 있는 애들만 따로 떼어서 고려했을때, i번째 자리에 남자가 나오면 그 뒤 2개의 i+3, i+6번째 자리에는 무조건 여자, 여자가 나와야함.

[ScARfaCE(kayuaao)]

그니까 저 순서쌍들의 각 자리는 서로 독립적이니 a_i에 대해 27가지의 경우가 생기니 27×3?

[익명(2.222)]

일단 남자가 30명이기 때문에, 비둘기집의 원리에 의해서 얘네들 중 적어도 10명 이상은 mod 3 하에서 같은 나머지를 가지게 됨. 그 나머지를 k라 하자. (k는 0,1,2 중 하나). 위 댓글에서 말했듯 1~80 중에서 나머지가 k인 숫자는 많아야 27개임. 이제 이 27개의 자리에 10명의 남자를 배치해야 하는데, 남자가 두번 연속해서 나오게끔 배치해서는 안되고 남 여 남처럼 2칸 띄워서 배치해서도 안됨. 두 인접한 남자 사이에 거리는 항상 3 이상이 되어야 하는데, 27개의 자리에 이렇게 남자 10명을 배치할수는 없음.

[익명(2.222)]

ㅇㅇ. 위 순서쌍 풀이에서는 (남,여,여)가 서로 겹칠수 없기 때문에 그래. 예를 들어서 (남,여,남)이 (i,i+3,i+6)에 있는 순서쌍들을 고려한다면 (i,i+3,i+6)과 (i+6,i+9,i+12)가 i+6번째 위치의 남자를 공유하는데, (남,여,여)꼴의 순서쌍들은 이런식으로 겹칠수 없음.

[ScARfaCE(kayuaao)]

아 그럼 그 다음부터 이제 순서쌍 갯수가 80개를 넘으니 순서가 3또는 6 차이가 나는 남자가 적어도 2명은 존재한다 이렇게 되는거구나

[Rafle(probaroque)]

그냥 심플하게 (1,4,7), (2,5,8), (3,6,9), (10, 13, 16), ... 이런 식으로 쪼갠 다음 어딘가엔 남자 둘이 들어간다고 하면 안 되냐?

[ScARfaCE(kayuaao)]

저렇게 (1,4,7),~,(24,27,30)까지의 순서쌍들 다 만들어놓고 남자 30명을 저기다가 대응시켜서 비둘기집 쓰면 적어도 두 명의 남자가 존재하는 순서쌍이 존재한다. 이렇게?

[Rafle(probaroque)]

ㅇㅇ 그럼 그냥 설명이 필요없잖아 워스트 케이스도 바로 보이고... 1에서 80까지의 분할이니까 정리 바로 적용되고.. 마지막은 (70, 73, 76), (71, 74, 77), (72,75,78)로 27개가 나오고 마지막에 (79)랑 (80)이 나오겠네

[익명(2.222)]

자리를 3개 차지하는 순서쌍 개수는 27개이니 30명의 남자를 넣으면 같은 순서쌍 내에 2명 들어가야하니까.

[ScARfaCE(kayuaao)]

맨위의 댓의 가정으로 인해 3+a_i,6+a_i에 남자가 안와야하니 남자를 대응시키려면 순서쌍이 (1,4,7),(2,5,8),(3,6,9) 그 다음 첫 성분(남자)엔 4,5,6,7,8,9는 들어가면 안되니 10부터해서 이런식으로 다 세어보면 27개가 딱 나오고 이걸로 비둘기집쓰면 금방나오네

[ScARfaCE(kayuaao)]

이렇게보니 존나 간단하게 풀리네 다들 ㄱㅅㄱㅅ

[Rafle(probaroque)]

아 계산이 틀렸네.. 1-9까지 묶음이 세 개니까 1-81까지면 27개 묶음 나오고 그럼 28명 남자로도 커버되지 않나?

[ScARfaCE(kayuaao)]

뭐 묶음이 일단 30개 미만으로 어떻게든 나오긴하니까 상관없을듯

[익명(175.223)]

연속한 남자 3명중에 항상 3의배수만큼 차이나는 두명이 있는데 3명씩 9묶고 2명은 버려도 이 9묶음은 많아야 78자리를 차지 할거고 그중 어느하나는 8이하임 그럼 거기에는 8미만의 3의배수만큼 차이나는 두명이 있음

[익명(223.33)]

와ㅅㅂ 이새끼들 ㅈㄴ멋있어