2022/03/04 21:20 更新
クイズ C-2
35 いいね ブックマーク
目次

問題

問題 C2

$2n+1$個の無理数がある. このうち$n+1$個の無理数を選んでその中のどの2つの和も無理数にすることができることを示せ.

         

$$  $$





ほぼC1の一般化です.
解答は以下.







$$    $$

 

   

解答

 $2n+1$個の無理数をグラフの頂点とみなし, 以下のルールによって辺を張ります.

  • 頂点$i,j$に対し, $i+j$が有理数なら辺$(i,j)$を張る.

 こうして得られたグラフについて考えます. このグラフに奇数サイクル$a_1, a_2, \dots, a_{2m+1}$があったとしましょう. このとき, $a_1+a_2, a_2+a_3, \dots, a_{2m+1}+a_1$は全て有理数ですが, それらの交代和を計算すると

$$(a_1+a_2)-(a_2+a_3) + \cdots -(a_{2m}+a_{2m+1}) + (a_{2m+1}+a_1) = 2a_1$$

となり, $a_1$が無理数であることと矛盾します. よって奇数サイクルは存在せず, 得られたグラフは2部グラフであることがわかります. つまり$2n+1$個の頂点の集合は$U, V$という2つの集合に分割され, $U, V$それぞれの中には辺がありません. 頂点は全部で$2n+1$個あるので$U, V$のうち少なくとも一方は$n+1$個の頂点を持ち, その中の2つの和は全て無理数です.

補足

  • $U, V$は片方が空でも良いです.
  • 一般に$k$個の無理数があったとき, 大体$k/2$個をうまく選んでその中のどの2つの和も無理数にできることが同じように証明できます. (今回は$k$が奇数の場合でした.) この$k/2$という値は最良です. 実際に$k$個の無理数が$(\sqrt 2,-\sqrt 2, \sqrt 2, -\sqrt 2, \dots)$のように与えられる時, $k/2$より多く選ぶと必ず和が$0$, すなわち有理数になるようなペアが存在してしまいます.