(z)总存在两个数之和等于另两数之和

realnumber

1到100的自然数中任取k个数,使得这k个数中总存在两个数之和等于另两数之和,求k的最小值.

isee

回复 1# realnumber


    真抽屉原理了：（1，100），（2，99），……，（49，52），（50，51）。
    这样就是52个数了，是否最小，还需证明。

realnumber

回复 2# isee


    不明白,isee解释下

isee

回复  isee


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

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

realnumber

$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左右都不错了.

realnumber

考虑反面，最大可以取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.

realnumber

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

realnumber

回复 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

realnumber

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

2016-6-5 22:18 Upload

Click on the file to download the attachment

isee

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