免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] (z)总存在两个数之和等于另两数之和

1到100的自然数中任取k个数,使得这k个数中总存在两个数之和等于另两数之和,求k的最小值.
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

回复 1# realnumber


    真抽屉原理了:(1,100),(2,99),……,(49,52),(50,51)。
    这样就是52个数了,是否最小,还需证明。

TOP

回复 2# isee


    不明白,isee解释下

TOP

回复  isee


    不明白,isee解释下
realnumber 发表于 2016-6-5 14:01



    50组,每组取一个,就是50个数了,再随便取2个,必有两个同组,(相加均为101)。
    52个是否是最小,这里还不知道。只知道,52个数中必有 两个数之和等于另两数之和

TOP

本帖最后由 realnumber 于 2016-6-5 19:03 编辑

$k\le 25$
理由这样,一旦一组(k个)数中,出现三个一样的差,就符合题意思(可惜不是充要条件).
因此必有不等式$C_k^2\le 3\times99$.(最小差是1,最大的差是100-1=99.共99个差)
但实际上只要不是连续四个数,出现2个一样的差,就会符合题目要求,
这样k应该远比25小.由$C_k^2\le 2\times99$,估计16左右都不错了.

TOP

本帖最后由 realnumber 于 2016-6-5 22:26 编辑

考虑反面,最大可以取m个数,使得取出的m个数中,任意四个都不会有2个和等于另外两个和.
考虑这m个数的两两的差,两数差为1,2,3,....,49的允许出现2次(此时出现三数成等差,若是四数a,b,c,d出现a-b=c-d,则有a+d=b+c.),差为50,51,..,99的只能出现一次.
因此有不等式$C_m^2\le 2\times49+50$,解得$m\le 17.$
只需要找出一组具体17个数的数列,就可以说明17最大.如果真的找到,那么1楼问题答案就是k=18.
目前只找到15个数的数列,
1,2,3,5,8,12,17,23,31,39,49,60,72,85,98----有错误,见楼下
虽然没解决,似乎很接近了.1楼答案猜是k=16.

TOP

第一次出现差s,t的话,意味着差s+t也第一次出现.这个似乎也可以改进不等式.

TOP

回复 6# realnumber


    转发:

浙江杭州骆--(37--9)  20:04:06
若两对数的差相等,则只可能为有一个数出现两次,否则两对和相等。
浙江杭州骆--(37--9)  20:06:06
不妨设a+c=2b,a>b>c。对于每个b只对应一组a,c。
浙江杭州骆--(37--9)  20:07:18
k(k-1)/2-(k-2)≤99
b至多有k-2个。
k≤15。
广东刘--(714---11)  20:08:28
最后一个解答例子有误,1.12.49.60

TOP

按1,2,3为初值。
逐步生成最小的数,使得任意两数和不等。
程序出来的数列为12个数,依次为
1,2,3,5,8,13,21,30,39,53,74,95
程序编的很难看,毕竟第一次查到smallbasic怎么用数组.
四数两两和相等问题.sb (444 Bytes)

TOP

这种题看似简单,一做都是泪

TOP

返回列表 回复 发帖