最大质因数 求和

hbghlyj

Invariants society, Summer 2022, Week 1.

Problem 1.
设 $f(k)$ 为正整数 $k$ 的最大质因数。假设序列 $(a_n)$ 满足$$a_1=2\quad a_{n+1}=a_n+f(a_n)$$
求最大的 $n$ 使得 $a_n<10^4$。

引理. 设 $p_1=2,p_2=3,\dots$ 为素数，则 $a_{p_n+p_{n+1}-2}=p_np_{n+1}$。

引理证明

对 $n$ 归纳。$a_3=6$，所以 $n=1$ 时引理成立。

假设 $a_{p_n+p_{n+1}-2}=p_np_{n+1}$，则 $a_{p_n+p_{n+1}-2}$ 的最大质因数是 $p_{n+1}$，
所以 $a_{p_n+p_{n+1}-1}=p_np_{n+1}+p_{n+1}=p_{n+1}(p_n+1)$。

同样地，$a_{p_n+p_{n+1}}=p_{n+1}(p_n+2)$，

$\ldots$

$a_{p_{n+1}+p_{n+2}-3}=p_{n+1}(p_{n+2}-1)$，

$a_{p_{n+1}+p_{n+2}-2}=p_{n+1}p_{n+2}$。因此引理对 $n+1$ 也成立。

解. 根据引理，$a_{97+101-2}=a_{196}=101\times97$，因此

$a_{197}=101\times98$，

$a_{198}=101\times99<10^4$，

$a_{199}=101\times100>10^4$。因此答案为 $\boxed{198}$。

A076271

hbghlyj

2. In the game masterbrain, your friend has secretly chosen a sequence of $n$ numbers, each in $\{1,2, \ldots, k\}$. On your turn you query a sequence of $n$ numbers in $\{1,2, \ldots, k\}$. Your friend then tells you which number is the most common among all of the terms that you predicted correctly. In the event of ties, your friend says the highest number. For example, if your friend's password is $1,2,2,3,1$ and you guess $3,3,2,2,1$, since one 2 and one 1 were guessed correctly, your friend would say 2.
   After $q$ queries, you then have to guess the sequence. If you guess correctly, you win, and otherwise your friend wins.
   • For what positive integers $(n, k)$ does there exists a $q$ so that you can guarantee you know your friend's sequence after $q$ queries?
   • Prove there exists a constant $C$ so that for any such $(n, k)$, you can guess your friend's sequence in $q=C n k$ queries.
3. Evaluate the following limit: $$\lim _{n \rightarrow \infty} \int_{0}^{2 \pi} \frac{\left(x^{3} \ln x\right)\left(\cos (\sin n x)+\cos ^{2} n x\right)}{(\sin n x) \sin (\sin n x)+1} d x$$

Week 2.

1. There are $n$ line segments in the plane, parallel to the coordinate axes, so every endpoint of a line segment does not intersect with any other line segment. A dotted rectangle is a rectangle whose sides all lie along one of the line segments such that there is exactly one endpoint of a line segment in the rectangle's interior. Find the maximum number of dotted rectangles in terms of $n$ (values for small $n$ can be stated without proof).
2. Given an increasing sequence of natural numbers $c_1, c_2, \cdots$, where $c_i$ does not divide $c_j$ for any $i \neq j$, show that the sequence of differences $$ c_2-c_1, c_3-c_2, c_4-c_3 \cdots $$ is unbounded.
3. Suppose acute triangle $A B C$ has a fixed side $B C$. $D$ is the incenter of triangle $A B C$ while its incircle is tangent to $A B, B C$ and $A C$ at $E, F$ and $G$, respectively. Suppose $A D$ intersects $E F$ at $I$ and $G F$ at $H$, respectively. Circumcircle of triangle $A I C$ intersects $B C$ at $J$. Show that no matter how $A$ varies, a fixed point lies on the circumcircle of triangle $J H I$.

Week 3.

