퀴즈 499, 500, 501 풀이
퀴즈 499 5장의 카드
5장의 서로 다른 카드 한 묶음을 어떤 특별한 방법으로 섞고, 반복해서 똑같은 방법으로 계속 섞는다.
이 때 카드가 처음 배열 상태로 돌아오게 하려면 최대 몇번을 섞어야 하는가?
p.s) 13장의 경우는? 52장의 경우는?
풀이
5=2+3 이라 2x3=6
13=5+4+3+1 이라 5x4x3x1=60
52=13+11+9+7+5+4+2+1 이라 13x11x0x7x5x4x2x1 = 180180
이 문제를 제대로 풀기 위해서는 치환의 개념을 제대로 알아야 한다. cycle, permutation 의 개념을 잘 알고 있으면 사실 아주 쉽게 풀 수 있는데 이 개념은 나중에 기회가 되면 소개하도록 하고 이번에는 답만 적고 남어간다. [ S_n 대칭군의 성질을 알면 바로 풀리는 문제인데, 이 대칭군은 대학교 현대대수학(or 추상대수학) 시간에 배우는 내용으로 기초 지식들이 조금 필요하다. 물론 문제를 푸는데 그 모든 것을 알 필요는 없지만 이 지식을 알면 답이 위에 쓴 것처럼 자연스럽게 적힌다.]
퀴즈 500 5개의 정수
임의의 5개의 정수 (반드시 이 5개의 정수가 다를 필요가 없다.)에서 그 합이 3으로 나누어 떨어지는 3개의 정수를 항상 택할 수 있음을 보여라.
c.f) 참고로 이 문제는 다음과 같이 일반화 될 수 있다.
2n-1 개의 정수들의 집합 S 는 합이 n 으로 나누어 떨어지는 n 개의 정수로 된 부분집합을 포함하고 있다.
풀이
3으로 나누었을 때 가능한 나머지는 0,1,2 이다. 특정 세 수를 3a+r_1, 3b+r_2, 3c+r_3 라 하면 이 세 수를 합했을 때 나머지는 r_1+r_2+r_3 를 3으로 나눈 것이 된다.
원하는 것은 5개의 수 중에서 3개를 조합하면 항상 3의 배수로 만들 수 있다는 것이다. 일단 첫번째로 생각해 볼 수 있는것은 r_1=r_2=r_3 이면 이는 항상 성립한다는 것이다. 같은 수를 세번 더하면 당연히 3의 배수가 될테니 이는 지극히 당연하다. 또 이 나머지가 모두 다르다면 또 3의 배수가 된다. 왜냐 나머지가 모두 다른 경우는 0,1,2 밖에 없고 이 3수의 합은 3이기에 3의 배수가 된다.
임의의 5개의 숫자를 뽑을 때, 나머지가 같은개 5, 나머지가 같은거 4+다른거 1, 나머지가 같은거 3, 다른거1 x2, 나머지가 같은거3, 다른거1, 또 다른거 1 또 나머지 같은거2, 나머지 다른거2, 나머지 또다른거 1 는 이 두가지 경우에 모두 대응되기에 임의의 다섯개의 정수에서 그 합이 3으로 나누어 떨어지는 3개의 정수를 항상 선택할 수 있다.
비슷한 방법으로 2n-1 개의 정수의 집합에서 n으로 나누어 떨어지는 n 개의 정수를 항상 선택할 수 있음을 보일 수 있다.
퀴즈 501 파토난 회의
회사 A 와 B 는 합병을 위해 회의를 하기로 했다. A 회사와 B 회사의 임원들과 회장들이 모여 최종 합의를 보기로 했다. 약속 시간이 지나도 B 의 회장이 오지 않았고, B 회사의 임원들이 하나 둘 씩 떠났다. 만약 이 상황에 내가 나가면, 원래 있었던 회의 모임에 1/3 만 남게 된다.하지만 내 상사와 후배가 돌아온다면, 처음에 모였던 사람의 절반이 남게 된다고 했을 때 처음에 참가한 회의에 모인 인원의 수는?
풀이
앞의 두 문제에 비해선 매우 쉬운 문제이다. 단순히 식만 잘 세우면 된다. x-1=y/3, x+2=y/2 --> x=7, y=18 즉 처음에 모인 모인은 18명이다.