一道无理数集合问题的图论解法

今天给学生讲了一道2019年百子S8等级的考试题目．

题目： 一个由实数构成的集合称为“幸运集“，若它满足以下性质：

1. 对每个，，数，均不为，且恰好有一个是有理数；
2. 对每个，是无理数．

求幸运集中元素个数的最大可能值．

分析： 条件1给出了幸运集中任意两个不同元素之间的关系：要么和为有理数，要么积为有理数．于是可以想到将其转化为一道简单的图论问题．

对中的两个不同元素和，若，则在和之间连一条红边，若，则在和之间连一条蓝边．

除题目中已给出的外，对于幸运集中任意三个不同元素，，，有以下几个结论：

1. ，，不同时为有理数．否则

   

   与条件2矛盾；
2. ，，不同时为有理数．否则

   与条件2矛盾．

到这里，容易想到拉姆塞问题．因为将中所有边红蓝二染色后，必不存在同色三角形，于是中至多有个元素．然而尝试后发现无法构造出满足题意的五元集合．原因是中的边有更高的要求：

3. （2的加强），不同时为有理数．否则除2的情形外，有．于是

   与条件2矛盾．

于是中不存在红色三角形，且蓝边不相邻．

如果中有不少于个点，则，，，中蓝边至多一条，故至少有三条红边．由拉姆塞问题的证明过程可知必存在红色三角形，矛盾．

如果中有个点，同上分析可知每个点恰连出条红边，条蓝边，且蓝边不相邻．于是一种构造为：红边为，，，；蓝边为，．

即，，，；，．

令，，，即可．

于是幸运集中元素个数的最大可能值为．