高级主题测试解决方案advanced-solutions11.pdfVIP

SMT2011AdvancedTopicsTestandSolutionsFebruary19,2011

1.Fivestudentsatameetingremovetheirnametagsandputtheminahat;thefivestudentstheneach

randomlychooseoneofthenametagsfromthebag.Whatistheprobabilitythatexactlyone

getstheirownnametag?

Answer:3

8

Assumewithoutlossofgeneralitythatthefirstgetsacorrectnametag.Let’scalltheother

peopleB,C,D,andE.Wecanorderthefourpeopleinninewayssuchthatnoneofthesgets

hisownnametag;CBED,CDEB,CEBD,DBEC,DEBC,DECB,EBCD,EDBC,EDCB.Therefore,

thedesiredprobabilityis9=3.

4!8

AlternativeSolution:Theselectionofrandomnametagsamountstoaselectionofarandomper-

mutationofthefivestudentsfromthesymmetricgroupS5.Theconditionwillbemetifandonlyif

theselectedpermutationhaactlyonecycleoflengthone(i.e.,exactlyonefixedpoint).Theonly

5!

distinctcycletypeswithexactlyonefixedpointare(1,4)and(1,2,2).Thereare=30permutations

4

5!30+153

ofthefirsttypeand23=15permutationsofthesecond.Thus,thedesiredprobabilityis5!=8.

2.Compute

1

n

X(7n+32)·3n.

n·(n+2)·4