大阪大学 情報科学研究科 情報工学 2020年8月実施 離散構造

标签：

• Osaka-University
• Recurrence-Relation
• Image-and-Preimage
• Binary-Relations

Author

祭音Myyura

Description

非負の整数全体の集合を $\mathbb{Z}_0$ と書く。 実数 $x$ に対して、$x$ を超えない最大の整数を $\lfloor x \rfloor$ と書く。 任意の $n \in \mathbb{Z}_0$ に対して、実区間 $[0, \infty)$ から $[0, \infty)$ への写像 (mapping) $f_n$ を以下の漸化式 (recurrence relation) により定める。

$$f_{n+1}(x) = x \lfloor f_n(x) \rfloor, \ f_0(x) = 1,\ x \in [0, \infty)$$

以下の各問に答えよ。

(1) 次の値をそれぞれ求めよ：$f_1(1.5)$, $f_2(2.5)$, $f_3(3.5)$。

(2) 命題 (proposition)「ある $n \in \mathbb{Z}_0$ が存在し $f_n$ は単射 (injective) である」の真偽を判定せよ。その理由を述べよ。

(3) 命題「$n \in \mathbb{Z_0}$ が正かつ偶数ならば $f_n$ は全射 (surjective) である」の真偽を判定せよ。その理由を述べよ。

(4) $\mathbb{Z}_0$ における以下の二項関係 (binary relation) を考える。

$$R = \{(k,l) \in \mathbb{Z}_0 \times \mathbb{Z}_0 \mid k = f_n(h/2) \text{ かつ } l = f_m(h/2) \text{ を満たす } h,n,m \in \mathbb{Z}_0 \text{ が存在する}\}$$

• (4-1) $R$ が反射的 (reflexive) であるかを判定せよ。その理由を述べよ。
• (4-2) $R$ が反対称的 (antisymmetric) であるかを判定せよ。その理由を述べよ。

(5) 方程式

$$\begin{align} f_2(x) = 171 \tag{i} \end{align}$$

を考える。以下の各問に答えよ。

• (5-1) 非負の実数 $x$ が方程式 (i) の解であると仮定する。ある実数 $\epsilon \in [0,1)$ が存在し $x=13+\epsilon$ が成り立つことを示せ。
• (5-2) 方程式 (i) の解を一つ求めよ。

(6) 方程式

$$\begin{align} f_3(x) = 171 \tag{ii} \end{align}$$

の解を一つ求めよ。

题目描述

记非负整数集为 $\mathbb Z_0$，$\lfloor x\rfloor$ 为不超过实数 $x$ 的最大整数。对每个 $n\in\mathbb Z_0$，递归定义映射 $f_n:[0,\infty)\to[0,\infty)$：

$$f_0(x)=1,\qquad f_{n+1}(x)=x\lfloor f_n(x)\rfloor.$$

1. 分别求 $f_1(1.5)$、$f_2(2.5)$、$f_3(3.5)$。
2. 判断命题“存在 $n\in\mathbb Z_0$ 使 $f_n$ 为单射”的真假并说明理由。
3. 判断命题“若 $n$ 为正偶数，则 $f_n$ 为满射”的真假并说明理由。
4. 在 $\mathbb Z_0$ 上定义关系
   $$R=\{(k,l)\mid \exists h,n,m\in\mathbb Z_0, k=f_n(h/2),\ l=f_m(h/2)\}.$$
   1. 判断 $R$ 是否自反并说明理由；
   2. 判断 $R$ 是否反对称并说明理由。
5. 考虑方程 $f_2(x)=171$：
   1. 假设非负实数 $x$ 为解，证明存在 $\epsilon\in[0,1)$ 使 $x=13+\epsilon$；
   2. 求一个解。
6. 求方程 $f_3(x)=171$ 的一个解。

考点

• 含取整函数的递推映射：逐层计算并分析分段结构。
• 单射与满射：用反例、值域区间或构造原像判断映射性质。
• 二元关系性质：根据量词定义检验自反性和反对称性。
• 取整方程：把整数部分设为未知整数，利用区间约束求解。

Kai

(1)

$$f_1(1.5) = 1.5 \cdot \lfloor f_0(1.5) \rfloor = 1.5 \cdot \lfloor 1 \rfloor = 1.5$$

$$f_2(2.5) = 2.5 \cdot \lfloor f_1(2.5) \rfloor = 2.5 \cdot \lfloor 2.5 \rfloor = 5$$

$$f_3(3.5) = 3.5 \cdot \lfloor f_2(3.5) \rfloor = 3.5 \cdot \lfloor 3.5 \cdot \lfloor 3.5 \rfloor \rfloor = 35$$

(2)

$n = 1$ の場合、

$$f_1(x) = x \lfloor f_0(x) \rfloor = x \cdot \lfloor 1 \rfloor = x$$

が単射であるので、命題は真である。

(3)

$n = 2$ の場合（$f_2(x) = x \lfloor x \rfloor$）を考える。

$0 \leq x < 1$ のとき、$f_2(x) = x \cdot 0 = 0$。

$x \geq 1$ のとき、$f_2(x) \geq 1$。

よって、$f_2(x)$ は全射ではない。ゆえに、命題は偽である。

(4)

(4-1)

任意の $k \in \mathbb{Z}_0$ に対して、(2) より、

$$\begin{aligned} &m = n = 1 \\ &h = 2k \end{aligned}$$

とおくと、$k = f_1(k)$ がわかるので、$R$ が反射的 (reflexive) である。

(4-2)

二項関係 $R$ の定義より、$R$ は対称的であることはほぼ自明なので、反対称的ではない。

(5)

(5-1)

$$\begin{aligned} f_2(x) = x \lfloor x \rfloor &= 171 \\ (13+\epsilon) \cdot \lfloor (13 + \epsilon) \rfloor &= 171 \\ 169 + 13 \epsilon &= 171 \\ \epsilon &= \frac{2}{13} \end{aligned}$$

(5-2)

（意味不明な設問）

(5-1) より、$x = \frac{171}{13}$ は一つの解である。

(6)

$$f_3(x) = x \lfloor x \lfloor x \rfloor \rfloor \leq x^3$$

$$5 < \sqrt[3]{171} < 6$$

なので、$x = 5 + \epsilon, \ \epsilon \in [0, 1)$ と書くと、

$$\begin{align} (5+\epsilon) \lfloor (5+\epsilon) \lfloor 5+\epsilon \rfloor \rfloor &= 171 \tag{iii} \\ (5+\epsilon) \lfloor 25 + 5 \epsilon \rfloor &= 171 \tag{iv} \end{align}$$

方程式 $(5+\epsilon)(25 + 5 \epsilon) = 171$ を解くと、$\epsilon = 3 \sqrt \frac{19}{5} - 5 \approx 0.85$ を得る。

よって、$\lfloor 25 + 5 \epsilon \rfloor = \lfloor 25 + 5 \times 0.85 \rfloor = 29$ を仮定し、方程式 (iv) を解くと、$\epsilon = \frac{26}{29}$ を得る。

最終的に $x = \frac{171}{29}$ を方程式 (ii) に代入して検証すると、$x = \frac{171}{29}$ は方程式 (ii) の解であることがわかる。