숫자의 합이 4의 배수가되는 5 자리 숫자는 몇 개입니까?
내 교과서에는 같은 문제가 있습니다. 5 자리 숫자의 합이 5의 배수 인 것을 제외하면 일반적인 접근 방식은 다음과 같습니다.
처음 4 자리를 선택합니다. 이를 수행하는 가능한 방법의 수 =$9\times 10 \times 10 \times 10$수만 자리 숫자는 0이 될 수 없기 때문입니다. 이 4 자리 숫자의 합은$5k$, $5k+1$, $5k+2$, $5k+3$, 또는 $5k+4$. 만약 그렇다면$5k$, 마지막 숫자는 $0$ 또는 $5$. 합계는$5k+1 \implies$ 마지막 숫자는 $4$ 또는 $9$, 등등. 각각의 경우에만$2$ 가능한 마지막 숫자.
따라서 이러한 5 자리 숫자의 총 수는 $9\times 10 \times 10 \times 10 \times 2 = 18000$.
이 접근 방식을 "자릿수 합은 4의 배수"문제에 적용하면
처음 4 자리의 합은 $4k \implies$ 마지막 숫자는 $0$, $4$, 또는 $8$.
처음 4 자리의 합은$4k+1 \implies$ 마지막 숫자는 $3$ 또는 $7$.
처음 4 자리의 합은$4k+2 \implies$ 마지막 숫자는 $2$ 또는 $6$.
처음 4 자리의 합은$4k+3 \implies$ 마지막 숫자는 $1$, $5$ 또는 $9$.
이 중 두 경우에는 가능한 마지막 자릿수 3 개를 얻고 다른 두 경우에는 가능한 마지막 자릿수 두 개를 얻습니다. 우리의 일반적인 접근 방식은 여기서 명확하게 구분됩니다. 이 문제를 해결하는 한 가지 방법은 "우리가 4 자리 숫자의 합이$4k$ 또는 $4k+3$", 그 숫자에 3을 곱합니다. $4k+2$ 과 $4k+1$ 그러나 2를 곱하십시오.이 두 숫자를 더하여 답을 얻으십시오.
너무 긴 것 같습니다. 이 작업을 수행하는 더 간단한 방법이 있습니까?
답변
허락하다 $S$ 범위에 하나 이상의 숫자가있는 숫자 세트 $\{1,\dots,8\}$. 나는 정확히 1/4의 숫자가$S$ 의 배수 인 자릿수 합계가 $4$. 이를 위해 우리는$S$ 4 개의 그룹으로, 각 그룹의 숫자는 나머지 모듈로 $4$.
허락하다 $S_1$ 숫자의 집합 $S$ 누구의 첫 번째 숫자가 $\{1,\dots,8\}$, 그리고 $x$ 숫자가있다 $S_1$. 첫 번째 숫자가$x$ 에 $\{1,2,3,4\}$, 다음을 포함하는 그룹 $x$ 해당 숫자를 다른 숫자로 변경하여 $\{1,2,3,4\}$. 예를 들어$34682$ 될 것이다 $\{14682, 24682, 34682, 44682\}$. 첫 번째 숫자가 다음과 같은 경우 해당 작업을 수행합니다.$\{5,6,7,8\}$.
하지만 첫 번째 숫자가 $0$ 또는 $9$? 그런 다음 고려$S_2$, 첫 번째 숫자가 $0$ 또는 $9$, 그리고 두 번째 숫자가 $\{1,\dots,8\}$, 첫 번째 글 머리 기호에서 두 번째 숫자까지 동일한 절차를 수행합니다.
그런 다음 $S_3$ 처음 두 자리가 각각있는 숫자 집합 $0$ 또는 $9$, 그리고 세 번째 숫자가 $\{1,\dots,8\}$, 동일한 작업을 수행합니다. 와 같다$S_4$.
이후 $S$ 겹치지 않는 합집합입니다. $S_1,S_2,S_3$ 과 $S_4$, 우리는 분할했습니다 $S$원하는대로 4 개의 그룹으로. 따라서 우리는 숫자의 수를 계산해야합니다$S$ 그리고 나누기 $4$ 원하는 숫자의 수를 찾으려면 $S$. 계산하기$S$, 보완 계산을 사용합니다.
외부의 숫자는 어떻습니까 $S$? 거기 엔 오직$16$ 이들의 숫자 합이 4의 배수 인 이들의 수를 직접 셀 수 있습니다.
표시 $a_i(n)$ $\>(0\leq i\leq3)$ 개수 $n$나머지를 남기는 숫자 합계가있는-자리 십진수 문자열 $i$ 모듈로 $4$, 수집 $a_i(n)$ 으로 $a(n):=\bigl(a_0(n), a_1(n), a_2(n), a_3(n)\bigr)$, 후자는 열 벡터로 간주됩니다. 그런 다음 우리는$$a(1)=(2,3,2,2)\ .$$ 후자의 경우 가능한 나머지의 다중성은 다음과 같습니다. $(3,3,2,2)$, 숫자 이후 ${\tt 0}$ 나머지 $0$ 허용됩니다.
우리가 이미 작성한 것은 $$a_0(2)=3\cdot2+2\cdot3+2\cdot2+3\cdot2=22\ .$$ 실제로 첫 번째 숫자에 나머지가있을 때 $0$ 두 번째는 또한 나머지가 있어야합니다 $0$, 그리고 첫 번째 숫자에 나머지가있을 때 $1$ 두 번째는 나머지가 있어야합니다 $3$, etcetera. 가능한 모든 나머지에 사용되는이 아이디어는 재귀로 이어집니다.$$ a(n+1)=A\ a(n)\qquad(n\geq1),\qquad A:=\left[\matrix{3&2&2&3\cr3&3&2&2\cr2&3&3&2\cr2&2&3&3\cr}\right]\ .$$ 이러한 방식으로 우리는 $$a(5)=A^4\ a(1)=\bigl(22500, 22498, 22500, 22502\bigr)\ ,$$ 그래서 우리가 찾고있는 숫자는 $22\,500$. 예를 들어 계산하려면$a(23)$ "순환"행렬의 더 높은 전력을 계산하는 방법을 찾는 것이 좋습니다. $A$.