百科知识

教育/科学

数学竞赛问题（集合问题）：求高手解决集合S={123…，2

2011-10-11 19:53:26朋***
集合S={1,2,3,…，280}，求最小的自然数n，使得S的每个有n个元素的子集都含有5个两两互素的数. (需要详细解题过程) 谢谢！数学竞赛问题（集合问题）：求高手解决集合S={1,2,3,…，280}，求最小的自然数n，使得S的每个有n个元素的子集都含有5个两两互素的数.(需要详细解题过程?

最佳回答

  •   引入一个概念F(N，p），即小于N，仅为素数p倍数、不是小于p的任一素数倍数的数的集合。 在给定N的情况下，F(N,p）包含的元素数随p的增大而递减 2的倍数有140个, |F(280, 2)| = 140 3的倍数有280 / 3 = 93个，其中偶数46个, |F(280, 3)| = 93 - 46 = 47 5的倍数有280 / 5 = 56个，|F(280, 5)| = 56 - 28 -（18 - 9）= 19 7的倍数有280 / 7 = 40个,|F(280, 7)| = 40 - 20 - （13 - 6）- （8 - 4 - （2 - 1））= 10 所以n的最小值 = 140 + 47 + 19 + 10 + 1 = 217个 如果n = 217时，那么任选一个子集，可以证明，必定有5个两两互素者。
       1。如果子集包含1，那么剩余的216个元素至少来自4个F(280, pi)(i = 1, 2, 3, 4, pi为素数)，显然可以选取5个两两互素者 2。如果子集不包含1，那么217个元素至少来自5个F(280, pi)(i = 1, 2, 3, 4, 5, pi为素数)，显然可以选取5个两两互素者 。
      
    2011-10-11 23:12:34
  • 答案是217　　　　　　
    2011-10-12 09:04:31
    • 很赞哦！ (97)

    相关文章