Katu math

数学やアルゴリズムなど

マトロイドの例と構成法

マトロイドの定義周りについて簡単に触れた後，マトロイドの例と，既存のマトロイドから新たなマトロイドを作る方法を見ていきます．各主張の証明は載せていませんが，末尾の参考文献にそのうちの多くが書かれているので，気になる方は参照してみてください．

準備

$\mathbb{Z}_{+}, \mathbb{R}_{+}$ を，それぞれ非負整数全体の集合，非負実数全体の集合とします．

有限集合 $E$ と $E$ の部分集合族 $ \mathcal{F} \subset 2^{E} $ の組 $ \mathcal{M} = (E, \mathcal{F})$ であって，次の条件を満たすものをマトロイドと呼びます．

  1. $\emptyset \in \mathcal{F}$
  2. $X \subset Y , Y\in \mathcal{F}$ なら $X \in \mathcal{F}$
  3. $|X| < |Y|, X \in \mathcal{F}, Y \in \mathcal{F}$ なら，ある $y \in Y\backslash X$が 存在して，$X \cup \{ y \} \in \mathcal{F}$ を満たす

$ \mathcal{F}$ の元を独立集合と呼び，独立集合でない $2^{E}$ の元を従属集合と呼びます．

マトロイドの極大な独立集合を基と呼び，極小な従属集合をサーキットと呼びます．

基とサーキットの性質として，次のようなものが知られています．

基の性質
マトロイド $(E,\mathcal{F})$ の基全体からなる集合を $\mathcal{B}$ とすると，次が成立する．
  • $\mathcal{B} \neq \emptyset$
  • 任意の $B_{1}, B_{2} \in \mathcal{B}$ と任意の $x \in B_{1} \backslash B_{2}$ に対して， $y \in B_{2} \backslash B_{1}$ であって， $(B_{1} \backslash \{ x\} ) \cup \{ y\} \in \mathcal{B}$ を満たすものが存在する．
  • 任意の $B_{1}, B_{2} \in \mathcal{B}$ と任意の $y \in B_{2} \backslash B_{1}$ に対して， $x \in B_{1} \backslash B_{2}$ であって， $(B_{1} \backslash \{ x\} ) \cup \{ y\} \in \mathcal{B}$ を満たすものが存在する．
サーキットの性質
マトロイド $(E,\mathcal{F})$ のサーキット全体からなる集合を $\mathcal{C}$ とおくと，次が成立する．
  • $\mathcal{C} \notin \emptyset $
  • 任意の $C_{1}, C_{2} \in \mathcal{C}$ に対して， $C_{1} \subset C_{2}$ ならば $C_{1} = C_{2}$ である．
  • 任意の $X \in \mathcal{F}$ と 任意の $e\in E$ に対して， $X\cup \{e\}$ に含まれるサーキットは高々1個である．

マトロイド $\mathcal{M} = (E, \mathcal{F})$ に対して，関数 $r: 2^{E} \to \mathbb{Z}_{+}$ であって，任意の $X \in 2^{E}$ に対して $$ r(X) = Xに含まれる独立集合の元数の最大値$$ を満たすものを，$\mathcal{M}$ のランク関数といいます．

ランク関数の性質として，次のようなものが知られています．

ランク関数の性質
マトロイド $(E,\mathcal{F})$ のランク関数を $r$ とすると，任意の集合 $X,Y \subset E$ と $x,y\in E$ に対して次が成立する．
  • $ r(X) \leq |X|$
  • $ X \subset Y$ なら $r(X)\leq r(Y)$
  • $ r(X\cup Y) + r(X \cap Y) \leq r(X) + r(Y) $

特に，3番目の不等式は，マトロイドのランク関数が劣モジュラーであるという重要な性質を表しています．

ここまで，基・サーキット・ランク関数が満たす性質を記しましたが，逆にこれらの性質を満たす集合族や関数からマトロイドを作ることもでき，かつそのようなマトロイドは一意に定まります．例えば，前述した3つの性質を満たす $E$ の部分集合族 $\mathcal{B}$ をとると，$\mathcal{B}$ を基の集合とするマトロイドが一意に定まり，それは $\mathcal{B}$ のある元の部分集合全体を独立集合とするマトロイドです．サーキットやランク関数についても同様です．

最後に，マトロイドに関する次の問題を考えます．

最大重み独立集合問題
マトロイド $(E, \mathcal{F} )$ と重み関数 $c: E \to \mathbb{R}_{+}$ が与えられた時，集合 $F\in \mathcal{F}$ であって $$ \sum_{e\in F} c(e) $$ の値が最大であるようなものを求める
最小重み基問題
マトロイド $(E, \mathcal{F} )$ と重み関数 $c: E \to \mathbb{R}_{+}$ が与えられた時，マトロイドの基 $B$ であって $$ \sum_{e\in B} c(e) $$ の値が最小であるようなものを求める

