首页> 重点归纳 > AMC数学竞赛真题2016年12B 24-25

AMC数学竞赛真题2016年12B 24-25

2018-09-12 重点归纳

AMC12是针对高中学生的数学测验，该竞赛开始于2000年，分A赛和B赛，于每年的2月初和2月中举行，学生可任选参加一项即可。其主要目的在于激发学生对数学的兴趣，参予AMC12的学生应该不难发现测验的问题都很具挑战性，但测验的题型都不会超过学生的学习范围。这项测验希望每个考生能从竞赛中享受数学。那么接下来跟随小编来看一下AMC12的官方真题以及官方解答吧：

Problem 24

There are exactly $77,000$ ordered quadruplets $(a, b, c, d)$ such that $\gcd(a, b, c, d) = 77$ and $\operatorname{lcm}(a, b, c, d) = n$ . What is the smallest possible value for $n$ ?

$\textbf{(A)}\ 13,860\qquad\textbf{(B)}\ 20,790\qquad\textbf{(C)}\ 21,560 \qquad\textbf{(D)}\ 27,720 \qquad\textbf{(E)}\ 41,580$

Solution

Let $A=a\div 77,\ B=b\div 77$ , etc., so that $\gcd(A,B,C,D)=1$ . Then for each prime power $p^k$ in the prime factorization of $N=n\div 77$ , at least one of the prime factorizations of $(A,B,C,D)$ has $p^k$ , at least one has $p^0$ , and all must have $p^m$ with $0\le m\le k$ .

Let $f(k)$ be the number of ordered quadruplets of integers $(m_1,m_2,m_3,m_4)$ such that $0\le m_i\le k$ for all $i$ , the largest is $k$ , and the smallest is $0$ . Then for the prime factorization $N=2^{k_2}3^{k_3}5^{k_5}\ldots$ we must have $美国数学竞赛$ So let's take a look at the function $f(k)$ by counting the quadruplets we just mentioned.

There are $14$ quadruplets which consist only of $0$ and $k$ . Then there are $36(k-1)$ quadruplets which include three different values, and $12(k-1)(k-2)$ with four. Thus $amc数学竞赛$ and the first few values from $k=1$ onwards are $14,50,110,194,302,434,590,770,\ldots$ Straight away we notice that $14\cdot 50\cdot 110=77000$ , so the prime factorization of $N$ can use the exponents $1,2,3$ . To make it as small as possible, assign the larger exponents to smaller primes. The result is $N=2^33^25^1=360$ , so $n=360\cdot 77=27720$ which is answer $\textbf{(D)}$ .

Also, to get the above formula of $f(k)=12 k^2+2$ , we can also use the complementary counting by doing $amc12$ , while the first term $(k+1)^4$ is for the four integers to independently have k+1 choices each, with the second term indicating to subtract all the possibilities for the four integers to have values between 0 and k-1, and similarly the third term indicating to subtract all the possibilities for the four integers to have values between 1 and k, in the end the fourth term meaning the make up for the values between 1 and k-1.

Problem 25

The sequence $(a_n)$ is defined recursively by $a_0=1$ , $a_1=\sqrt[19]{2}$ , and $a_n=a_{n-1}a_{n-2}^2$ for $n\geq 2$ . What is the smallest positive integer $k$ such that the product $a_1a_2\cdots a_k$ is an integer?

$美国数学竞赛AMC真题$

Solution 1

Let $b_i=19\text{log}_2a_i$ . Then $b_0=0, b_1=1,$ and $b_n=b_{n-1}+2b_{n-2}$ for all $n\geq 2$ . The characteristic polynomial of this linear recurrence is $x^2-x-2=0$ , which has roots $2$ and $-1$ .

Therefore, $b_n=k_12^{n}+k_2(-1)^n$ for constants to be determined $k_1, k_2$ . Using the fact that $b_0=0, b_1=1,$ we can solve a pair of linear equations for $k_1, k_2$ :

$k_1+k_2=0$ $2k_1-k_2=1$ .

Thus $k_1=\frac{1}{3}$ , $k_2=-\frac{1}{3}$ , and $b_n=\frac{2^n-(-1)^n}{3}$ .

Now, $a_1a_2\cdots a_k=2^{\frac{(b_1+b_2+\cdots+b_k)}{19}}$ , so we are looking for the least value of $k$ so that

$b_1+b_2+\cdots+b_k \equiv 0 \pmod{19}$ .

Note that we can multiply all $b_i$ by three for convenience, as the $b_i$ are always integers, and it does not affect divisibility by $19$ .

Now, for all even $k$ the sum (adjusted by a factor of three) is $2^1+2^2+\cdots+2^k=2^{k+1}-2$ . The smallest $k$ for which this is a multiple of $19$ is $k=18$ by Fermat's Little Theorem, as it is seen with further testing that $2$ is a primitive root $\pmod{19}$ .

Now, assume $k$ is odd. Then the sum (again adjusted by a factor of three) is $美国数学竞赛AMC真题$ . The smallest $k$ for which this is a multiple of $19$ is $k=17$ , by the same reasons. Thus, the minimal value of $k$ is $\textbf{(A) } 17$ .

Solution 2

Since the product $a_1a_2\cdots a_k$ is an integer, the sum of the logarithms $\log _2 a_k$ must be an integer. Multiply all of these logarithms by $19$ , so that the sum must be a multiple of $19$ . We take these vales modulo $19$ to save calculation time. Using the recursion $a_n=a_{n-1}a_{n-2}^2$ : $a_0=0,a_1=1\dots\implies 0,1,1,3,5,11,2,5,9,0,18,18,16,14,8,17,14,10,0\dots$ Listing the numbers out is expedited if you notice $a_{n+1}=2a_n+(-1)^n\pmod {19}$ . Notice that $a_k+a_{k+9}\equiv 0\text{ mod }19$ . The cycle repeats every $9+9=18$ terms. Since $a_0=0$ and $a_{18}=0$ , we only need the first $17$ terms to sum up to a multiple of $19$ : $\boxed{\textbf{(A) }17}$ . (NOTE: This solution proves 17 is the upper bound, but since 17 is the lowest answer choice, it is correct. To rigorously prove it, you will have to add up the mods listed until you get $0\pmod{19}$ .