1. Suppose $l_1, l_2, l_3, l_4$ are parallel lines so $l_i$ lies below $l_{i+1}$ for $i=1,2,3$. Let $d_i$ denotes the distance between $l_i$ and $l_{i+1}$. Suppose $d_1=d_3=1$ and $d_2=4$. $A_i$ lies on $l_i$ for $i=1,2,3,4$, such that $A_3$ lies on left of $A_4$ and $A_3 A_4=\sqrt{26}$. Now suppose $A_3 A_4$ are fixed and $A_1 A_2$ is moving alone their lines such that $A_1 A_2=\sqrt{10}$ and $A_1$ lies on left of $A_2$. Find the minimum value of $A_2 A_4+A_1 A_3$ throughout the motion of $A_1$ and $A_2$.
2. Find all positive integers $m$ such that for all positive integers $n$, $$ \sum_{k=1}^{10}\left(k^2+k\right)^n-9 \cdot 10^n $$ and $m$ are relatively prime
3. A directed graph $G$ has $n$ nodes and there are no four nodes $a_1, a_2, b_1, b_2 \in V(G)$ so that there are edges from $a_i$ to $b_j$ for each $i, j \in\{1,2\}$.
   Let $f(n)$ be the maximum number of edges in $G$. There exists constants $c, C>0$ and $\alpha$ so $$ c n^\alpha \leq f(n) \leq C n^\alpha $$ for all $n$. Find $\alpha$. (Partial credit will be given for bounds on $\alpha$.)

Week 4.

1. Suppose $f, g$ are Riemann integrable functions on closed interval $I$ that are non-zero everywhere. Define $$ \|f\|_m^g=\left(\int_I\left|g f^m\right| \mathrm{d} x\right)^{\frac{1}{m}} $$ Suppose further that $f, g$ are both continuous on $I$, show that $\lim _{m \rightarrow \infty}\|f\|_m^g$ exists and doesn't depend on $g$. Is this conclusion still true if one of $f$ or $g$ is not continuous?
2. Given real numbers $c_1, c_2, \cdots, c_n$, show that it is possible to color each of them either red or green in such a way that each triple $c_i, c_{i+1}, c_{i+2}$ for $i=1,2, \cdots, n-2$ contains numbers of both colors and $$ |R| \geq \frac{1}{6} \sum_{i=1}^n\left|c_i\right| $$ where $R$ denotes the sum of numbers colored red.
3. Find all functions $f: \mathbb{Z} \rightarrow \mathbb{Z}$ so $$ f\left(a^2\right)+f\left(b^2\right)+f\left(c^2\right)+2 f(a) f(b)+2 f(b) f(c)+2 f(c) f(a)=0 $$

Week 5.

1. There are $n$ people, numbered $1,2, \cdots, n$, playing a game. First, they are all told a directed graph $G$ with $n$ nodes labelled $1,2, \cdots, n$. They are then allowed to discuss and decide a collective strategy amongst themselves, before they are placed in a room and each person is given a red or blue hat. The room is designed such that person $i$ cannot see their own hat, nor the hat of any person $j$ such that there is a directed edge in $G$ from $i$ to $j$. They can see all other hats.
   
   All at once, each person guesses the color of their own hat. If at least one person guesses correctly, the $n$ people win, and otherwise they lose. For which $G$ can a win be guaranteed?
2. Suppose a $n \times n$ matrix satisfies that its $(k, 1),(k, 2), \ldots,(k, k),(k-1, k),(k-2, k), \ldots,(1, k)$ entries are identically $1 / k$ for $k=1,2, \ldots, n$, where the $(i, j)$ th entry refers to its entry in the $i$ th row and $j$ th column. Suppose it has (possibly complex) eigenvalues $\lambda_1, \lambda_2, \ldots, \lambda_n$. Show that $$ \max _{i=1,2, \ldots, n}\left|\lambda_i\right| \leq 4 $$
3. Suppose $\Lambda$ is a quadrilateral. Suppose a pair of opposite sides of $\Lambda$ lie on line $l_1, l_2$; the other pair of opposite sides of $\Lambda$ lie on line $l_3, l_4$ and the diagonals of $\Lambda$ lie on line $l_5, l_6$. Line $l$ intersects $l_{2 i-1}$ at $A_i$ and $l_{2 i}$ at $B_i$ for $i=1,2,3$. Circle $\Omega_i$ has diameter $A_i B_i$ for $i=1,2,3$. Find all possible values of total number of intersections of three circles $\Omega_1, \Omega_2$ and $\Omega_3$, given that any two of them do not coincide.