マトロイド上では，これらの問題はどちらも貪欲的に解くことができます．つまり，最初は空集合を保持し，$E$ の要素を重みの降順(最小重み基問題の場合は昇順)に見ていき，その要素を加えても集合が独立であるならば集合に要素を加えることを繰り返すことで，最適解である独立集合を得ることができます．

マトロイドの例

一様マトロイド

$E$ を $n$ 元集合として，$k$ を $0\leq k \leq n$ を満たす整数とします．$ \mathcal{F} $ を，$E$ の部分集合のうち元数が $k$ 以下であるもの全体からなる集合とすると， $U_{n}^{k} = (E, \mathcal{F} )$ はマトロイドをなします．これを一様マトロイドと呼びます．特に， $k = n$ のとき，$E$ の全ての部分集合が独立集合になり， $U_{n}^{n}$ を自由マトロイドと呼びます．

行列マトロイド

$ M $ を体 $F$ 上の $m \times n$ 行列 として，$E = \{1,2,\ldots, n \}$ とします．$\mathcal{F}$ を，$E$ の部分集合であって，対応する $ M $ の列ベクトルが一次独立であるもの全体からなる集合とすると， $(E,\mathcal{F})$ はマトロイドをなし，これを行列マトロイドといいます．

特に，任意の体 $F$ 上の行列マトロイドとして表せるマトロイドを正則マトロイドといいます．

  • 独立集合の判定は，選んだ列ベクトルからなる行列に対して掃き出し法を適用して列フルランクであるかを確認することで行えます．

  • $ M $ が行フルランクであるとき，マトロイドの基は列ベクトルのなす基底に対応しています．

  • ちなみに，matroidという名称は行列 (matrix) に由来しています．

グラフマトロイド

$G = (V,E)$ を無向グラフとして，$\mathcal{F}$ を，$E$ の部分集合のうち閉路を持たないもの全体からなる集合とすると， $(E, \mathcal{F})$ はマトロイドをなし，これをグラフマトロイドといいます．

  • $G$ が連結である時， グラフマトロイドの基は木です．連結でないなら，グラフマトロイドの基は全域森です．

  • グラフマトロイドのサーキットは単純閉路です．

  • $G$ が連結である時，最小重み基問題は $G$ の最小全域木を求める問題になり，クラスカル法はこれに対する貪欲アルゴリズムです．

  • グラフの接続行列を考えることで，グラフマトロイドは $\mathbb{F}_{2}$ 上の行列マトロイドであることが分かります．さらに，グラフマトロイドは正則マトロイドでもあることが知られています．

bicircularマトロイド

$G = (V,E) $ を無向グラフとして，$\mathcal{F}$ を，$E$の部分集合のうち，その集合のなすどの連結成分も閉路を高々1つしか持たないもの全体からなる集合とすると，$(E, \mathcal{F})$ はマトロイドをなし，これをbicircular マトロイドと呼びます．

gammoid

$G = (V,E) $ を有向(無向)グラフとして， $S, T$ をそれぞれ $V$ の空でない部分集合とします． $\mathcal{F}$ を， $T$ の部分集合 $F$ であって次の条件を満たすもの全体からなる集合とします．

$S$ の各点から $F$ の点への $|F|$ 個のパスであって，どの二つも点素であるものが存在する

このとき， $(E,\mathcal{F})$ はマトロイドをなし，これをgammoidといいます．$T = V$ であるときは，特にstrict gammoidと呼びます．

  • $G$ が無向グラフのとき，「点素である」という条件を「辺素である」としてもマトロイドになります．

横断マトロイド

$G = (V_{1} \cup V_{2} , E)$ を二部グラフとします． $\mathcal{F}$ を，$V_{1}$ の部分集合であって，それに含まれる点を全て含む $G$ のマッチングが存在するようなもの全体からなる集合とすると， $(E,\mathcal{F})$ はマトロイドをなし，これを横断マトロイドと呼びます．

  • マッチングの端点集合を集めたものなので，マッチングマトロイドと呼ぶこともあります．

分割マトロイド

$E = \{1,2,\ldots, n \}$ として， $E_{1},\ldots, E_{m}$ を $E$ の分割とします(つまり，1以上 $n$ 以下の整数はそれぞれ $E_{1},\ldots, E_{m}$ のうちちょうど一つに含まれます) ．また，$ r_{1},\ldots, r_{m}$ を整数とします．$\mathcal{F}$ を，$E$ の部分集合 $F$ であって，各 $i$ に対して $$ |F \cap E_{i}| \leq r_{i} $$ を満たすようなもの全体からなる集合とします．このとき，$(E,\mathcal{F})$ はマトロイドをなし，これを分割マトロイドと呼びます．

