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.