UyHiP趣题:自然数划分中的幂关系

    UyHiP上个月的题目:把所有大于 1 的自然数划分成两个集合,证明至少能在其中一个集合里找到互不相同的三个数 a 、 b 、 c 满足 a^b=c 。然后,试着给出一种划分,使得只有其中一个集合里存在这样的三元组。
    Update: 后一个问题要求两个集合都是无限集。感谢网友 Triple.J 的提醒。

    证明:如果集合 A 里只有有限个数,那就在集合 B 里选两个比集合 A 中的最大数还大的数 a 和 b ,显然 a^b 也在集合 B 里。类似的,若集合 B 里只有有限个数,我们立即可知 A 中存在满足 a^b=c 的三元组。因此,我们只需要讨论两个集合里都有无穷多个数的情况。
    从集合 A 里选一个数 x ,从集合 B 里选一个数 y 。无妨假设 xy 在集合 A 中。在集合 A 中选一个比 xy 大的数 r 。由于集合 A 是无限大的,因此这样的数总存在。由于 r 比 xy 大,因此 x 、 y 、 xy 、 r 、 r^x 、 r^(xy) 这六个数两两不同。为了避免在同一集合里出现满足要求的三元组, r^x 和 r^(xy) 都必须在集合B里面,但这样的话, r^x 、 y 和 r^(xy) 就成了符合要求的三元组了。
    后一个问题则出奇的简单:把所有素数放进一个集合,所有合数放进另一个集合。显然,一个素数不可能是另一个素数的整数次幂

    这个月的题目非常有意思,点击这里围观。

15 条评论

  • 高考完了

    List of solvers里面中国人占了很多耶。

  • primenumber

    简单的数论题。

  • lk_Nicole

    呐呐,我还真没想到素数去……

  • Triple.J

    问题后半部分应该加强要求:划分出来的两个集合都是无限集。
    否则就很无聊:A={2},B={n>2}。

  • Triple.J

    我这里有个问题请教各位.

    【问题】
    给定任何一个大于 2 的整数 n,考虑闭区间 [-n, n] 上所有整数组成的集合 S = {-n,-(n-1),…,0,1,…,n},问是否总存在满足如下要求的分解:
    将 S 中的所有整数 m,都分解成 S 中两个整数 m1, m2 的和的形式,即 m = m1 + m2;
    当 m 取遍 S 时,m1 和 m2 也分别取遍 S;
    另外,0 必须分解成 0 + 0.

    【举例】
    n=3 的其中一种分解方法是
    m: -3 -2 -1 0 1 2 3
    m1:-2 -3 2 0 3 -1 1
    m2:-1 1 -3 0 -2 3 2

  • magic.lin

    不简单的数论题。

  • fs

    你的意思是集合里根本不含0,否则可以-3=-3+0,就平庸了。
    1 = 2-1
    2 = 3-1
    3 = 4-1
    4 = 5-1
    5 = 6-1
    6 = 1+5
    等式两边同时取符号,得到另一半。很有规律,证明很平庸,问题也平庸。

  • fs

    没注意‘分别’,我错了。

  • fs

    博主为嘛不提供删除或者编辑功能呢。。。地核

  • pig_green

    写一个不是很好的证法…反证
    先证所有的平方数不全在同一集合。这显然,4,16,4^16不在同一集合…
    不妨设2与a^2在A,那么a^4,a在B,所以4在A
    再考虑4与b^4,类似可得16在A
    4^2=16矛盾了……

  • wuzhengkai

    被这月题目藐了

    期末考试期间没心情想题目

  • 28.com

    蛮有趣的一道题,呵呵

  • sss正和

    加强版能否成立:将自然数任意分成N个不相交的子集,则至少一个子集中可找到三个不同的自然数a,b,c使得a^b=c成立。试证明之或找出破坏此性质的最小N。

  • www.28.com

    呵呵,受教了,蛮有意思的一道题

发表评论