カタランマトロイド

$E = \{1,2, \ldots, 2n \}$ として，$\mathcal{F}$ を，$E$ の部分集合 $F$ であって，次の条件を満たすようなもの全体からなる集合とします．

$1$ 以上 $2n$ 以下の任意の整数 $i$ に対して，$i$ 以下の $F$ の元の個数は， $i$ 以下の $E\backslash F$ の元の個数以下である．

このとき， $(E,\mathcal{F})$ はマトロイドをなし，これをカタランマトロイドと呼びます．

  • カタランマトロイドの独立集合は，ある括弧列の左端を含む連続部分列に対応しています． ($F$ の元を ')' に，それ以外の元を '(' に対応させます)

  • カタランマトロイドの基は長さ $2n$ の括弧列に対応しています

  • 商品の単位量ごとの購入と売買，対角線を跨がないグリッド上の経路など，二つの選択のうち一方は他方より多く行えないような構造に適用できます．

ラミナーマトロイド

有限集合 $E$ に対して，集合族 $\mathcal{L} \in 2^{E}$ が次の条件を満たす時，$(E, \mathcal{L})$ はラミナーと呼びます．

任意の二つの集合 $X,Y \in \mathcal{L}$ に対して， $X \backslash Y, Y \backslash X, X \cap Y$ のうちいずれかは空集合である

ラミナー$(E,\mathcal{L})$ と関数 $u : \mathcal{L} \to \mathbb{Z}_{+}$ に対して， $$ \mathcal{F} = \{ F \subset E : すべての L \in \mathcal{L} に対して |F \cap L| \leq u(L) \}$$ と定めると， $(E,\mathcal{F})$ はマトロイドをなし，これをラミナーマトロイドと呼びます．

  • 例えば，根付き木 $G = (V,E)$ の頂点 $v$ に対して，$v$ を根とする部分木の頂点集合を $F(v)$ とすると，$(E, \{ F(v) : v \in V \} )$ はラミナーであり，「各部分木 $T(v)$ との共通部分のサイズが $u(T(v))$ 以下」という条件を満たす $V$ の部分集合全体がラミナーマトロイドをなします．

マトロイドの構成法

マトロイドが与えられた時，それらから新たなマトロイドを作る方法が色々と知られています．

要素数の限定

マトロイド $(E, \mathcal{F})$ と非負整数 $k$ に対して，独立集合の要素数を $k$ 以下に限定して $$ \mathcal{F_{k}} = \{ F \in \mathcal{F} \mid | F | \ \leq k \} $$ と定めると， $(E, \mathcal{F_{k}} ) $ はマトロイドをなします．

制限・縮約

マトロイド $\mathcal{M} = (E, \mathcal{F})$ と $E$ の部分集合 $X$ に対して，独立集合を $X$ に含まれるものに制限して $$ \mathcal{F}|X = \{ F \in \mathcal{F} : F \subset X \} $$ と定めると，$\mathcal{M}|X = (E, \mathcal{F}|X ) $ はマトロイドをなします．これを，マトロイドの $X$ による制限と呼びます．

マトロイド $\mathcal{M} = (E, \mathcal{F})$ と $E$ の独立集合 $S$ に対して， $$ \mathcal{F}\backslash S = \{ F \in E \backslash S : F \cup S \in \mathcal{F} \} $$ と定めると，$\mathcal{M}\backslash S = (E\backslash S, \mathcal{F}\backslash S ) $ はマトロイドをなします．これを，マトロイドの $X$ による縮約と呼びます．

  • マトロイドの制限・縮約は，グラフマトロイドにおいてグラフの辺の開放除去(単純に辺を除去する)・短絡除去(除去する辺の連結部分に含まれる点を1点につぶす)に対応したものになっています．

  • マトロイドの制限と縮約を繰り返して得られるマトロイドを $\mathcal{M}$ のマイナーと呼び，グラフのマイナーのように，どのようなマイナーを持つかでそのマトロイドを特徴付けることができます(例えば，マトロイドが $\mathcal{F}_{2}$ 上の 行列マトロイドであることは，そのマトロイドが一様マトロイド $U_{4}^{2}$ をマイナーに持たないことと同値であることが 知られています*1 )．

双対

マトロイド $\mathcal{M} = (E, \mathcal{F})$ の基全体からなる集合を $\mathcal{B}$ とします．$\mathcal{F}^{\star}$ を， $$ \mathcal{F}^{\star} = \{ F \subset E : F \cap B = \emptyset を満たす B \in \mathcal{B} が存在する \}$$ と定めると，$(E,\mathcal{F}^{\star})$ はマトロイドをなし，これを $(E,\mathcal{F})$ の双対といいます．

