Prove that among 2 n + 1 irrational numbers we can choose n + 1 numbers such that the sum of any two chosen numbers is irrational.

Question

Prove that among   2  n  +  1 irrational numbers we can choose   n  +  1 numbers such that the sum of any two chosen numbers is irrational.

meexeniexia17h · Accepted Answer

HINT: Let   X  =  {      x    1    ,  …  ,      x          2      n      +      1        } be the set of irrational numbers. Take   X to be the vertex set of a graph   G whose edges are the pairs   {      x    k    ,      x    ℓ    } such that       x    k    +      x    ℓ    ∈      Q  ; you want to show that   G has an independent set of size   n  +  1. You can do this by showing (by contradiction) that   G has no odd cycle and concluding that   G is bipartite.To show that   G has no odd cycle, suppose that the vertices       x                  i        1              ,  …  ,      x                  i                  2          k          +          1                     form such a cycle. Then the sums      x                  i        1              +      x                  i        2              ,      x                  i        2              +      x                  i        3              ,  …  ,      x                  i                  2          k                      +      x                  i                  2          k          +          1                      ,      x                  i                  2          k          +          1                      +      x                  i        1            are all rational. Now take the alternating sum of these sums:  (      x                  i        1              +      x                  i        2              )  −  (      x                  i        2              +      x                  i        3              )  +  (      x                  i        3              +      x                  i        4              )  −  …  −  (      x                  i                  2          k                      +      x                  i                  2          k          +          1                      )  +  (      x                  i                  2          k          +          1                      +      x                  i        1              )    ;are all rational. Now take the alternating sum of these sums:  (      x                  i        1              +      x                  i        2              )  −  (      x                  i        2              +      x                  i        3              )  +  (      x                  i        3              +      x                  i        4              )  −  …  −  (      x                  i                  2          k                      +      x                  i                  2          k          +          1                      )  +  (      x                  i                  2          k          +          1                      +      x                  i        1              )    ;

Prove that among 2n+1 irrational numbers we can choose n+1 numbers such that the sum of any two chosen numbers is irrational.

Answered question

Answer & Explanation

New Questions in Algebra I