Question

【題目】排成一排的10名學(xué)生生日的月份均不相同.有名教師，依次挑選這些學(xué)生參加個(gè)興趣小組，每名學(xué)生恰被一名教師挑選，且保持學(xué)生的排序不變，每名教師挑出的學(xué)生必須滿足生日的月份是逐漸增加或逐漸減少的（挑選一名或兩名學(xué)生也認(rèn)為是逐漸增加或逐漸減少的），每名教師盡可能多地選學(xué)生.對于學(xué)生所有可能的排序，求的最小值.

Answer 1

【答案】4

【解析】

若，不妨設(shè)這10名學(xué)生生日的月份分別為.

當(dāng)學(xué)生按生日排序?yàn)?,3,2,1,7,6,5,9,8,10時(shí)，存在一名教師至少要挑選前四名學(xué)生中的兩名，由于這兩名學(xué)生生日的月份是逐漸減少的，且后六名學(xué)生生日的月份均大于前四名學(xué)生生日的月份，因此，這名教師不可能再挑選后六名學(xué)生；在余下的不超過兩名教師中，一定存在一名教師至少要挑選第五名至第七名學(xué)生中的兩名.同理，這名教師不可能再挑選后三名學(xué)生；余下的不超過一名教師也不可能挑選后三名學(xué)生，矛盾.

下面證明：對于互不相同的有序?qū)崝?shù)列，當(dāng)時(shí)，一定存在三個(gè)數(shù)滿足或.

設(shè)最大數(shù)、最小數(shù)分別為、.

不妨設(shè).

若，則滿足；.

因?yàn)?/span>，所以，要么在的前面，要么在的后面至少有兩個(gè)數(shù).

不妨設(shè)在的后面有兩個(gè)數(shù).從而，與中一定有一個(gè)成立.

引用上面的結(jié)論，當(dāng)時(shí)，第一名教師至少可以挑選3名學(xué)生；若余下的學(xué)生大于或等于5名，則第二名教師也至少可以挑選3名學(xué)生；這時(shí)，剩下的學(xué)生的數(shù)目不超過4名，可以被兩名教師全部挑選.

因此，的最小值為4.