別の言い方をすると，マトロイドの双対とは，元のマトロイドの基の補集合を基とするようなマトロイドのことです．よって，2回双対をとると元のマトロイドに戻ります．

  • マトロイドのランク関数を $r$ ，その双対マトロイドのランク関数を $r^{\star}$ とすると，$F \subset E$ に対して $$ r^{\star}(F) = |F| + r(E\backslash F) - r(E) $$ を満たします．よって，元のマトロイドにおいてランクを求められるなら，双対マトロイドでのランクは容易に得られます．
  • 行列マトロイドの双対は行列マトロイドです．
  • 平面グラフ $G$ の双対グラフがなすグラフマトロイドは， $G$ がなすグラフマトロイドの双対と同型です．
  • $G$ が平面グラフでないなら，一般には $G$ のなすグラフマトロイドの双対をとってもグラフマトロイドにはなりません．
  • strict gammoidは横断マトロイドの双対として表せます．*2

直和・合併

二つのマトロイド $(E_{1},\mathcal{F}_{1}), (E_{2},\mathcal{F}_{2})$ であって， $ E_{1} \cap E_{2} = \emptyset $ を満たすものが与えられた時， $$ \mathcal{F}_{1,2} = \{ F_{1}\cup F_{2} : F_{1} \in \mathcal{F}_{1}, F_{2} \in \mathcal{F}_{2} \} $$ と定めると，$(E_{1} \cup E_{2} , \mathcal{F}_{1,2})$ はマトロイドをなし，これをマトロイドの直和と呼びます．

また，二つのマトロイド $(E,\mathcal{F}_{1}), (E,\mathcal{F}_{2})$ に対して， $$ \mathcal{F}_{1,2} = \{ F_{1} \cup F_{2} : F_{1} \in \mathcal{F}_{1}, F_{2} \in \mathcal{F}_{2} \} $$ と定めると，$(E, \mathcal{F}_{1,2})$ はマトロイドをなし，これをマトロイドの合併と呼びます．

  • 分割マトロイドは，いくつかの一様マトロイドの直和として表せます．

独立集合の和集合をとったものはマトロイドになりますが，共通部分集合をとったものは一般にはマトロイドになりません(これをマトロイドの交叉と呼びます)．しかし，最大二部マッチングをはじめ多くの問題がマトロイドの交叉として定式化でき，また，2つのマトロイドの交叉に含まれる独立集合のうち最大重みのものを多項式時間で求めることができます．

マトロイドの最大独立集合を考えるように，与えられたマトロイドの合併に含まれる元数最大の集合を考えることがあります．これはマトロイドの交叉に帰着させることで，多項式時間で得ることができます．これを用いると，例えばグラフから辺素な全域木をいくつとれるかといった問題を扱うことができます．

マトロイド分割問題
$n$ 個のマトロイド $(E, \mathcal{F}_{1}), \ldots, (E,\mathcal{F}_{n})$ が与えられた時， $F_{i} \in \mathcal{F}_{i}$ を用いて $ X = F_{1} \cup \ldots \cup F_{n} $ と表せる $X \in E$ のうち元数最大のものを求める

二部グラフのマッチングによる構成

マトロイド $(E_{1}, \mathcal{F}_{1})$ ，有限集合 $E_{2}$ と，二部グラフ $G = (E_{1} \cup E_{2} , M)$ に対して， $\mathcal{F}_{2}$を次のように定めます． $$ \mathcal{F}_{2} = \{ F_{2} : F_{1} \in \mathcal{F}_{1} であって，F_{1} と F_{2} の間に完全マッチングが存在する \} $$ このとき，$(E_{2} , \mathcal{F}_{2})$ はマトロイドをなします．

  • 横断マトロイドは，$(E_{1}, \mathcal{F}_{1})$ が自由マトロイドのときに構成されるマトロイドです．

関数による構成

マトロイド $(E_{1}, \mathcal{F}_{1})$ と有限集合 $E_{2}$，関数 $f: E_{1} \to E_{2}$ に対して， $$\mathcal{F}_{2} = \{ f(F_{1}) : F_{1} \in \mathcal{F}_{1} \} $$ と定めると，$ (E_{2}, \mathcal{F}_{2}) $ はマトロイドをなします．

  • $e$ から $f(e)$ に辺を張った二部グラフを考えると，二部グラフのマッチングによる構成の特殊ケースであることがわかります．
  • どんな関数でもマトロイド性を保存するところが面白いです．

競プロでの出題例

