Question

【題目】對n個互不相等的正整數(shù)，其中任意六個數(shù)中都至少存在兩個數(shù)，使得其中一個能整除另一個.求n的最小值，使得在這n個數(shù)中一定存在六個數(shù)，其中一個能被另外五個整除.

Answer 1

【答案】見解析

【解析】

所求的最小正整數(shù)n＝26.

分兩步證明.

第一步 當(dāng)n≤25時不滿足題意,構(gòu)造如下的25個正整數(shù):

;

一方面，把這25個正整數(shù)分成五組.則任意選取六個數(shù)都一定會有兩個數(shù)在同一組.顯然，在同一組中的這兩個數(shù)中的一個能整除另一個.

另一方面，由于每一組數(shù)只有5個，因此，所選的六個數(shù)必然至少選自兩組數(shù)，即在所選的六個數(shù)中不存在其中一個能被另五個整除的數(shù),所以，當(dāng)n＝25時不滿足題意.

對于n＜25，也可類似地證明.

第二步 當(dāng)n＝26時滿足題意.

如果一數(shù)組中的數(shù)都在所給定的26個正整數(shù)中，將其中最大一個記為a，除a外的25個數(shù)中沒有a的倍數(shù)，且這25個數(shù)中所有a的約數(shù)都在這組數(shù)中，則稱這個數(shù)組為“好數(shù)組”（一個好數(shù)組中的數(shù)可以只有一個）.

接下來證明:這樣的好數(shù)組至多有五個.否則，必存在六個好數(shù)組.

考慮這六個好數(shù)組中的最大數(shù)，分別記為a、b、c、d、e、f由題意知這六個數(shù)中必然存在一個能整除另一個，不妨記為，即a的約數(shù)b不在a所在的好數(shù)組中.

這與好數(shù)組的定義不符，故好數(shù)組至多有五個.

由于好數(shù)組至多有五個，而所給的正整數(shù)有26個，因此，至少存在一個好數(shù)組中有六個數(shù)

考慮這個好數(shù)組中的最大數(shù).由好數(shù)組的定義知，這個數(shù)組中至少另有五個數(shù)都能整除該數(shù)

綜上，所求的最小正整數(shù)n＝26.