根源杯初中二试，任意两数不存在整除关系

12673zf

从$1-200$中选出100个数$a_1<a_2<a_3<\cdots<a_{100}$，使得其中任意两个数之间都不存在整除关系，
（1）求$a_{100}$的最小可能值
（2）求$a_1$的最小可能值
很久没有碰过数论题了，感觉条件很常见，就是不太会用……

realnumber

修改了下,好像可以了.
这样把1~200划分为以101,102,...,200开头的100类
{101}
{102,51}
{103}
{104,52,26,13}
......
{200,100,50,25}(2倍关系在同一个类)
那么每个类,由抽屉原理最多只能取1个,因此互不整除的数最多不超过100个,又101,102,...,200符合互不整除,因此数目恰好是100个.
把其中的134替换为67也符合,更小的替换的话,比如132替换为66,但66的3倍198也 要去掉了,少于100个了,(130,128,...102也同样不能替换)最小$a_1=67$.
    200可以替换为100,199是质数,无法替换,因此最小$a_{100}=199$.完

      问题修改为 1~200取99个互不整除的数,分别求可能最小的$a_{99},a_1$,
最小的$a_{99}$应该是197了,也是除199外的最大的一个素数.最小的$a_1=51$?,再加个坑.

hbghlyj

A subset of size 101 from 1,2,3,…,200 must contain one element which divides another
考虑将这 $2n$ 个数分成 $n$ 组，其中第 $i$ 组为 $\{2^k(2i-1)|1 \le 2^k(2i-1) \le 2n, k \in \mathbf N\}$
由于一个正整数总可以唯一表示成 $x=2^{v_2(x)} \cdot (2k-1)$ 的形式，故 $x$ 会且只会出现在第 $k$ 组
根据鸽巢原理，任意的 $n+1$ 个正整数一定有两个出现在同一组