マトロイドの最大重み独立集合問題または最小重み基問題に帰着されるものが多いです．貪欲で解けるタイプの問題は，正しい貪欲の方法を見つけたりその正当性を証明したりするのが難しいことも多いですが，マトロイド上の最適化問題として定式化できればそれ以降は機械的に解くことができて嬉しいです．

  • yukicoder No.2957

    略解 $X_{i} < Y_{i}$ であるような $i$ に対応するカードは，最初から $C_{i}$ 枚目までに使うとダメージが増えます．各カードと，それまでに使ったカードの枚数を頂点とする二部グラフを考え，各カード $i$ に対して，今まで使ったカードの枚数 ${0,1,\ldots, C_{i}-1}$ を対応させることで，横断マトロイドの最大重み問題に帰着できます．貪欲法を適用する際，カードは $Y_{i}-X_{i}$ の値が大きい順に見ていきます．対応する枚数の集合がどれも $\{0,1,\ldots, C_{i}-1 \}$ の形をしているので，独立性判定の際には，選んだ $i$ のうち $C_{i}$ が小さい方から順にカードを使うことで条件を満たすかを確かめるとよく，これはUnion-Findなどのデータ構造を用いることで高速に判定することができます．$X_{i} \geq Y_{i}$ の場合も同様で，$X_{i} < Y_{i}$ の場合と独立に考えることができます．

  • ABC236 F

    略解 $1$ 以上 $2^{N}-1$ 以下の任意の整数の辛さのカレーが作れることは，選んだ値を2進表記により長さ $N$ のベクトルに対応させたとき，そのうち$\mathbb{F}_{2}$ 上一次独立な $N$ 個のベクトルを選ぶことができることと同値です．そのような選び方は行列マトロイドの基に一対一対応しているので，行列マトロイドの最小重み基問題に帰着できます．独立性判定の際には，選んだベクトルがなす行列のランクを掃き出し法などを用いて計算して，列フルランクであるか確かめるとよいです．

  • ABC250 G

    略解 常に「買った株数」> 「売った株数」である必要があることから，買い方を括弧列に対応させられそうな感じがしてきます．株を買う日と何もしない日を区別するために，株を買う日・何もしない日・株を売る日のそれぞれに ( (, ( ), ) ) を割り当てると，実現可能な買い方の集合とカタランマトロイドの独立集合が1対1に対応することが分かります．よって，カタランマトロイドの最大重み独立集合問題に帰着できます．

  • 2019最強コン予選 E

    略解 各行と各列に対応する頂点を考え，各カードに対して，そのカードが存在する行と列に対応した頂点を繋ぐ辺を引いた二部グラフを考えると，選べるカードの集合は二部グラフ上で各連結成分が閉路を高々1個持つような辺の選び方の集合と1対1に対応することが分かります．よって，bicircular matroid の最大重み独立集合問題に帰着できます． ( *3に詳しいです)

  • ICPC2023Asia J

    略解 ラミナーマトロイドの最小重み基問題に帰着して解くことができます ( *4 に詳しいです)

参考文献

*1:https://www.ieice-hbkb.org/files/12/12gun_02hen_05.pdf

*2:https://www.sciencedirect.com/science/article/pii/0095895673900312

*3:https://maspypy.com/atcoder-jsc2019%E4%BA%88%E9%81%B8-e-card-collector-%EF%BC%88%E3%83%9E%E3%83%88%E3%83%AD%E3%82%A4%E3%83%89%EF%BC%89

*4:https://tokusakurai.hatenadiary.jp/entry/2024/01/14/012042#f-85b9f14a

自作問題3 like ABC conjecture

自作問題 整数論 数オリ

問題の下に元ツイート・補足(若干のネタバレ)・解答-解説(pdf)・類題・余談が載っています。気を付けてください。

 

問題

二つの問題のうちどちらか一つは恐らく未解決です

 nを3以上の正の整数とする。正の整数の組(a_1, a_2, \ldots , a_n)が美しいとは、これらのうちどの2つも異なりかつ互いに素で、しかも a_1+a_2+ \ldots +a_{n-1} = a_n を満たすことをいう。

(1)　任意の3以上の整数nに対し、美しい正の整数の組であって

a_n > \mathrm {rad} (a_1 a_2 \cdots a_n)

をみたすものが無限に存在するか。

 

(2)　任意の3以上の整数nに対し、正の実数kであって任意の美しい正の整数に対して

a_n < \mathrm {rad} (a_1 a_2 \cdots a_n)^k

をみたすものが存在するか。

 

ただし、正の整数cに対し、\mathrm{rad} (c) でcの相異なる素因数の積を表す。

 

難易度： 一方 3- (IMO3番級)　他方 5+ (未解決枠)

 

 

元ツイート

2020/4/1

 

補足

 自作問題は(1)です。(2)はいわゆる強いABC予想を弱めた命題です。

 強いABC予想

