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

解  的最小值为

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

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

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

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

 0  423369  423377  423383  423387  423393  423395  423399  423405  423407  423413  423419  423423  423425  423429  423435  423437  423443  423447  423449  423453  423455  423459  423461  423463  423464  423465  423467  423468  423469  423471  423473  423477  423479  423483  423485  423489  423495  423497  423503  423507  423509  423513  423519  423525  423527  423533  423537  423539  423545  423549  423555  423563  447090 

违法和不良信息举报电话:027-86699610 举报邮箱:58377363@163.com

精英家教网