从1~13这13个数字中选出K个,使得其中任意两数字差既不为5也不为8,K最大多少?RT

Question

从1~13这13个数字中选出K个,使得其中任意两数字差既不为5也不为8,K最大多少?
RT

Answer 1

如果存在a,那么a+5和a+8都不能存在,也就是说,对于1,如果存在,那么6和9就不能存在,也就是不能共存,同理,2和7,10不能共存,类推,写成 1(6,9),2(7,10),3(8,11),4(9,12),5(10,13),6(1,11),7(2,12),8(3,13),9(1,4),10(2,5),11(3,6),12(4,7),13(5,8) 那么每次找最小化的情况,因为每个数字都有2个不能共存,所以从中任选一个,如1,那么6和9就不能选择,第二,找到使不能共存最小化的,也就是括号里有6或者9的数,4和11符合题意,选择,现在是1,4,11,类推,可以继续选择到7,8,5 最后是一共有6个,所以K最大是6