任意の美しい整数の組 (a_1 , a_2 , a_3 ) は

a_3 < \mathrm {rad} (a_1 a_2 a_3) ^2

を満たす

 　現時点で、この予想はおろか、指数部分を正の実数 kに拡張した場合の主張も示されていません。(つまり、任意の美しい組に対して  a_3 が \mathrm {rad} (a_1 a_2 a_3) の指数乗で抑えられることが示されていません。) (2)はその主張について項数を増やすところまで緩めたものです。

　ちなみに、「強い」ABC予想と呼称されることが多いですが、(強くない)ABC予想とは別主張のの命題で包含関係は成立しないと思われます。(少なくとも自明な言い換えでは包含していることがいえません)

 

解答-解説

drive.google.com

 

類題

1.  n! + 1 = m^2 は自然数の解を無限に持つか。

ABC予想の主張を使うと解けます

2. n\geq 6 のとき、 x^n + y^n = z^n をみたす自然数の組 (x,y,z) は存在しないことを示せ。

強いABC予想の主張を使うと解けます

3. 任意の 6 以上の偶数は 2 つの奇素数の和で表せるか。

何を使っても解けません

 

余談

あまり見かけない形の問題になりました。かなり構築寄りですが、天才的な発想は必要ないと思います。解答のような抽象的な構築は可能なのですが、具体的な値での構築方法は見つけていません。ただしn=3の場合は (1, 3^{2n-1}, 3^{2n} ) と簡単に構築できます。n \geq 4 の場合は修羅の道だと思います。

ちなみに作成日はエイプリルフールだったので未解決問題っぽい雰囲気の問題を上げようと思ってABC予想っぽい問題を作ったのですが、その2日後にABC予想の査読が完了したというニュースが上がって話題になっていたので震え上がりました。

自作問題1 c^11-1=n^2-449

自作問題 整数論 数オリ

問題の下に元ツイート・解答-解説(pdf)・類題・余談が載っています

問題

方程式

  c^{11} - 1 = n^2 - 449

をみたす整数の組 (c,n) を全て求めよ。

 

難易度：2- (IMO2番級)

 

元ツイート

2019/9/21

 

 

解答-解説

drive.google.com


 

類題

1.  n^7 ＋ 7 が平方数となるような整数nは存在しないことを示せ。(USATST 2008-4)

ほぼ同じ手法で解けます

 

余談

難易度設定は自信が無いのですが一応2番級としておきました。典型と捉えている人にとっては1番級以下に感じるかもしれません。

ちなみに左辺の11乗にあまり意味はありません。定数の値を変えれば、類題のようにほとんどの奇数乗で同じような問題が作れます。

2020JMO本選記

数オリ JMO

　もうJMO本選から6週間近く経っていると考えると早いですね。時期外れですが本選対策や当日の僕の思考状況などについて書いておきます。

 

対策 

　IMO型の問題の演習を続けてきていたので本選の問題形式に触れることはあまりなかったのですが、本選は通ったことも受けたこともなかったので1,2週間前くらいから本選のセットに似た感じのものを時間を計って解く演習をしました。 JMO本選の過去問は直近10年ぐらいは目を通していたので特に解きませんでしたが、手を付けてない場合は良い練習になると思います。

　取りあえずAPMO対策も兼ねてAPMOの過去問を4時間のセットで解くことにしました。制限時間・問題数・難易度共にJMOに近いのでかなり良いセットだと思います。ただ問題が難易度順に並んでいなかったり、問題の後半は年によってかなりの難易度の差があったりします。(最近の年のものはAPMOのホームページに問題ごとの平均点などが載っています)

　他に試してみたのは

・Canada NO...3時間で5問、難易度は全体的にJMOより少し易しい

・Balkan MO...4時間30分で4問、JMOの2~4番位が並んでいる感じ

辺りです。JMO本選には近い方だと思います。

 　ちなみにここら辺の海外の試験問題はArt of Problem Solvingと呼ばれる海外の数学関連のサイトに載っています。(Community)

 

 　あとは幾何が苦手だったのでJMO本選2-3番位の幾何の問題を色々なところから探して解きまくって構図を身につけました。

 

当日

　試験の日は集合時間20分前に会場に着くようにするのがルーティーンになっているのでそうしました。財団のホームページに載っている会場までの所要時間は短すぎると毎回思ってます。

　あと計算用紙と解答用紙がA4だと思って演習していたら本番はB4でした。やけに図を描くスペースが狭いと思っていたらそういうことでした。

　3完－αで通過、3完～＋αで入賞、4完で金だと思って挑みました。

 

 試験問題

1　