Week 6.

1. Suppose $f:[0,1] \rightarrow \mathbb{R}$ is continuous and differentiable on $[0,1]$. Suppose further that $f(1)=f(0)=0$. Find the largest possible constant $A$ such that $$ A\left(\int_0^1 f \mathrm{~d} x\right)^2 \leq \int_0^1\left(f^{\prime}\right)^2 \mathrm{~d} x $$ for all such $f$ on $[0,1]$ (Where $f^{\prime}$ is the derivative of $\left.f\right)$.
2. Let $a_1, \cdots, a_n$ be (not necessarily distinct) positive integers. Among such $a_i$, let $f(n)$ be the maximum number of nonempty subsets $S \subseteq\{1,2, \cdots, n\}$ such that $$ \sum_{x \in S} a_x $$ divides $$ \sum_{i=1}^n a_i $$ Prove $$ \left|\frac{f(n)}{2^n}-\frac{1}{2}\right| \leq \frac{1}{\sqrt{n}} $$
3. Suppose $O$ is the center of ellipse $\Omega$ and $A B$ is its diameter. Suppose the perpendicular of $A B$ via $O$ intersects $\Omega$ at $D$. $C$ lies on $\Omega$ but doesn't lie on arc $A D B$. Suppose $H$ is the orthocenter of $\triangle A B C$ and the perpendicular of $O H$ via $O$ intersects $\Omega$ at $E$ and $F$. Show that at least one of $D E$ and $D F$ is perpendicular to $A H$.

Week 7.

1. There is a (not necessarily finite) set $S$ of points in the plane such that
   • For any $p_1, p_2 \in S$ with $p_1 \neq p_2, d\left(p_1, p_2\right)>1$, where $d$ denotes Euclidean distance.
   • For every two points $p_1, p_2 \in S$ with $d\left(p_1, p_2\right) \leq 2$, there is some other point $p$ in the plane (not necessarily in $S$ ) such that $p_1, p_2$ are the only points in $S$ that are a distance $\leq 1$ from $p$.
   Prove that we can color every point in $S$ one of four colors such that for any $p_1, p_2 \in S$ with $d\left(p_1, p_2\right) \leq 2$, $p_1$ and $p_2$ are different colors.
2. You have a $2022 \times 2022$ grid. Each grid cell is colored either black or white, such that for some $k \leq 1000$, it's impossible to partition the grid into disjoint rectangular regions such that there's at least $k$ black cells in each region. In terms of $k$, what is the maximum number of grid cells colored black?
3. Let $\left(a_i\right)_{i=1, n},\left(b_i\right)_{i=1, n},\left(c_i\right)_{i=1, n}$, be 3 sequences of $n$ real numbers each, such that $b_i>0$ for each $i$ and $\left(a_i\right),\left(\frac{c_i}{b_i}\right)$ are both increasing sequences. Show that if $$ \sum_{i=1}^n a_i b_i=0 $$ then $$ \sum_{i=1}^n a_i c_i \geq 0 $$

Week 8.

