임의의 52개의 정수를 택했을때 그중엔 합 또는 차가 100으로 나누어 떨어지는 두 수가 존재함을 보여야하는 문제인데 내가 이걸 일반화 시켜서 풀어보려고 하는중임
n+2개의 정수들을 택했을때 그 중엔 합 또는 차가 2n으로 나누어 떨어지는 두 수가 존재한다.
이걸 증명해보는데 (0,0), (1,2n-1),(2,2n-2),...,(n-1,n+1),(n,n)으로 둬보면 n+1개의 비둘기집을 만들수가 있어서 여기에 n+2개의 비둘기(정수)들을 대응시켜보려는데 대응을 어떻게 줘야할지를 모르겠음
일단 그냥 대응시키면 적어도 2개의 정수는 저 비둘기집에 같이 들어가있단건 알겠는데 저것들 비둘기집의 원소들을 더하면 그건 2n으로 나누어떨어지는데 빼주면 안나누어 떨어져서 어떻게 풀이를 다시 잘 써내려가야할지 모르겠다
비둘기집을 (0), (50), (1,99), (2,98), (3,97), ..., (49,51)에 써 봐. 나머지만 본거라 한 곳에서 같은거 두 개 뽑기 가능
그 다음엔 증명을 어떻게 써내려가야할까? 적어도 2개의 정수는 같은 비둘기집(순서쌍)에 있다. 이렇게 하고 뭐 어떻게 써내려가야 정확한 풀이가 될지 모르겠음 나머지들에 대응을 시킨거니까 같은 비둘기집에 있는 정수 2개를 a,b라고 하면 순서쌍의 일반적인 형태가 (p,q)인데 (q=2n-p (mod 2n))그럼 여기서 a=b=p mod 2n 일때, a=b=q mod 2n일때 이렇게 나눠서 풀이를 써야하나? 근데 이건 너무 이상해보임; 정확한 풀이가 잘 안떠오르네..
해당 댓글은 삭제되었습니다.
음 대충 이해는가는데 글에 나온대로 하면 p,2n-p 둘 중 하나를 같은 비둘기집에 있는 비둘기들에 대응시키면 합은 2n으로 나누어떨어지는데 그 차는 아닌거같음 뭐가 이상한거지
(0,0,0) (1,1,2n-1) ... (n,n,n) 에 비둘기를 넣으면 한집(i번째라해보면)에 두마리가 있는데 이 두마리에게 3개의 나머지중 서로 다른 두개를 주는데 그럼 어느 한마리는 나머지가 i임 남은 애는 i 또는 2n - i 이므로 성립
모르고 지웠는데 한마리의 비둘기가 가져가는 나머지가 2개(물론 n인 경우는 1개)인데 글대로 순서쌍을 만들면 비둘기가 순서쌍 내에서 서로달라서 엇갈리기 때문에 가져갈 나머지를 가져가지 못하지 않을까
ㅇㅇ 그니까 내가 하던게 그거임
아 아니다 순서쌍 그 자체에다 대응하라고?
그러니까 사실은 n+2개의 비둘기를 순서쌍 내의 나머지가 아니라 순서쌍에 대응시키면 됨 내가 한건 '순서쌍 하나를 비둘기랑 대응시키고 그중 겹치는 순서쌍이 있다' 를 좀 정교하게 고친거임
ㅇㅇ
그럼 그 다음은? 한 순서쌍에 적어도 두 개의 정수가 대응될텐데 그것들을 a,b라고 두면 a랑 b를 어떻게 해줘야함?
내가 막힌부분이 딱 여기임
음 '순서쌍이 같으면, 합차가 같은 두 원소가 있다'를 풀어서? 써보면 되지않을까
a=p, b=2n-p로 대응시키면 합은 뭐 2n으로 나누어 떨어지겠다만은 둘을 빼면 또 2n으로 나누어떨어지지가 않지않음?
합 또는 차는 결정되는게 아니라 푸는 사람이 적절히 택하면 됨 순서쌍이 같으면 두 원소를 막 택해도 적절한 연산(합 차)를 부여해서 같게 만든다는 거임
아 잠만 그니까 a,b가 꼭 순서쌍에 나타나는 수들과 다를 필요가 없단거네? a=b일수도 있단거고 쨌든 합차를 이렇게 시킬수는 있으니까
맞음
아 그렇구나 ㅈㄴ 간단한거였네 ㅋㅋㅋㅋ 새벽인데 도와줘서 ㄱㅅㄱㅅ