　個人的には序盤にNが出るのは嫌なのですが、去年に続いて6連続1Nです。2度あることは3度あるとかいう次元を超えているので諦めるしかありません。

 

　 \sqrt{2^{n+1}+m+4} が整数という条件を見て、去年の1Nで隣り合う平方数の差を不等式評価したことを思い出します。

 

　\sqrt{2^{n+1}} が平方数でnが十分大きい時にこれが2^{\frac{n+1}{2}} と 2^{\frac{n+1}{2}}+1 で挟み込めそう。前者の条件を見てみると、\frac{n^2+1}{2m} が整数よりnが奇数であることから \sqrt{2^{n+1}} は常に平方数で、さらに n \geq \sqrt{m} がいえるので m+4 は  2^{n+1} に対してあまり大きくなれず、方針は正しそうです。

 

 　簡略化のために k=\frac{n+1}{2} と置いて両式に代入して整理すると

　2^k\leq2k^2-2k+4

となり、k がある程度大きいと矛盾がいえます。これは明らかって書きたいけど1番だと厳密に書かないと減点されそうなので数学的帰納法を使って k\leq7 で矛盾を示します。あとは k\geq6 を調べ上げるだけだけど、ここでミスりそうなので慎重に何回か確認します。調べると

　(m,k)=(1,2) , (61,6)

で、非自明な解も自明な解も入っていて正しそうです。答えるのは (m,n) の組なので k を n に変換して終わりです。

 

<感想>

　いつもの1番という感じでした。ちなみにJMO本選の特に1,2番は採点が厳しいことが多いらしいので、今回の数学的帰納法のパートのように一見自明なところもしっかり数学的に示した方がいいと思います。

 

 

2

　ここ5年は偶数年に2Gが置かれていたので、今回も来ると冗談半分で予想してたら本当に来ました。

 

　まず図をきれいに描きます。しばらく図を眺めていると点 Q が完全四辺形 BPCA のミケル点である(構図です)ことが分かります。どこまで詳しく記述すればいいか分からなかったので完全四辺形にミケル点が存在する証明をミケルの定理を使って書きました。これが分かると共円がたくさん出てくるので角度計算が進みます。

　ただこれだけでは結果に辿りつけなさそうなので他に相似や共円などがないかしばらく探してみると、BD=CE=BC が使えそうじゃないかとなり、そこから角度計算と合わせて三角形 QCE と QDB の合同がいえます。すると残りの辺の長さも等しいことがいえ、PQ と BC の交点を H とすると地道な角度計算で BHQ=CHQ=90 が分かるので示されました。

 

＜感想＞

　2番級にしてはやや簡単だったと思います。Gが苦手なので救われました。

　ちなみに、Q がミケル点であることを使わなくても、Q が三角形 ABC の内心で三角形 PBC の垂心であることが分かれば解けるようです。いずれにしても図は大きく綺麗に描いて上記の性質を見つけやすい状態にするといいと思います。

　あとここまで1時間弱で解けたのでこれは川井狙えるかもとか思っていました。(完全な戯言であることが後に分かります)

 

 

3　

　N→N の関数方程式は得意意識があったのでウキウキしながら解き始めました。ただ少し考えると整数論的な考察はあまり意味が無くてどちらかというと整数の離散性が鍵っぽく感じました。

 

　解を探してみます。f(n)=n は解っぽいけど他にもあるかも。見た目的にfは線形っぽいので f(n)=an+b を代入してみると、 f(n)=n+b  (b\geq0)

で成立することがいえました。( これは大嘘で本当は b\geq1 のとき矛盾します) 

 

　まず、与式の左辺の (m-f(n))^2 という項がいかにも m=f(n) をしてほしそうな見た目をしているので代入すると

　2f(n)^2 \geq   f(f(n))^2+n^2

を得ます。式を見た感じ f(n)\leq f(f(n))\leq ... が示せそう。まず f(n) < n のときはそれが成立します。それどころか f(f(n)) < f(n) とより強い評価ができて、よって無限に続く単調減少数列がとれますが f:N→N より下界が存在するはずなので矛盾します。だから

　f(n)\geq n

ですね。幸先の良いスタートを切れた感じがします。解予想はf(n)=n+b (間違っている)だから、f(n)\geq n より g(n)=f(n)-n とおくと g:N→N+{0} でこれが定数関数であることを示すことに帰着されます。

 

 　しかしここから沼にはまります。g(n)=f(n)-n を与式に代入して整理してもかなり複雑な式しか出てきません。この間に4番も考えますが有効な議論ができず。大幅に時間をロスします。しばらく考えて、すでに導いた式にこれを代入してかろうじて

　g(f(n))\leq g(n)

