Long Luo's Life Notes

每一天都是奇迹

发表于 更新于 分类于 阅读次数： Waline： 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 2 分钟

By Long Luo

数学题中个人比较喜欢数列与不等式结合的题目，这类题主要对递推关系的观察、数列分析、不等式放缩和解题思路的构造都有较高要求，能体会到数学乐趣。今天来挑战一道2011年清华大学自主招生数学试题中的数列大题，这道题本身计算量不大，难度中等。本文将详细分析这道数列题的解题过程，希望能够帮助读者直观理解这类题目的解题思路。

  1. (本小题满分14分)

已知函数 \(f(x) = \dfrac{2x}{ax + b}\) ，\(f(1) = 1\) ，\(f(\dfrac{1}{2}) = \dfrac{2}{3}\) 。令 \(x_1 = \dfrac{1}{2}\) ，\(x_{n+1} = f(x_n)\) 。

  1. 求数列 \(\{ x_n \}\) 的通项公式；

  2. 证明 \(x_1x_2 \dots x_n > \dfrac{1}{2e}\) 。

第一问

解：由 \(f(1) = 1\) ，\(f(\dfrac{1}{2}) = \dfrac{2}{3}\) 得：

\[ \begin{cases} a + b = 2 \\ a + 2b = 3 \end{cases} \]

易得：\(a = 1, \ b = 1\) ，所以 \(f(x)\) 的表达式为：

\[ f(x) = \frac{2x}{x+1} \label{1.1} \tag{1.1} \]

先求出数列 \(\{ x_n \}\) 的前几项： \(x_1 = \dfrac{1}{2}，x_2 = \dfrac{2}{3}，x_3 = \dfrac{4}{5}，x_4 = \dfrac{8}{9}\) ，可以猜测 \(\{ x_n \}\) 通项公式为：

\[ x_n = \frac{2^{n-1}}{2^{n-1} + 1} \label{1.2} \tag{1.2} \]

阅读全文 »

发表于 更新于 分类于 阅读次数： Waline： 阅读次数： 本文字数： 4.6k 阅读时长 ≈ 4 分钟

By Long Luo

在 2005 - 2015 年江西高考自主命题时期，江西卷一直以鲜明的风格闻名全国，尤其是数学试卷，更因题目难度大、运算量惊人而被许多考生视为“噩梦级”存在。此前我们曾解析过 2010年江西高考数学压轴题 ，一道融合数论的难题。

今天继续回顾江西卷另一道代表性压轴题：2006 年江西高考理科数学最后一题。这道题以数列为核心，将递推关系与不等式深度结合，综合性极强，即使放到今天来看，依然是一道颇具挑战性的高水平试题。

  1. (本小题满分 14 分)

已知数列 \(\{ a_n \}\) 满足： \(a_1 = \dfrac{3}{2}\) ，且 \(a_n = \dfrac {3na_{n-1}}{2a_{n-1} + n - 1}\) （ \(n \geq 2\) ， \(n \in \mathbb{N}^{*}\) ）.

  1. 求数列 \(\{ a_n \}\) 的通项公式；
  2. 证明：对于一切正整数 \(n\) ，不等式 \(a_1 \cdot a_2 \cdot \cdots \cdot a_n < 2 \cdot n!\) 恒成立。

第一问

在没有头绪的时候，我们不妨先算出数列的前几项，推测数列可能的表达式。

容易计算出： \(a_1 = \dfrac{3}{2}\) , \(a_2 = \dfrac{9}{4}\) , \(a_3 = \dfrac{81}{26}\) ， \(a_3 = \dfrac{162}{40}\) 。

不过观察数列 \(\{ a_n \}\) 前 4 项，仍然看不出什么规律，这个时候就要根据题设条件，找到数列的递推公式。

观察 \(a_n = \dfrac {3na_{n-1}}{2a_{n-1} + n - 1}\) ，由于分子只有1项，而分母里既有 \(a_{n-1}\) 又有 \(n - 1\) ，这种情况下如果对原式取倒数更容易化简：

阅读全文 »

发表于 更新于 分类于 阅读次数： Waline： 阅读次数： 本文字数： 3.5k 阅读时长 ≈ 3 分钟

By Long Luo

