MathLabs

第3题

设整数 n>3n>3。从集合 {1,2,…,n}\{1,2,\ldots,n\} 中选取三个数，每个数使用一次，利用加法、乘法和括号写出所有可能的表达式。(a) 证明：若三个选数都大于 n/2n/2，则所得各值两两不同。(b) 设 pp 是满足 p≤np\le \sqrt{n} 的素数。证明最小选数为 pp 且表达式的值不全相异的选法数，恰好等于 p−1p-1 的正因数个数。
第 7/7 步：计数因数并完成 (b)
上一步下一步
p<p+d<2p≤p2≤n,z=p+p(p−1)d≤p2≤n,Nchoices=τ(p−1)p< p+d<2p\le p^2\le n,\qquad z=p+\frac{p(p-1)}{d}\le p^2\le n,\qquad N_{\mathrm{choices}}=\tau(p-1)
详细分析

对 p−1p-1 的每个因数 dd，有 d≤p−1d\le p-1，故 p<y=p+d<2p≤p2≤np<y=p+d<2p\le p^2\le n，同时 z=p+p(p−1)d≤p2≤nz=p+\frac{p(p-1)}{d}\le p^2\le n。因此每个因数都给出一个有效选法，且因数参数化是一一对应的，所以选法数等于 p−1p-1 的正因数个数。