(选修4-5)排序不等式课件

2020年9月17日星期四排序不等式问题:已知两组数1,2,3和4,5,6，若123,,ccc是4,5,6的一个排列，则123123ccc的最大值是_____,最小值是_____.32284,5,6只有6种不同的排列:分析:(4,5,6),(4,6,5),(5,4,6),(5,6,4),(6,4,5),(6,5,4),123123Sccc只有6种不同的和式．123456142536321426353115243631152634291624352916253428SSSSSS　　　问题探讨123,,ccc如果的值大一点，结果怎么样？思考:对应关系和备注（1,2,3）（25,30,45）1112233220Sababab（1,2,3）（25,45,30）2112332205Sababab（1,2,3）（30,25,45）3122133215Sababab（1,2,3）（30,45,25）4122331195Sababab（1,2,3）（45,25,30）5132132185Sababab（1,2,3）（45,30,25）6132231180Sababab发现:反序和≤乱序和≤顺序和.顺序和反序和乱序和乱序和乱序和乱序和最大值最小值一般地,设有两组实数:123,,,,naaaa与123,,,,nbbbb,且它们满足:123naaaa,123nbbbb,若123,,,,ncccc是123,,,,nbbbb的任意一个排列,则和1122nnSacacac称为数组123(,,,,)naaaa和123(,,,,)nbbbb的乱序和,其中按相反顺序相乘所得积的和11211nnnSababab称为反序和.按相同顺序相乘所得积的和21122nnSababab称为顺序和.根据直觉你可以得什么不等式?1122nnSacacac11211nnnSababab21122nnSababab定义顺序和乱序和反序和1212naaabbbn当且仅当或时,反序和等于顺序和.（排序不等式，又称排序定理）定理12121212,,,,,,nnnnaaabbcccbbb设，b为两组实数是的任一排列,那么反序和≤乱序和≤顺序和121111221122.........nnnnnnnabababacacacababab．12SSS下面我们来证明，其中11211nnnSababab反序和1122nnSacacac乱序和21122nnSababab顺序和123123,,,,,,,,,nnccccbbbb证:是的任一排列123,,,,!,nbbbbn而的全排列只有个其中必有最大值和最小值.1122:kknnSacacacac考虑和式①1111,(1),.kkcbcbkcc若则有某个1,kcc将①中对换得1221kknnSacacacac②111111()()0kkkkkkSSacacacacaacc③S的值也只有!n有限个(个数),12SSS下面我们来证明，其中11211nnnSababab反序和1122nnSacacac乱序和21122nnSababab顺序和111kacac③式说明:将①中的第一项换为后,1111acab即换为后,和式不减少.112,cbc若则转而考察,并进行类似讨论.1122abab同理,将①中的第一项换为,第二项换为后,和式不减少.,如此继续下去经有限步调整,可知一切和式中,{},ic最大和数只能是数组由小到大排序的情况2SS即最大和数是顺序和,.112,SSSSS同理可证成立．这种证题方法叫做逐步调整法12SSS下面我们来证明，其中11211nnnSababab反序和1122nnSacacac乱序和21122nnSababab顺序和1212nnaaabbb易知,当或时,反序和顺序和，12.SSS从而有1212,,,,,,,nnaaabbb事实上若不全相等,且也不全相等,,(1,,,),ijlkaabbijkln则可找到21122iijjllkknnSababababababab④,,,ijlkbbbb交换中的位置,得到下面两个和式：④*21122ikjllikjnnSababababababab⑤**21122iljklikjnnSababababababab⑥12SSS下面我们来证明，其中11211nnnSababab反序和1122nnSacacac乱序和21122nnSababab顺序和,S显然,两式都符合的形式即它们都是乱序和.⑤⑥***22()()()()ikjliljkikjkjlilSSabababababababab()()()()0,kijljiijklbaabaaaabb***22.SS***1222.SSSS进而得到12,,,,naaa这就是说若不全相等,1212,,,nbbbSS且也不全相等,则，121212nnaaabbbSS当或时,才有,12SSS从而才有.(1,2,,10),10,iiiitt有10个人各拿一只水桶去接水,设水龙头注满　第个人的水桶需要分钟假定这些各不相同.问只有一个水龙头时,应如何安排人的顺序使他们等候的总时间最少?这个最少的总时间等于多少？例1.2299,tt第二桶水需分钟,接这桶水时,人共需分钟3388,tt第三桶水需分钟,接这桶水时,人共需分钟,这是一个实际问题需要转化为数学问题.分析:111010,tt若第一桶水需分钟,则接这桶水时,人共需分钟1010,tt第十桶水需分钟,只有一个人了,只需分钟......12391010982.ttttt等待的总时间(分)是(1,2,,10),10,iiiitt有10个人各拿一只水桶去接水,设水龙头注满　第个人的水桶需要分钟假定这些各不相同.问只有一个水龙头时,应如何安排人的顺序使他们等候的总时间最少?这个最少的总时间等于多少？例1.12391010982.ttttt等待总时间(分)是解:,根据排序不等式10按水桶的由小到大依次接水,人等候的总时间最少,12391010982,ttttt最少总时间是12910.tttt其中12910,tttt当时总时间取最小值，12321222,,,,1111.2323nnaaanaaaann设是个互不相同的正整数求证例2.121212,,,,,,,nnnbbbaaabbb设是的一个排证列,且:12,,,nbbb是互不相同的正整数,2221111,23n又由“乱序和反序和”得3322112222222323nnaabbababnn22211111111231.2323nnn121,2,,.nbbbn,,,,,abcabc把和看作是证两组数:2220,.abcabcabbcca1.已知求证,abc由“顺序和乱序和”得aabbccabbcca，222abcabbcca即．练习:,,,0.abcabc不等式关于对称可设证:222222,,,.222abcRabbccaabccab2.已知　求证222111,,abccba由“反序和乱序和”得222222111111abcabcabcbca①222222111111abcabcabccab②[2①②]即得要证的不等式．练习:45122222112122313.(4),,...,.nnnnnPaaaaaaaaaaaaaa设为正数，试分别用柯西不等式与排序不等式证明用柯西不明证等式证:2211223112231()(),nnnnnaaaaaaaaaaaaaaa222211212231.......nnnnaaaaaaaaaaa2222112231231()()nnnnaaaaaaaaaaaa下面用排序不等式证明．45122222112122313.(4),,...,.......nnnnnPaaaaaaaaaaaaaa设为正数，试分别用柯西不等式与排序不等式证明121212,,,,,,,nnnbbbaaabbb证设是的一个排列,且0:2221212111,,nnbbbbbb则由“乱序和反序和”得222222212112231121111111nnnnnaaaabbbaaaabbb1212,nnbbbaaa222211212231.......nnnnaaaaaaaaaaa即1212naaabbbn当且仅当或时,反序和等于顺序和.（排序不等式，又称排序定理）定理12121212,,,,,,nnnnaaabbcccbbb设，b为两组实数是的任一排列,那么反序和≤乱序和≤顺序和121111221122.........nnnnnnnabababacacacababab．作业:第45页1－3题课堂小结