------------------------------- 질문 --------------------------------
52장을 완벽하게 섞는다는 가정하에(그럼 카드순서가 1,2,...,51,52에서 27,1,28,2,...,52,26 순으로 되겠죠)
c자리에 있던 카드가 섞은후엔 b자리로 가 있다는 것을 b==2c(mod53)를 사용해서 보이려면 어떻게 해야 하나요?
또, 이렇게 섞는것을 52번 했을때 그 카드가 다시 원위치로 가게 되는걸 보여야 하는데... 좀 도와 주세요.
--------------------------------- 대답 ------------------------------
안으로 섞기(In shuffle) 문제군요. (즉, 양끝인 1,52가 안으로 들어가는 문제) 바깥으로 섞는 문제도 있겠군요. 한번 풀어보죠.
자, 문제를 간단히 해서 카드가 1,2,3,...,10까지 있다고 합시다.
한번 섞으면 순서가 6, 1, 7, 2, 8, 3, 9, 4, 10, 5 가 됩니다.
이 위치를 어떻게 표현할까요?
느낌상 1,2,3,4,5 는 각각 위치가 두배로 밀려났고, 6,7,8,9,10은 맨앞에서 두칸씩 밀려났군요.
표현하자면 이렇습니다. 카드숫자 d는 처음의 숫자 2d 자리(mod 11)에 있습니다. 직접 해보면 아시겠죠?
한번섞었으니, 2배를 곱해서 계산했고, 한번 더 섞으면 2*2배, 즉 2^2를 곱해서 계산하고,..... s번 섞으면 2^s * k 자리(mod 11)에 있겠죠.
일반적으로 말하자면 카드가 n개 있고, s번 섞으면 처음의 숫자k가 위치한 곳은 2^s * k (mod n+1) 에 있습니다.
님은 두가지 질문을 하셨군요.
1. c자리에 있던 카드가 섞은후엔 b자리로 가 있다는 것을 b==2c(mod53)를 사용해서 보이려면 어떻게 해야 하나요?
-> 처음 b숫자가 2c로 간다는 것은 위에서 보였습니다.
2. 이렇게 섞는것을 52번 했을때 그 카드가 다시 원위치로 가게 되는걸 보여야 하는데...
-> 원래의 위치로 돌아간다는 것은 s번 섞었을 때 원래대로 돌아간다는 것은 다음과 같이 쓸 수 있습니다.
2^s == 1 (mod 53)
페르마 공식인가? (이름이 기억 안남 -_-;) 공식에 의해 s = 52 일 때는 반드시 참이죠. 따라서 52번 섞으면 원래 자리로 돌아옵니다.
그럼.
============================================
▷◁ 대구지하철 희생자를 추모합니다!
첫댓글 beyondit님 고마워요^^ 근데 아직두 왜 카드수가 10이하일땐 이게 적용이 되지 않는지 잘 모르겠네요..