페리 수열 $F_{n}$은 0부터 1까지 분모가 $n$이하인 모든 기약분수들을 오름차순으로 배열한 수열이다. 예를 들어 $n=3$ 이라면 수열은 다음과 같다. $\frac{0}{1}\ \frac{1}{3}\ \frac{1}{2}\ \frac{2}{3}\ \frac{1}{1}$ 페리 수열은 이전 수열에 새로운 기약분수가 추가되며 수열이 만들어진다. 페리 수열의 $a$번째 항을 $\frac{h_1}{k_1}$, $a+2$번째 항을 $\frac{h_2}{k_2}$, $a+1$번째 항을 $\frac{h_3}{k_3}$이라 하면 $h_{3}=h_{1}+h_{2}$, $k_{3}=k_{1}+k_{2}$ 이다. 이 성질을 이용해 이 다음 페리 수열에 등장할 분수를 알 수 있다. 페리 수열의 크기를 $|F_{n}|$이..

$a_{1}+a_{2}+...+a_{k}=d$이고 $0 \le a_{i} \le m$인 $a$에 관한 순서쌍의 개수를 찾고싶다! 예를 들어서 다음 경우를 보자. $a+b+c=15$이고 $m=9$ 기본적으로 전체 경우에서 망한 경우를 뺀다고 생각해보면 전체 경우는 $_{3}H_{15}$이다. 망한 경우는 $a$또는 $b$또는 $c$가 10이상인 경우로 $a$가 10이상이라고 생각한다면 $a^{\prime}+b+c=5$ 즉, $_{3}H_{5}$가 되고 $b$ ,$c$도 마찬가지이므로 $_{3}C_{1}$을 곱하여 망한 경우는 $_{3}C_{1}*$$_{3}H_{5}$가 된다. 따라서 구하고자 하는 경우의 수는 $_{3}H_{15}-$$_{3}C_{1}*$$_{3}H_{5}=73$이다. 이제 여러분은 계산할..

$n$이 자연수인 $k$에 대해 $n=2k+1$임을 만족한다고 하자. 이때 정$n$각형의 한 꼭짓점을 $a_{1}$이라 하고 반시계 방향으로 꼭짓점을 $a_{i}$ ($i=2,3,...,n$) 라고 하자. 이때 $\overrightarrow{a_{1}a_{2}}$를 $\vec{a}$, $\overrightarrow{a_{1}a_{n}}$을 $\vec{b}$라고 하자. 정$n$각형의 한 변의 길이는 1이며 $\overline{a_{1}a_{i}}=r_{i-2}$라고 하자. 이때 $\overrightarrow{a_{k+1}a_{k+2}}$를 $\vec{a}$, $\vec{b}$로 나타내보자. 이 문제 해결의 아이디어는 순서대로 내려가는 것이다. 위 그림에서 $\vec{b}$의 한칸 아래인 $\overrigh..

서로소인 자연수 $a,b$에 대해 수열 $F_{n}=aF_{n-1}+bF_{n-2}$에 대해 초항 $F_{0}=0, F_{1}=1$이면 $\gcd(F_{n},F_{m})=F_{\gcd(n,m)}$이다. 이것을 증명해보자. $F_{m} | F_{qm}$ 임의의 정수 $n$과 $p$에 대해 $F_{n-2} \equiv 0 \mod{p}$라고 하자. $F_{n} \equiv aF_{n-1} \pmod{p}$ $F_{2}=a$이므로 다음과 같이 바꿔쓸 수 있다. $F_{n} \equiv F_{2}F_{n-1} \pmod{p}$ 일반적으로 다음과 같이 쓸 수 있다.(이 아래에 나올 성질을 참고하자.) $F_{n+k} \equiv F_{2+k}F_{n-1} \pmod{p}$ $k=n-4$라고 하자. $F_{2n-4..

피보나치 수열 $f_n$에 대해 $F_{n}=f_{1}f_{2}f_{3} \cdot\cdot\cdot f_{n}$ 으로 정의되는 수열 $F_{n}$이 어떤 수로 몇 번 나누어 떨어지는지 계산하는 문제이다. 이 문제의 핵심은 $\gcd(f_{n},f_{m})=f_{\gcd(n,m)}$임을 이용하는 것이다. 주어진 수가 $n$이라 하고 직접 계산해보자. 또, $F_{n}$이 2로 나누어 떨어지는 횟수를 $g_2$라고 하자. $f_3$은 2이다. 그럼 $f_{3m}$은 전부 2의 배수가 됨을 알 수 있다. $g_{2}$+=$\lfloor \frac{n}{3} \rfloor$ $f_6$은 8이고 6은 3의 배수로 이미 한번 센 수를 빼면 2는 2개가 된다. $g_{2}$+=$2\cdot \lfloor \frac..

문제는 다음과 같습니다. 양의 정수 $n$이 주어졌을 때, 다음 두 조건을 만족하는 양의 정수 $x$의 개수를 구해보자. - $x$는 $n$의 배수이다 - $x$의 양의 약수의 개수는 $n$개이다. $x$가 $n$의 배수이니 적어도 $x$는 $n$의 소인수들을 모두 갖고 있습니다. $n=p^{c}$($p$는 임의의 소수, $c$는 임의의 자연수)라고 해봅시다. 만약 임의의 소수 $q$에 대해 $x=p^{p^{c-1}-1}q^{p-1}$이라면 $q$를 마음껏 정할 수 있기 때문에 경우가 무한개가 될 것입니다. 이를 만족하기 위해서는 $p^{c-1}-1 \ge c$이면 됩니다. 가장 작은 소수인 2에 대해서 생각해봅시다. $2^{c-1} \ge c+1$을 만족해야 합니다. 이 부등식은 $c=3$일 때부터 성..