토끼가 도착하게 되는 출발점은 모두 몇개인가? 모듈러 산술(Modular Arithmetic) KMO 대비문제

정 11각형의 꼭짓점에 시계방향으로  1,2,3 ...11 로 번호가 붙여져 있고 , 토끼는  이 도형위를 다음의 규칙에 따라 이동한다고 하자.

꼭지점 k 에서는 시계방향을 다음 k의 제곱번째 꼭지점으로 이동한다.
(예를 들어 , 꼭짓점 3 에서는 꼭지점 1로 ,꼭지점 4에서는 꼭짓점 9로 이동한다)

이규칙을  2008회 적용하여 꼭짓점  2에 토끼가 도착하게 되는 출발점은 모두 몇개인지 구하시요.
(KMO BIBLE COMBINATORICS 한국수학올림피아드 바이블 조합 p 187연습문제 4-20)
풀이:
규칙에 의해 k번째 꼭짓점에 있던 토끼는 k + k^2 번째 꼭짓점으로 이동한다.

1+ 1^2 ≡ (mod 11)
2+ 2^2 ≡ 6 (mod 11)
3+ 3^2 ≡ 1 (mod 11)
4+ 4^2 ≡ 9 (mod 11)
5+ 5^2 ≡ 8 (mod 11)
6+ 6^2 ≡ 9 (mod 11)
7+ 7^2 ≡ 1 (mod 11)
8+ 8^2 ≡ 6 (mod 11)
9+ 9^2 ≡ 2 (mod 11)
10+10^2 ≡ 0 (mod 11)
11+ 11^2 ≡ 0 (mod 11)

을 이용하면 꼭짓점 2, 꼭짓점 6, 꼭짓점 9가 반복됨을 알수있다.


Modular 1


Starting at noon, the hour hand points in order to the following:
$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, \ldots$


This is the way in which we count in modulo 12



Mod 6 Clock 

<modulo 6 clock>

modulo 11 clock 그려보시면 무슨말인지 아실거예요.
시계가 11시까지 있는 이상한 나라의 엘리스시간 그림으로 표현해 보세요!
modulo 11 을 쉽게 이해 할수있을 거예요.

여기서 ab(modm) 
m mod ,합동의 법(modular)이라고 한다.  "a를 m으로 나눈 나머지는 b"
라는 문장을 수식으로 표현한 것. 
 대수학에서 합동인 두 숫자는, 숫자의 실제 크기를 불문하고 어떤 수로 나누었을 때 나머지만 같으면 합동이라고 한다

그러므로
꼭짓점 1 ㅡ>2ㅡ> 6 ㅡ>9
꼭짓점 2 ㅡ> 6 ㅡ>9 ㅡ> 2 ㅡ> 6 ㅡ>9
꼭짓점 3 ㅡ> 1 ㅡ>2ㅡ> 6 ㅡ>9
꼭짓점 4 ㅡ> 9 ㅡ>2ㅡ> 6 ㅡ>9
꼭짓점 5 ㅡ> 8 ㅡ>6 ㅡ>9 ㅡ>2ㅡ> 6 ㅡ>9
꼭짓점 6 ㅡ>9 ㅡ>2 ㅡ> 6 ㅡ>9
꼭짓점 7 ㅡ> 1 ㅡ>2ㅡ> 6 ㅡ>9
꼭짓점 8 ㅡ>6 ㅡ>9 ㅡ>2ㅡ> 6 ㅡ>9
꼭짓점 9 ㅡ>2 ㅡ> 6 ㅡ>9

이고, 꼭짓점 1, 9 에서 출발하는 경우는 2008= 3*669+1이고,
꼭짓점 5 에서 출발하는 경우는 2008= 3*668+4이므로 , 2008회의  
규칙을 적용한후 2번 꼭짓점에 토끼가 도착하게 되는 경우는 
꼭짓점 1, 5, 9 에서 출발하는 경우뿐이다.
따라서 3개이다.

다시 풀어서 설명하겠습니다.
꼭짓점 1에서 출발하는 경우는 2008= 3*669+1 식과 무슨 상관이 있는지
살펴봅시다.
 꼭짓점 1에서 출발하는 경우 1+ 1^2 ≡ (mod 11)

1 더하기 1의 제곱은 2 , 다시  2 더하기 2의 제곱은 6 , 6 더하기 6의 제곱은 6+36=42
42를 (mod 11) 계산하면 6+ 6^2 ≡ 9 (mod 11)
 42 = 11*3 + 9 , 42≡ 9 (mod 11)라고 할수있고, 42를 11로 나누면 몫 3과 
나머지 9로 9 (mod 11) 입니다.
꼭짓점 1 ㅡ>(2ㅡ> 6 ㅡ>9)ㅡ>(2ㅡ> 6 ㅡ>9)ㅡ>(2ㅡ> 6 ㅡ>9).......
 꼭짓점 1에서 출발하는 경우 꼭짓점 2, 꼭짓점 6, 꼭짓점 9가 반복됨을 알수있다.
2008은 3 (2ㅡ> 6 ㅡ>9) 이 669개 와 나머지 1개로 나눌수있으니
이규칙을  2008회 적용하여 꼭짓점  2에 토끼가 도착하게 되는 출발점은  꼭짓점 1이 될수있다.

꼭짓점 9에서 출발하는 경우도 마찬가지다.
꼭짓점 9 ㅡ>(2ㅡ> 6 ㅡ>9)ㅡ>(2ㅡ> 6 ㅡ>9)ㅡ>(2ㅡ> 6 ㅡ>9).......

꼭짓점 5에서 출발하는 경우
꼭짓점 5 ㅡ> 8 ㅡ>6 ㅡ>9 ㅡ>(2ㅡ> 6 ㅡ>9)ㅡ>(2ㅡ> 6 ㅡ>9)ㅡ>(2ㅡ> 6 ㅡ>9)ㅡ>(2ㅡ> 6 ㅡ>9).......

꼭짓점 5 에서 출발하는 경우는 2008= 3*668+4이므로 , (2ㅡ> 6 ㅡ>9)3개씩 668개와 나머지 4개 5 ㅡ> 8 ㅡ>6 ㅡ>9 로 이규칙을  2008회 적용하여 꼭짓점  2에 토끼가 도착하게 되는 출발점은  꼭짓점 5가 될수있다.

이규칙을  2008회 적용하여 꼭짓점  2에 토끼가 도착하게 되는 출발점은 꼭짓점 1, 5, 9로
모두  3개이다.



궁금한점이나 모르는게 있으면 주저하지 마시고 연락하세요.
010-3549-5206

댓글