Question

排成一排的名学生生日的月份均不相同，有名教师，依次挑选这些学生参加个兴趣小组，每个学生恰被一名教师挑选，且保持学生的排序不变，每名教师挑出的学生必须满足生日的月份是逐渐增加或逐渐减少的（挑选一名或两名学生也认为是逐渐增加或逐渐减少的），每名教师尽可能多选学生，对于学生所有可能的排序，求的最小值。

Answer 1

的最小值为。

若，不妨假设这名学生生日的月份分别为，当学生按生日排序为时，存在一名教师至少要挑选前四名学生中的两名，由于这两名学生生日的月份是逐渐减少的，且后六名学生生日的月份均大于前四名学生生日的月份，因此这名教师不可能再挑选后六名学生；在余下的不超过两名教师中，一定存在一名教师至少要挑选第五名至第七名学生中的两名，同理，这名教师不可能再挑选后三名学生；余下的不超过一名教师也不可能挑选后三名学生，矛盾。

下面先证明：对于互不相同的有序实数列，当时，一定存在三个数满足或。

设最大数和最小数分别为，不妨假设。若，则满足；，因为，所以要么在的前面，要么在的后面至少有两个数，不妨假设在的后面有两个数，从而与中一定有一个成立。

引用上面的结论，当时，第一名教师至少可以挑选三名学生；若余下的学生大于等于名，则第二名教师也至少可以挑选三名学生；这时剩下的学生的数目不超过名，可以被两名教师全部挑选，因此，的最小值为。