从 1,2,⋯,2018 中取 k 个不同的数,其中任意 2 个数的商不等于 32,那么 k 的最大值为_______.
答案 1514.
解析 任何一个正整数必然可以写成 2p⋅3q⋅r 的形式,其中 2∤r,3∤r 且 p,q∈N,r∈N∗.按每个正整数对应的 (p,q) 做分划,有p/q012345601,5,7,⋯3,15,21,⋯9,45,63,⋯27,135,189,⋯81,405,567,⋯243,1215,170172912,10,14,⋯6,30,42,⋯18,90,126,⋯54,270,378,⋯⋯⋯145824,20,28,⋯12,60,84,⋯36,180,252,⋯⋯⋯⋯38,40,56,⋯24,120,168,⋯⋯⋯⋯⋯416,80,112,⋯⋯⋯⋯⋯⋯532,160,224,⋯⋯⋯⋯⋯⋯664,320,448,⋯⋯⋯⋯⋯⋯7128,640,896,⋯⋯⋯⋯⋯⋯8256,1280,1792⋯⋯⋯⋯⋯9512⋯⋯⋯⋯⋯101024⋯⋯⋯⋯⋯ 设 x>y 且 x,y∈{1,2,⋯,2018},则 xy=32 等价于 x,y 位于 p+q 的值相等的相邻斜格.下面证明 k 的最大值为 1514.记 N(p,q) 为 (p,q) 对应的格子中的元素个数.
构造 去掉 q=1,3,5 列中的所有格子里的元素,剩下的元素符合题意.考虑到 q 列格子元素个数之和Tq=∑p=0,1,⋯,10N(p,q)=⌊20183q⌋−⌊20183q+1⌋,而q0123456⌊20183q⌋2018672224742482⌊20183q⌋−⌊20183q+1⌋1346448150501662 此时元素个数之和为∑q=0,2,4,6Tq=2+16+150+1346=1514.
论证 考虑 p+q=m(m=0,1,2,⋯,10)的斜格,记为斜格组Um:(0,m),(1,m−1),⋯,(m,0),每个斜格组中的数可以写成 N(0,m) 个数链,如 m=3 的情形,有8,12,18,27;40,60,90,135;56,84,126,189;⋯,长度为 l 的数链中至多取 ⌈l2⌉ 个数,因此至少要去掉的元素个数为∑q=1,3,5Tq=504. 综合所述,k 的最大值为 1514.
备注 长度为奇数的数链取数方法是唯一的,长度为 2n 的数链取数方法有 n+1 种,因此可以在此基础上思考最大集合的个数.长度为 l 的数链个数 n(l) 分别为l1234567n(l)898298100341042因此所求最大集合的个数为 2298⋅334⋅44.