2의 거듭 제곱으로 변경 [중복]
컴퓨터 과학 수업에서 저는 Codeforces의 다음 문제를 해결해야했습니다. https://codeforces.com/problemset/problem/55/A 원 위에 놓인 베개와 점프하는 파리에 관한 것입니다. $n$ 베개, 어디 $n = \overline{0,k}$. 파리는 무한한 시간 동안 이것을합니다. 특정 수의 베개에 대해 파리가 모든 베개에 닿을까요?$z$?
놀면서 나는 처음에 베개 수가 많을 때 파리가 모든 베개에 닿을 수 있다는 것을 발견했습니다. $z$2의 거듭 제곱이고 프로그램이 풀렸지 만 수학적으로 증명하고 싶습니다. 나는 다음 순서로 파리의 움직임을 설명 할 수 있었다.$a_n = (a_{n-1} + n)mod\ z, a_0 = 1;$ 인터넷 조사를하면서 글을 쓸 수 있다는 것을 알았습니다. $a_n = (a_{n-1} + n)$ 이 명시 적 기능으로 $\frac{n(n+1)}{2} + 1$. 이것은 내가 갇힌 곳입니다. 이것을 소화 할 수있는 방법으로 증명할 수있는 방법이 있습니까 (컴퓨터 과학 1 학년 학생)?
답변
당신의 생각을 계속해서, 질문은 나머지 모든 모드가 $z$ 형태이다 $\tfrac{n(n+1)}{2}+1$ 음이 아닌 정수 $n$. 참고$n\equiv m\pmod{z}$ 그리고 또한 $$\frac{n(n+1)}{2}+1\equiv\frac{m(m+1)}{2}+1,$$그래서 나머지가 형태 라면$\tfrac{n(n+1)}{2}+1$ 음이 아닌 정수 $n$이면 다음과 같은 형식이기도합니다. $\tfrac{n(n+1)}{2}+1$ 음이 아닌 정수 $m<z$. 이것은 파리가 모든 베개에 도달한다는 것을 보여줍니다.$$\Bbb{Z}/z\Bbb{Z}\ \longrightarrow\ \Bbb{Z}/z\Bbb{Z}:\ n\ \longmapsto\ \frac{n(n+1)}{2}+1,$$추측입니다. 때문에$\Bbb{Z}/z\Bbb{Z}$유한하다 이것은지도가 주입적일 때만 발생합니다. 어느 것을 알아낼 수 있습니까?$z$ 지도는 주입식입니까?
그건 그렇고, 서면으로 약간의주의를 기울여야합니다 $\tfrac{n(n+1)}{2}+1$ 에 $\Bbb{Z}/z\Bbb{Z}$. 만약$z$ 그럼에도 불구하고 무엇을 나누는 지 명확하지 않습니다. $2$의미해야합니다. 위에서이 표현은$$\tfrac{n(n+1)}{2}=1+2+3+\ldots+n.$$
어떤 값에 대해 정확히 파악할 필요없이 $z$이 맵은 추측 적입니다.이 아이디어는 이미 프로그램 작성에 도움이됩니다. 는 것을 보여준다 경우 즉시 결국 모든 베개에 도달, 다음 은 내 모든 베개에 도달$z$의사록. 따라서 처음에 파리의 위치 만 확인하면됩니다.$z$의사록; 같은 베개를 두 번 방문하면 완료된 것입니다. 그렇지 않으면 모든 베개를 방문합니다.