Question

【题目】对n个互不相等的正整数，其中任意六个数中都至少存在两个数，使得其中一个能整除另一个.求n的最小值，使得在这n个数中一定存在六个数，其中一个能被另外五个整除.

Answer 1

【答案】见解析

【解析】

所求的最小正整数n＝26.

分两步证明.

第一步 当n≤25时不满足题意,构造如下的25个正整数:

;

一方面，把这25个正整数分成五组.则任意选取六个数都一定会有两个数在同一组.显然，在同一组中的这两个数中的一个能整除另一个.

另一方面，由于每一组数只有5个，因此，所选的六个数必然至少选自两组数，即在所选的六个数中不存在其中一个能被另五个整除的数,所以，当n＝25时不满足题意.

对于n＜25，也可类似地证明.

第二步 当n＝26时满足题意.

如果一数组中的数都在所给定的26个正整数中，将其中最大一个记为a，除a外的25个数中没有a的倍数，且这25个数中所有a的约数都在这组数中，则称这个数组为“好数组”（一个好数组中的数可以只有一个）.

接下来证明:这样的好数组至多有五个.否则，必存在六个好数组.

考虑这六个好数组中的最大数，分别记为a、b、c、d、e、f由题意知这六个数中必然存在一个能整除另一个，不妨记为，即a的约数b不在a所在的好数组中.

这与好数组的定义不符，故好数组至多有五个.

由于好数组至多有五个，而所给的正整数有26个，因此，至少存在一个好数组中有六个数

考虑这个好数组中的最大数.由好数组的定义知，这个数组中至少另有五个数都能整除该数

综上，所求的最小正整数n＝26.