がいえました。f:N→Nと合わせると、f(n)-n,f(f(n))-f(n),... からなる数列の隣り合う二項の差はやがて一定になることがいえます。ただ、n の値によってこの一定になる差の値は異なるのでこれだけではあまり大きな進捗にならなさそうです。また、しばらく色々と代入したりしてfに固定点が存在するなら全部固定点であることが分かりました。

 

　ここからも時間を使って適当に代入します。m=n+1 を代入したときにnが十分大きいと

　g(n+1)> g(n)\Rightarrow g(n)^2\geq 6g(n)+2n+2

がいえます。つまり g(n) を定数とみたときに n が十分大きいと後者の不等式に矛盾するので、何らかの方法で g(n) が小さく抑えられれば g(n+1)=g(n) がいえます。求めたい条件はこれなので進捗したっぽい。さらに m=n+k ( k は正の整数の定数)としても同じことがいえます。

 

　g(n) を小さく抑えたいですが、f:N→N より g(n) が最小値 r をとる n が存在し、そのような n の最小値をとると r \geq1 のときは r に対して十分に大きい整数 m (n に f を有限個かけて得られる数) において

　g(m+k)=g(m)(1\leq k \leq r)

がいえます。これで十分大きい整数に対して g の値が一定であることがいえました。

 

　あとは g の値が小さい方でも一定であることを示したいのですが、ここからさらに詰まり、成果が得られないまま試験終了。

 

　本当は f(n)=n+b(b\geq1) は解ではなく、これは代入で容易に確かめられます。計算ミスをしていたわけです。ちなみにこの解を排除すると十分大きい m に対して g(m)=0 がいえ、g(m)\geq1 だと同じく代入で矛盾が言えます) そして先で示した f の固定点関連の性質より f(n)=n が唯一の解であることが分かります。

 

 ＜感想＞

　嘘を嘘で証明しました。実は予選の f:N→N の問題でも嘘証明をしていて、嘘に気付いてからあの時から何も変わっていないと落胆しました。

 　ちなみに模範解答は m=f(n) を代入した式を整理して

　f(f(n))^2-f(n)^2\leq f(n)^2-n^2

を導いており、そうするとはるかに簡単に g(n),g(f(n)),...  がいずれ0で一定になることがいえます。そこまで強い代入だと思ってなかったので放置していましたが天才かと思いました。一度嵌るとなかなか抜けられなくて、そういう意味では難しい問題だと思います。

 

 

4

 途中から3番と同時並行で考えました。

　(n-1)/6 本だから取りあえず n=7,13,19 あたりで実験してみると確かに条件を満たしそうです。小さい方から6個ずつで同じ規則で構成できるのかなと思って実験を続けますが、大きい n にも通用する構成法が見つかりません。(こういう時は大体値を上下から評価したり帰納的でない構成であることが多いのですが本番では気づけませんでした) 仕方なく解ける望みのある3に時間を割くことにして4を捨てました。

 

<感想>

　自分が沼にはまっている時にどれだけ早く気づいて別方針を立てられるかって大事だと思います。帰納的でない構成でできるそうです。まあ難しいです。言われれば簡単に納得できるのですが。

 

 

5

　問題だけ見て解きませんでした。まあ難しいです。最近のSLP(2015-N7)に似たような問題があったなと思いました。Nだしもしかしたら4より議論が進んだかもしれませんが、5番で正の得点を取った人は居なかったので採点も厳しかったようです。

 

 

　試験開始時は2Gが早く解ければ勝ち、という感じでしたが、自分が解けると思っていた分野で大嵌りしてしまい満足のいかない感じで終わりました。5も面白そうだったので手は付けてみたかったのですが...

　3完出来なかったので試験終了直後はものすごく不安でした。関東会場では3完主張は多くなかったのですが、関西で相当いるという話を聞いて、Twitterで3完報告をしている人数を数えたりもしました。

 

結果

　8-8-4-0-0の20点で優秀賞でした。銅ボーダーが24で金が31だったそうです。順位表を見ると関西勢が17/21で驚きました。去年も2/3くらいが関西だったし、3年後ぐらいには春合宿も関西でやるようになるんじゃないでしょうか。

　結果が出るのは例年2/20頃だったのですが、今年は少し早く2/19にホームページで出ていて、学校の昼休みの時に自分の通過を確認しました。3番のミスにさえ気付けばメダルが狙えたので少し惜しい気もしましたが抜けられた安堵感と春合宿に行ける嬉しさの方が勝っていました。ただ不安で一切のタスクに精が入らなかったあの本選からの1週間は2度と味わいたくないです。

 

 

余談

　東京会場は分からなかったですがお菓子類持ち込み可能の会場もあったみたいですね。実際4時間も試験を受けていると最後の方に腹が減ってきたのでグミなどの軽食は用意しておいた方がいいかもしれません。