2004 AIME I 第 15 题
先试着解答 2004 AIME I 第 15 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2004 AIME I 解答,或核对答案。
所有题目均经美国数学协会(MAA)官方合法授权使用。
15.
对所有正整数 ,定义 并按如下方式定义一个数列:,且对所有正整数 有 。令 为使 成立的最小 。(例如,,。)设 为满足 的正整数 的个数。求 的不同质因数之和。
For all positive integers let and define a sequence as follows: and for all positive integers Let be the smallest such that (For example, and ) Let be the number of positive integers such that Find the sum of the distinct prime factors of
答案:511
解答:
倒推:若 ,则 (总是可以);还可能有 ,前提是 不是 的倍数且 ,即 不以 结尾且 。因此满足 的整数构成一棵以 为根的树的第 列:前几列为 、、、,并且除 和以 结尾的顶点以外,每个顶点都有两个子节点;那些例外只有子节点 。
找出这些只有一个子节点的顶点。因为 ,顶点 位于第 列。以 结尾的顶点可由一个以 结尾的顶点连续减 九次到达,所以这样的顶点位于树中那些 的倍数之后 列。第 到第 列完全翻倍(那之前没有只有一个子节点的顶点),所以第 列有 个顶点,其中 的倍数,也就是第 列顶点的子节点 ,有 个。因此对 ,第 列含有 个以 结尾的顶点(第 列没有,因为第 列中的 的倍数是 本身,它的后代 被排除;这个排除正好就是 缺少的那个子节点)。
第 列中一个只有一个子节点的顶点,会从第 列原本可能的 个顶点中去掉 个。因此 因为 是质数, 的不同质因数之和为 。
Work backwards: for (always) and for (provided is not a multiple of and i.e. does not end in and ). So the integers with form column of a tree rooted at the columns begin and every vertex has two children except and the vertices ending in which have only the child
Locate those one-child vertices. Since the vertex sits in column A vertex ending in is reached by subtracting nine times from a vertex ending in so such vertices sit columns after the multiples of in the tree. Columns through double perfectly (no one-child vertices occur that early), so column has vertices, of which the multiples of — the children of column — number Hence for column contains vertices ending in (column has none, because the multiple of in column is itself, whose descendant is excluded — that exclusion is exactly the missing child of ).
A one-child vertex in column removes of the potential vertices from column Therefore Since is prime, the sum of the distinct prime factors of is
其他年份的第 15 题
1997 AIME · 1998 AIME · 1999 AIME · 2000 AIME I · 2000 AIME II · 2001 AIME I · 2001 AIME II · 2002 AIME I · 2002 AIME II · 2003 AIME I · 2003 AIME II · 2004 AIME II · 2005 AIME I · 2005 AIME II · 2006 AIME I · 2006 AIME II · 2007 AIME I · 2007 AIME II · 2008 AIME I · 2008 AIME II · 2009 AIME I · 2009 AIME II · 2010 AIME I · 2010 AIME II · 2011 AIME I · 2011 AIME II · 2012 AIME I · 2012 AIME II · 2013 AIME I · 2013 AIME II · 2014 AIME I · 2014 AIME II · 2015 AIME I · 2015 AIME II · 2016 AIME I · 2016 AIME II · 2017 AIME I · 2017 AIME II · 2018 AIME I · 2018 AIME II · 2019 AIME I · 2019 AIME II · 2020 AIME I · 2020 AIME II · 2021 AIME I · 2021 AIME II · 2022 AIME I · 2022 AIME II · 2023 AIME I · 2023 AIME II · 2024 AIME I · 2024 AIME II · 2025 AIME I · 2025 AIME II · 2026 AIME I · 2026 AIME II