1. Find all positive integer values of $n$ such that every digit of $n$ is 8 or 9 and every digit of $n^2$ isn't 8 or 9 .
2. A hunter is chasing an invisible rabbit along the positive real axis. The hunter colors each integer one of $k$ colors, and then the rabbit sees this coloring and chooses an integer to start at it. Then, every second the rabbit either stays at their current integer, $n$, can move to $n-1$ if $n-1>0$, or can move to $n+1$. The hunter is then reported the color of the rabbit's current integer. The hunter can catch the rabbit if they know its exact position, otherwise the rabbit is never caught. Let $m$ be the minimum value of $k$ for which the rabbit can be caught. Prove $3 \leq m \leq 4$. [Bonus points will be awarded if anyone submits a proof for which of these two values $k$ is]
3. Suppose circle $\Omega$ is centered at $A$, and $B$ is a point on this circle. Suppose further that $C$ is a point on segment $A B$. Circle $\Gamma$ is centered at $C$ with radius $C B$. Line $A E$ is tangent to $\Gamma$ at $D$, intersect $\Omega$ at $E$ where $E$ lies on the extension of $A D$. The Euler line of $\triangle D E B$ intersects $\Omega$ at point $H$ such that $B$ lies between $E$ and $H$ on $\Omega$, and intersects $D B$ at $L$. $E B$ intersects $\Lambda$ at $I$. Circle pass through $H, I$ and $A$ intersects $\Gamma$ at $K$ other than $I$. Show that if $I K=I L$ then $K M=K O$, where $M$ and $O$ are the orthocenter and circumcenter of triangle $D E B$, respectively.

hbghlyj

1. 给定集合$\{1,2,3,\ldots,n\}$的$n$个不同的子集，证明存在一个数字，使得如果它在每个子集中都被去掉，其余子集仍然是不同的。
2. 证明存在一个自然数$n$，满足以下条件：它不可被10整除，它的十进制表示中至少有100个数字，并且可以交换$n$的两个不同数字，得到与$n$有相同质因数集的数字。
3. 一个$n\times m$的矩形由$nm$个单位正方形组成。画出矩形的对角线。它穿过多少个单位正方形？
   MSE | MSE | MSE | MSE
   $m+n-\gcd(m,n)$

hbghlyj

1. 一个$23\times23$的正方形被划分成大小为$1\times1$，$2\times2$和$3\times3$的小正方形。最少可能有多少个$1\times1$的小正方形？
2. 设$n$是一个正整数，$a_1,a_2,\cdots,a_n$是互不相同的整数。证明多项式$\left(x-a_{1}\right)\left(x-a_{2}\right) \ldots\left(x-a_{n}\right)-1$在$\mathbb Z$上不可约。MSE | 类似MSE

hbghlyj

hbghlyj 发表于 2023-4-29 01:25
设$n$是一个正整数，$a_1,a_2,\cdots,a_n$是互不相同的整数。证明多项式$\left(x-a_{1}\right)\left(x-a_{2}\right) \ldots\left(x-a_{n}\right)-1$在$\mathbb Z$上不可约。MSE

如果这个多项式在$\mathbb Z$可约，那么存在两个次数小于$n$的整系数首1多项式$P(x)$和$Q(x)$，使得
$$P(x)Q(x)=(x-a_1)(x-a_2)\dots(x-a_n)-1.$$
因此
$$P(a_i)Q(a_i)=-1\quad\forall i\in\{1,2,\ldots,n\},$$
但$P(a_i)$和$Q(a_i)$都是整数，所以只有两种可能：

• $P(a_i)=1$且$Q(a_i)=-1$，
• $P(a_i)=-1$且$Q(a_i)=1.$

无论哪种情况，都会得到
$$P(a_i)+Q(a_i)=0\quad\forall i\in\{1,2,\ldots,n\},$$
但这是不可能的，因为$P(x)+Q(x)\not\equiv0$（两个首项系数为1的多项式之和）的次数小于$n$，根据代数基本定理，它不可能有$n$个不同的根$a_1,a_2,\ldots,a_n.$

hbghlyj

hbghlyj 发表于 2023-4-29 01:24
给定集合$\{1,2,3,\ldots,n\}$的$n$个不同的子集，证明存在一个数字，使得如果它在每个子集中都被去掉，其余子集仍然是不同的。

去掉这个数字后出现相同集合是因为有相差1个元素的集合
例如$n=3$
{1,2}
{1,3}
{1,2,3}
若去掉1,得到3个不同的集合,满足条件;
若去掉2,得到2个{1,3},不满足条件;
若去掉3,得到2个{1,2},不满足条件.

