Question

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

Answer 1

【答案】見解析

【解析】

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

分兩步證明.

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

;

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

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

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

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

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

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

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

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

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

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

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