$A$ を $y = \frac{1}{2}x$, $x$ 軸 および 楕円 $\frac{1}{9}x^2+y^2=1$ で囲まれた第1象限の領域とする。
$y = mx$, $y$ 軸 および $\frac{1}{9}x^2+y^2=1$ で囲まれた第1象限の領域の面積が $A$ の面積と一致するような正数 $m$ を求めよ。
$x_1 = \frac{1}{3}x$, $y_1 = y$ とする。この線形変換により、楕円 $\frac{1}{9}x^2+y^2=1$ は 円 $x_1^2+y_1^2=1$ と変換され、また直線 $y = \frac{1}{2}x$ は 直線 $y_1 = \frac{3}{2}x_1$ に変換される。
この線形変換によって変換された領域を $A'$ とする。
ここで、直線 $y_1 = \frac{3}{2}x_1$ が直線 $y_1 = x_1$ に対して線対称となる直線 $y_1 = \frac{2}{3}x_1$ を考える。
直線 $y_1 = \frac{2}{3}x_1$ と 円 $x_1^2+y_1^2=1$、そして $y$ 軸で囲まれた領域 $A''$ は 領域 $A'$ と同じ面積になる。
線形変換による面積の拡大率は $A'$、$A''$ とも同じである。
したがって、直線 $y_1 = \frac{2}{3}x_1$ に対して、線形変換前の元の直線は $y = \frac{2}{9}x$ となるため、$m = \frac{2}{9}$ である。
2017年4月14日金曜日
2016年10月3日月曜日
USAMO 1997 Problem1
$p_1, p_2, p_3, \cdots$ を昇順に並んだ素数列とし、$x_0$ を $0 と 1$ の間の実数とする。
正の整数 $k$ に対して、$x_k$ を以下の通り定義する。なお $\{x\}$ で $x$ の小数部を示すものとする。 \[ \begin{eqnarray} x_k = \left\{ \begin{array}{ll} 0 & {\rm if }\; x_{k-1} = 0 \\ \left\{ \frac{p_k}{x_{k-1}}\right\} & {\rm if }\; x_{k-1} \neq 0 \\ \end{array} \right. \nonumber \end{eqnarray} \] このとき、$0<x_0<1$ を満たし、$x_0, x_1, x_2, \cdots$ が $0$ に収束する $x_0$ をすべて見つけよ。
$x_0$ を有理数と仮定した場合、互いに素な2つの正の整数 $0 < m_0 < n_0$ が存在し、$x_0 = m_0/n_0$ と表すことができる。
$m_0 < n_0$ であるため、ある正の整数 $\alpha$ が存在し、 \[x_1 = \left\{\frac{p_1}{\frac{m_0}{n_0}}\right\} = \left\{\frac{n_0p_1}{m_0}\right\} = \frac{n_0p_1 - \alpha m_0}{m_0}\] となる。このとき、定義より $0 \leq n_0p_1 - \alpha m_0 < m_0$ を満たす。
ここで改めて、$m_1 = n_0p_1 - \alpha m_0, n_1 = m_0$ とすると、$x_1 = m_1/n_1$ となり、分母は単調減少（$n_0 > m_0 = n_1 > m_1 = \cdots$）となる。
また定義より、分子は分母より常に真に小さくなるため、、分子の数列 $m_i$は $0$ 以上の単調減少となり、$i\to\infty$ としたとき、$m_i\to 0$ となる。
一方、$x_0$ を無理数と仮定した場合、$p_1/x_0$ は無理数であることは自明である。
よって、その小数部である $x_1$ も無理数となる。同様に $x_k$ が無理数ならば、$x_{k+1}$ も無理数となり、$0$ へ収束しない。
正の整数 $k$ に対して、$x_k$ を以下の通り定義する。なお $\{x\}$ で $x$ の小数部を示すものとする。 \[ \begin{eqnarray} x_k = \left\{ \begin{array}{ll} 0 & {\rm if }\; x_{k-1} = 0 \\ \left\{ \frac{p_k}{x_{k-1}}\right\} & {\rm if }\; x_{k-1} \neq 0 \\ \end{array} \right. \nonumber \end{eqnarray} \] このとき、$0<x_0<1$ を満たし、$x_0, x_1, x_2, \cdots$ が $0$ に収束する $x_0$ をすべて見つけよ。
$x_0$ を有理数と仮定した場合、互いに素な2つの正の整数 $0 < m_0 < n_0$ が存在し、$x_0 = m_0/n_0$ と表すことができる。
$m_0 < n_0$ であるため、ある正の整数 $\alpha$ が存在し、 \[x_1 = \left\{\frac{p_1}{\frac{m_0}{n_0}}\right\} = \left\{\frac{n_0p_1}{m_0}\right\} = \frac{n_0p_1 - \alpha m_0}{m_0}\] となる。このとき、定義より $0 \leq n_0p_1 - \alpha m_0 < m_0$ を満たす。
ここで改めて、$m_1 = n_0p_1 - \alpha m_0, n_1 = m_0$ とすると、$x_1 = m_1/n_1$ となり、分母は単調減少（$n_0 > m_0 = n_1 > m_1 = \cdots$）となる。
また定義より、分子は分母より常に真に小さくなるため、、分子の数列 $m_i$は $0$ 以上の単調減少となり、$i\to\infty$ としたとき、$m_i\to 0$ となる。
一方、$x_0$ を無理数と仮定した場合、$p_1/x_0$ は無理数であることは自明である。
よって、その小数部である $x_1$ も無理数となる。同様に $x_k$ が無理数ならば、$x_{k+1}$ も無理数となり、$0$ へ収束しない。
2016年8月15日月曜日
Putnam 1994 A-1
$a_n$ を $a_n\le a_{2n} + a_{2n+1} (\forall n\in\mathbb{N})$ を満たす数列とする。
このとき $\sum_{n=1}^{\infty}a_n$ が発散することを示せ。
与えられた条件より、$a_1\le a_2+a_3\le (a_4+a_5)+(a_6+a7)\le …$ となる。
$b_1=a_1, b_2=a_2+a_3, b_3=a_4+a_5+a_6+a_7, b_4=…$ となる数列$b_m$ を以下の通り定義する。\[b_m=\sum_{i=2^{m-1}}^{2^m-1}a_i (\forall m\in\mathbb{N})\]
このとき、$b_m$ は単調増加数列であるため、以下を満たす。 \[\sum_{i=1}^t b_i = \sum_{i=1}^t\sum_{j=2^{i-1}}^{2^i-1}a_j=\sum_{i=1}^{2^t-1}a_i\ge tb_1=ta_1\] よって、$\lim_{t\to\infty}\sum_{i=1}^{2^t-1}a_i=\sum_{i=1}^\infty a_i$ は発散する。
このとき $\sum_{n=1}^{\infty}a_n$ が発散することを示せ。
与えられた条件より、$a_1\le a_2+a_3\le (a_4+a_5)+(a_6+a7)\le …$ となる。
$b_1=a_1, b_2=a_2+a_3, b_3=a_4+a_5+a_6+a_7, b_4=…$ となる数列$b_m$ を以下の通り定義する。\[b_m=\sum_{i=2^{m-1}}^{2^m-1}a_i (\forall m\in\mathbb{N})\]
このとき、$b_m$ は単調増加数列であるため、以下を満たす。 \[\sum_{i=1}^t b_i = \sum_{i=1}^t\sum_{j=2^{i-1}}^{2^i-1}a_j=\sum_{i=1}^{2^t-1}a_i\ge tb_1=ta_1\] よって、$\lim_{t\to\infty}\sum_{i=1}^{2^t-1}a_i=\sum_{i=1}^\infty a_i$ は発散する。
2016年6月26日日曜日
Putnam 1994 A-3
$X$ を、辺の長さが $1, 1, \sqrt{2}$ である直角二等辺三角形の点の集合とする。
もし、$X$ の元を4色で塗り分ける場合、同じ色の点が $2-\sqrt{2}$ 以上の距離に存在している。
「同じ色の点が $2-\sqrt{2}$ 以上の距離に存在していない」場合を仮定する。
$X$ の元が4色で塗り分けられないことを証明する。
直角三角形の各点を $A:(0, 0), B:(1, 0), C:(1,1)$ とする。
また、線分 $AB$ 上の点で、点 $A$ から $k=2-\sqrt{2}$ の距離にある点を $D$ とする。同様に、線分 $AC$ 上の点で、点 $A$ から $k$ の距離にある点を $E$、点 $C$ から $k$ の距離にある点を $F$、線分 $BC$ 上の点で、点 $C$ から $k$ の距離にある点を $G$ とする。（下図参照）
三角形 $ABC$ と、三角形 $DBG$ が相似形であることから、線分 $DB$ の長さは $k$ になり、四角形 $ADGE$ と四角形 $CFDG$ が平行四辺形であることが分かる。
よって、線分 $EG$ および 線分 $DF$ の長さも $k$ になる。
点 $A$ および点 $C$ は、どの点からも $k$ 以上離れている。少なくともこれらの点が別々の色である必要がある。点 $A$ 、点 $C$ の色をそれぞれ色 $cA$、色 $cC$ とする。
点 $D$ の色は、点 $A$ からの距離より、色 $cA$ ではない。また、点 $C$ からの距離より、色 $cC$ でもない。よって、色 $cD$ とする。
点 $G$ の色も同様、どの色とも異なる色 $cG$ となる。
点 $B$ の色を色 $cD$ としても一般性を失わない。
このとき、点 $E$ は、その位置から色 $cA$, $cC$ $cG$ のいずれでもない。また、色 $cD$ により点 $B$ を塗っているため、色 $cD$ でもない。
以上より、$X$ の元を4色で塗りつぶすことはできない。
これにより、「同じ色の点が $2-\sqrt{2}$ 以上の距離に存在していない」⇒ 「$X$ の元を4色に塗り分けられない」となる。
よって、上の命題の対偶「$X$ の元を4色で塗り分ける」⇒「同じ色の点が $2-\sqrt{2}$ 以上の距離に存在する」は真となる。
もし、$X$ の元を4色で塗り分ける場合、同じ色の点が $2-\sqrt{2}$ 以上の距離に存在している。
「同じ色の点が $2-\sqrt{2}$ 以上の距離に存在していない」場合を仮定する。
$X$ の元が4色で塗り分けられないことを証明する。
直角三角形の各点を $A:(0, 0), B:(1, 0), C:(1,1)$ とする。
また、線分 $AB$ 上の点で、点 $A$ から $k=2-\sqrt{2}$ の距離にある点を $D$ とする。同様に、線分 $AC$ 上の点で、点 $A$ から $k$ の距離にある点を $E$、点 $C$ から $k$ の距離にある点を $F$、線分 $BC$ 上の点で、点 $C$ から $k$ の距離にある点を $G$ とする。（下図参照）
三角形 $ABC$ と、三角形 $DBG$ が相似形であることから、線分 $DB$ の長さは $k$ になり、四角形 $ADGE$ と四角形 $CFDG$ が平行四辺形であることが分かる。
よって、線分 $EG$ および 線分 $DF$ の長さも $k$ になる。
点 $A$ および点 $C$ は、どの点からも $k$ 以上離れている。少なくともこれらの点が別々の色である必要がある。点 $A$ 、点 $C$ の色をそれぞれ色 $cA$、色 $cC$ とする。
点 $D$ の色は、点 $A$ からの距離より、色 $cA$ ではない。また、点 $C$ からの距離より、色 $cC$ でもない。よって、色 $cD$ とする。
点 $G$ の色も同様、どの色とも異なる色 $cG$ となる。
点 $B$ の色を色 $cD$ としても一般性を失わない。
このとき、点 $E$ は、その位置から色 $cA$, $cC$ $cG$ のいずれでもない。また、色 $cD$ により点 $B$ を塗っているため、色 $cD$ でもない。
以上より、$X$ の元を4色で塗りつぶすことはできない。
これにより、「同じ色の点が $2-\sqrt{2}$ 以上の距離に存在していない」⇒ 「$X$ の元を4色に塗り分けられない」となる。
よって、上の命題の対偶「$X$ の元を4色で塗り分ける」⇒「同じ色の点が $2-\sqrt{2}$ 以上の距離に存在する」は真となる。
2016年1月18日月曜日
1からNまで繋げた回文
例えば $1234567891011･･･$ といったように $1$ から 順番に数字を繋げて文字を作る。
いくつまで数字を結合すれば回文になるか？
$N> 0$ とし、$1234･･･N$ を回文と仮定する。
$N$ の桁数を $k$ とした場合、$10^{k-1} \leq N < 10^k$ となる。
このとき $10^{k-1} = 100･･･00\leq N$ は、$0$ が $k-1$ 個続く回文を構成する数字の中で最も $0$ が連続する数の一つとなる。
$10^{k-1}$ と $10^{k-1}+1$ が結合した数字 $100･･･00100･･･01$ を考える。
$0$ で始まる数字は存在せず、また、回文であっても最大桁数は $k$ であるため、100･･･00 と 00･･･001 が回文の真ん中の値の候補の一つになる。
（候補の一つ、と言ったのは、$N$ よりも小さな値であれば $2\times 10^{k-1}$ や $3\times 10^{k-1}$ も候補になり得るため）
しかし、真ん中の値である $x\times 10^{k-1}$ の左右は $99･･･99$ と $00･･･01$ であるため、回文になりえない。
いくつまで数字を結合すれば回文になるか？
$N> 0$ とし、$1234･･･N$ を回文と仮定する。
$N$ の桁数を $k$ とした場合、$10^{k-1} \leq N < 10^k$ となる。
このとき $10^{k-1} = 100･･･00\leq N$ は、$0$ が $k-1$ 個続く回文を構成する数字の中で最も $0$ が連続する数の一つとなる。
$10^{k-1}$ と $10^{k-1}+1$ が結合した数字 $100･･･00100･･･01$ を考える。
$0$ で始まる数字は存在せず、また、回文であっても最大桁数は $k$ であるため、100･･･00 と 00･･･001 が回文の真ん中の値の候補の一つになる。
（候補の一つ、と言ったのは、$N$ よりも小さな値であれば $2\times 10^{k-1}$ や $3\times 10^{k-1}$ も候補になり得るため）
しかし、真ん中の値である $x\times 10^{k-1}$ の左右は $99･･･99$ と $00･･･01$ であるため、回文になりえない。
2015年11月25日水曜日
最小値
$0<u<\sqrt{2}, v>0$ の場合、以下の式の最小値は？
平面図上の点 $A: (u, \sqrt{2-u^2})$ および点 $B: (v, 9/v)$を考える。
問いの式は $AB$ 間の距離の最小値の2乗と考えることができる。
$0<u<\sqrt{2}$ 上の任意の値を $u_1$ とし、点 $A$ の $y$ 座標を $u_2$ とした場合、$u_2 = \sqrt{2-u_1}\Rightarrow u_1^2 + u_2^2 = 2$ となる。
これは $(u_1, u_2)$ が原点を中心とした半径 $\sqrt{2}$ 上の円周上（ただし第1象限上のみ）に存在していることを示している。
また、$v>0$ 上の任意の値を $v_1$ とし、点 $B$ の $y$ 座標を $v_2$ とすると、$v_1v_2 = 9$ となる。
反比例のグラフになるが、このグラフは $(0, 0), (3, 0), (0, 3), (3, 3)$ を頂角とする1辺が $3$ となる正方形の頂角を通り、かつ、$(3, 3)$ でのみ接する。
点 $A$ は上の正方形の内側になるため、点 $A$ と点 $B$ の距離が最も短くなるのは、原点と $(3, 3)$ を結ぶ直線上に各々の点が存在する場合となる。
このときの点 $A$ は、$u_1 = \sqrt{2-u_1^2} \Rightarrow 2u_1^2 = 2$ となり、前提条件より、$(1, 1)$ となる。
同様に点 $B$ は $(3, 3)$ となり、上記式が最小値になるときの $(u, v)$ は各々 $(1, 3)$ となる。
したがって、 \[(1-3)^2+\Big(\sqrt{2-1^2}-\frac{9}{3}\Big)^2 = 4+(1-3)^2 = 4+4=8\] となり、上記式の最小値は $8$ である。
平面図上の点 $A: (u, \sqrt{2-u^2})$ および点 $B: (v, 9/v)$を考える。
問いの式は $AB$ 間の距離の最小値の2乗と考えることができる。
$0<u<\sqrt{2}$ 上の任意の値を $u_1$ とし、点 $A$ の $y$ 座標を $u_2$ とした場合、$u_2 = \sqrt{2-u_1}\Rightarrow u_1^2 + u_2^2 = 2$ となる。
これは $(u_1, u_2)$ が原点を中心とした半径 $\sqrt{2}$ 上の円周上（ただし第1象限上のみ）に存在していることを示している。
また、$v>0$ 上の任意の値を $v_1$ とし、点 $B$ の $y$ 座標を $v_2$ とすると、$v_1v_2 = 9$ となる。
反比例のグラフになるが、このグラフは $(0, 0), (3, 0), (0, 3), (3, 3)$ を頂角とする1辺が $3$ となる正方形の頂角を通り、かつ、$(3, 3)$ でのみ接する。
点 $A$ は上の正方形の内側になるため、点 $A$ と点 $B$ の距離が最も短くなるのは、原点と $(3, 3)$ を結ぶ直線上に各々の点が存在する場合となる。
このときの点 $A$ は、$u_1 = \sqrt{2-u_1^2} \Rightarrow 2u_1^2 = 2$ となり、前提条件より、$(1, 1)$ となる。
同様に点 $B$ は $(3, 3)$ となり、上記式が最小値になるときの $(u, v)$ は各々 $(1, 3)$ となる。
したがって、 \[(1-3)^2+\Big(\sqrt{2-1^2}-\frac{9}{3}\Big)^2 = 4+(1-3)^2 = 4+4=8\] となり、上記式の最小値は $8$ である。
2015年11月12日木曜日
互いに素な部分集合
集合 $\{1, 2, ..., 2n\}$ から任意に $n+1$ 個の整数を取り出す。
取り出した整数群には、必ず互いに素な整数が$2$つ以上存在している。
$i$ が奇数である集合$\{i, i+1\}$ を $n$ 個作成する。
集合 $\{1, 2, ..., 2n\}$から取り出した任意の整数は、上で作成した $n$ この集合のいずれかに属する。
取り出した整数が $n+1$ 個であるため、少なくとも2つの整数が同じ集合 $\{i_1, i_1+1\}$ に属することになる。
隣り合う整数 $i_1$ と $i_1+1$ は互いに素である。
Q.E.D
取り出した整数群には、必ず互いに素な整数が$2$つ以上存在している。
$i$ が奇数である集合$\{i, i+1\}$ を $n$ 個作成する。
集合 $\{1, 2, ..., 2n\}$から取り出した任意の整数は、上で作成した $n$ この集合のいずれかに属する。
取り出した整数が $n+1$ 個であるため、少なくとも2つの整数が同じ集合 $\{i_1, i_1+1\}$ に属することになる。
隣り合う整数 $i_1$ と $i_1+1$ は互いに素である。
Q.E.D
登録:
投稿 (Atom)