最近在短视频 App 里刷到不少中学数学题讲解，才发现现在的初中数学题，很多已经不只是“会算”这么简单了，背后往往还藏着不等式、函数、几何直觉等不同层面的思维训练。

当然，这也不算奇怪，几十年前的 IMO 试题放现在也就普通题。很多经典数学竞赛题，随着时间推移和教学资源普及，早已从高阶技巧逐渐变成了基础训练的一部分。

前几天我就反复刷到一道“求极值”的题，看起来不难，但这道题其实非常适合拿来练习数学直觉。

已知 \(x + y = 5\) ，求 \(\sqrt {x + 1} + \sqrt {y + 3}\) 的最大值。

看到这道题，首先想到的几何意义其实是将军饮马模型，但将军饮马问题求得是最小值问题。那最大值该怎么求呢？最大值的几何意义是什么呢？

这道题的有趣之处在于可以用很多完全不同的思路来解决，有的解法只需要代数变形和基本不等式，也可以使用几何视角、函数思想。

下面就道题为例，把几种典型解法都梳理一遍，也顺便重新锻炼一下自己的数学思维。

解法一：常规解法

由 \(y = 5 - x\) ，原式变成 \(\sqrt {x + 1} + \sqrt {8 - x}\) ，要保证根号有意义，所以 \(−1 \le x \le 8\) 。

设 \(S = \sqrt {x + 1} + \sqrt {8 - x}\) ，两边平方得 \(S^2 = (\sqrt{x + 1} + \sqrt{8 - x})^2\) 。

展开可得：

\[ \begin{aligned} S^2 & = (x + 1) + (8 - x) + 2 \sqrt {(x + 1)(8 - x)} \\ & = 9 + 2 \sqrt {(x + 1)(8 - x)} \\ & = 9 + 2 \sqrt {-x^2 + 7x + 8} \\ & = 9 + 2 \sqrt {-(x - \frac {7}{2})^2 + \frac {81}{4}} \end{aligned} \]

因此 \(S^2 \le 9 + 2 \times \dfrac {9}{2} = 18\) ，于是 \(S \le 3 \sqrt 2\) 当且仅当 \(x = \dfrac {7}{2}\) 时取等号。

故最大值为 \(3\sqrt2\) 。

阅读全文 »

发表于 更新于 分类于 阅读次数： Waline： 阅读次数： 本文字数： 3.9k 阅读时长 ≈ 4 分钟

By Long Luo

在上一篇文章我们剖析了 拼多多 2020 年校招笔试算法题中第一题: 多多的魔术盒子 ，今天来挑战下其中的第 4 题：骰子期望 1 ，题目如下：

骰子期望

扔 \(n\) 个骰子，第 \(i\) 个骰子有可能投掷出 \(X_i\) 种等概率的不同的结果，数字从 \(1\) 到 \(X_i\) 。所有骰子的结果的最大值将作为最终结果。求最终结果的期望。

  • 输入描述:
    • 第一行一个整数 \(n\) ，表示有 \(n\) 个骰子。( \(1 \le n \le 50\) )
    • 第二行 \(n\) 个整数，表示每个骰子的结果数 \(X_i\) 。( \(2 \le X_i \le 50\) )
  • 输出描述:
    • 输出最终结果的期望，保留两位小数。
  • 输入例子 \(1\) :
    • 2
    • 2 2
  • 输出例子 \(1\) :
    • 1.75

要解答这道题，我们需要先从脑海里把中学数学知识捡起来，弄清楚什么是期望 2？

在概率论和统计学中，一个离散性随机变量的数学期望是试验中每次可能的结果乘以其结果概率的总和：

\[ \operatorname {E} [X] = \sum _{i=1}^{\infty }x_{i}\,p_{i} \tag{1} \label{1} \]

具体到这道题示例 \(1\) ，很明显 \(2\) 个骰子只能取到 \(1\) 或者 \(2\) 个值：

  1. 假设这 \(2\) 个骰子取到的最大值为 \(1\) ，那么这 \(2\) 个骰子都只能选择 \(1\) ，概率为： \(\dfrac {1}{2} \times \dfrac {1}{2} = \dfrac {1}{4}\) ；

  2. 假设这 \(2\) 个骰子取到的最大值为 \(2\) ，那么存在 \(2\) 种可能，要么都取 \(2\) 或者 \(2\) 个骰子中有一个骰子投出了 \(2\) ，其概率为： \(\dfrac {1}{2} \times \dfrac {1}{2} + \dfrac {1}{2} \times 1 = \dfrac {3}{4}\) 。