hbghlyj

hbghlyj 发表于 2023-4-29 01:47
Given $n$ different subsets of the set of numbers $1,2,3,\dots,n$, prove that there exists a number, such that if it is left out of each subset, the remaining subsets will still be different. FB

我想了一个证明:

若$A\ne B$且$A\setminus\{x\}=B\setminus\{x\}$, 则$A\setminus\{x\}=B$或$B\setminus\{x\}=A$.

将题中的$n$个子集看作顶点, 若存在$x$使$A\setminus\{x\}=B$, 就连接一条边$A\to B$, 并且将$x$标注在其上. 这样得到一个$n$阶图$G$.

注意到$A\to B$能推出$|A|=|B|+1$
所以$G$是acyclic graph(无圈图),
所以$G$的边数小于$n$, 但一共有$n$个数, 所以至少有一个数没有被标注在边上, 它就是所求的数.

hbghlyj

hbghlyj 发表于 2023-4-29 01:22
Week 4 Q1
Suppose $f, g$ are Riemann integrable functions on closed interval $I$ that are non-zero everywhere. Define $$ \|f\|_m^g=\left(\int_I\left|g f^m\right| \mathrm{d} x\right)^{\frac{1}{m}} $$ Suppose further that $f, g$ are both continuous on $I$, show that $\lim _{m \rightarrow \infty}\|f\|_m^g$ exists and doesn't depend on $g$. Is this conclusion still true if one of $f$ or $g$ is not continuous?

YouTube
$\exists\xi_m\in I$ s.t.$$\|f\|^g_m=\left(\int_I|f^mg|\right)^{1/m}=\left(|g(\xi_m)|\int_I|f^m|\right)^{1/m}$$
$\forall x\in I:0<c\le|g(x)|\le C$
$$\implies c^{1/m}\left(\int_I|f^m|\right)^{1/m}\le\|f\|^g_m\le C^{1/m}\left(\int_I|f^m|\right)^{1/m}$$
By Extreme value theorem $\exists x_0\in I:|f(x)|\le|f(x_0)|\;\forall x\in I$
Claim: $\lim_{m\to\infty}\|f\|^g_m=|f(x_0)|=\|f\|_\infty$
Proof:$$\|f\|^g_m\le C^{1/m}\left(\int_I|f(x_0)^m|\right)^{1/m}=C^{1/m}|I|^{1/m}|f(x_0)|$$
Let $m\to\infty$
$$\lim_{m\to\infty}\|f\|^g_m\le|f(x_0)|=\|f\|_\infty$$
It remains to prove $\lim_{m\to\infty}\|f\|^g_m\ge\|f\|_\infty$

Czhang271828

hbghlyj 发表于 2023-4-29 08:24
证明存在一个自然数 $n$, 满足以下条件: ① 它不可被 $10$ 整除, ② 它的十进制表示中至少有 $100$ 个数字, ③ 可以交换 $n$ 的两个不同数字, 得到与 $n$ 有相同质因数集的数字.

第二题挺好想的, 用一下循环节即可. 例如取 $14\cdots 43$ 和 $34\cdots 41$. 其中 $4$ 的数量为 $1/(31\cdot 13)$ 循环节长度 $\times n$ 再 $-1$.

例如
\[
n_1:=1444444444444444444444444444443
\]
\[
n_2:=3444444444444444444444444444441
\]
有相同的质因数集. 记 $S(-): n\mapsto \text{$n$ 的质因数集}$, 则
\[
S(n_1)=S(n_1)\cup \{13,31\}=S(n_2)\cup \{13,31\}=S(n_2).
\]

Czhang271828

hbghlyj 发表于 2023-4-29 08:25
本帖最后由 hbghlyj 于 2023-4-29 02:03 编辑
一个的 $23\times 23$ 正方形被划分成大小为 $3\times 3$, $2\times 2$ 和 $1\times 1$ 的小正方形. 最少可能有多少个 $1\times 1$ 的小正方形?

构造 $1$ 可以, 证明 $0$ 不行即可.