那么期望为： \(\dfrac {1}{4} \times 1 + \dfrac {3}{4} \times 2 = 1.75\) 。

对于骰子数少的时候还可以枚举，如果骰子数量很多呢？用上述方法就会遇到困难，比如有 \(N\) 个骰子，最大值为 \(M\) ，那么骰子结果为 \([1, 2, \dots, M]\) ，如何计算每个结果的概率值呢？

直接算当然是可行的，但是如果骰子数量很多的话，计算会非常繁琐，所以有没有更简单的方法呢？

阅读全文 »

发表于 更新于 分类于 阅读次数： Waline： 阅读次数： 本文字数： 3.4k 阅读时长 ≈ 3 分钟

By Long Luo

众多IT大厂中拼多多虽然工作强度很大，但在给钱方面非常大方。大厂给的钱多，但要求也高。下面就来挑战拼多多 2020 年校招笔试算法题 1 中第一题：多多的魔术盒子 2 ，看看难度如何。

多多的魔术盒子

多多鸡有 \(N\) 个魔术盒子(编号 \(1 \sim N\) )，其中编号为 \(i\) 的盒子里有 \(i\) 个球。多多鸡让皮皮虾每次选择一个数字 \(X\) ( \(1 \le X \le N\) )，多多鸡就会把球数量大于等于 \(X\) 个的盒子里的球减少 \(X\) 个。 通过观察，皮皮虾已经掌握了其中的奥秘，并且发现只要通过一定的操作顺序，可以用最少的次数将所有盒子里的球变没。

那么请问聪明的你，是否已经知道了应该如何操作呢？

  • 时间限制：

    • C/C++ 1秒，其他语言 2 秒

  • 空间限制：

    • C/C++ 256M，其他语言 512M

  • 输入描述:

    • 第一行，有 \(1\) 个整数 \(T\) ，表示测试用例的组数。 ( \(1 \le T \le 100\) )
    • 接下来 \(T\) 行，每行 \(1\) 个整数 \(N\) ，表示有 \(N\) 个魔术盒子。 ( \(1 \le N \le 1,000,000,000\) )

  • 输出描述:

    • 共 \(T\) 行，每行 \(1\) 个整数，表示要将所有盒子的球变没，最少需要进行多少次操作。

  • 输入例子 1 :

    1
    2
    3
    4
    3
    1
    2
    5

  • 输出例子 1 :

    1
    2
    3
    1
    2
    3

最少的操作次数该怎么做？

根据题意，我们关键是要找到最少次数这个方法，那如何操作才能使用最少次数呢？

当面对复杂问题时，我们需要从简单情况入手，分析其中规律，找到突破口。

  1. \(N = 1\) 时，显然选择 \(X = 1\) ，需要 \(1\) 次操作；
  2. \(N = 2\) 时，可以先选择 \(X = 1\) ，再选择 \(X = 2\) ，需要 \(2\) 次操作；
  3. \(N = 3\) 时，只有先选择 \(X = 2\) ，再选择 \(X = 1\) ，最少需要 \(2\) 次操作；
  4. \(N = 4\) 时，可以先选择 \(X = 2\) 或者 \(X = 3\) ，最少需要 \(3\) 次操作；

通过分析发现，每次操作之后，球的数量都会动态变化。如果每次都选择中间的数字，这样每次操作之后，如果 \(N\) 为奇数的话，可以变成 \(2\) 个对称相同的数组， \(N\) 为偶数的话，则 \(2\) 个数组中元素值会相差 \(1\) ，再选择元素值更多的数组进行消除，这样可以实现操作次数最少。

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
private static int leastTimes_power(int n) {
    int ans = 1;

    for (int i = 0; i <= Math.sqrt(n); i++) {
        if (Math.pow(2, i) <= n) {
            ans = i;
        } else {
            break;
        }
    }

    return ans + 1;
}

为什么每次选取中间的数字进行操作次数最少呢？下面我们就来严谨的证明下！

阅读全文 »
0%