(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software %%Title: Basic.dvi %%Pages: 13 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips -f Basic.dvi %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2005.02.08:1127 %%BeginProcSet: texc.pro %! /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72 mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{ landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[ matrix currentmatrix{A A round sub abs 0.00001 lt{round}if}forall round exch round exch]setmatrix}N/@landscape{/isls true N}B/@manualfeed{ statusdict/manualfeed true put}B/@copies{/#copies X}B/FMat[1 0 0 -1 0 0] N/FBB[0 0 0 0]N/nn 0 N/IEn 0 N/ctr 0 N/df-tail{/nn 8 dict N nn begin /FontType 3 N/FontMatrix fntrx N/FontBBox FBB N string/base X array /BitMaps X/BuildChar{CharBuilder}N/Encoding IEn N end A{/foo setfont}2 array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/df{/sf 1 N/fntrx FMat N df-tail}B/dfs{div/sf X/fntrx[sf 0 0 sf neg 0 0]N df-tail}B/E{pop nn A definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get }B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub} B/Cdx{Cd A length 1 sub get}B/Ci{Cd A type/stringtype ne{ctr get/ctr ctr 1 add N}if}B/id 0 N/rw 0 N/rc 0 N/gp 0 N/cp 0 N/G 0 N/CharBuilder{save 3 1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx 0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{ rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B /chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{ /cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{ A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse} ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17 {2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{ 1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop} forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{A A length 1 sub A 2 index S get sf div put }if put/ctr ctr 1 add N}B/I{cc 1 add D}B/bop{userdict/bop-hook known{ bop-hook}if/SI save N @rigin 0 0 moveto/V matrix currentmatrix A 1 get A mul exch 0 get A mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N/eop{ SI restore userdict/eop-hook known{eop-hook}if showpage}N/@start{ userdict/start-hook known{start-hook}if pop/VResolution X/Resolution X 1000 div/DVImag X/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4 index cvrs cvn put}for pop 65781.76 div/vsize X 65781.76 div/hsize X}N /p{show}N/RMat[1 0 0 -1 0 0]N/BDot 260 string N/Rx 0 N/Ry 0 N/V{}B/RV/v{ /Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT) (LaserWriter 16/600)]{A length product length le{A length product exch 0 exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot} imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto fill grestore}B/a{moveto}B/delta 0 N/tail{A/delta X 0 rmoveto}B/M{S p delta add tail}B/b{S p tail}B/c{-4 M}B/d{-3 M}B/e{-2 M}B/f{-1 M}B/g{0 M} B/h{1 M}B/i{2 M}B/j{3 M}B/k{4 M}B/w{0 rmoveto}B/l{p -4 w}B/m{p -3 w}B/n{ p -2 w}B/o{p -1 w}B/q{p 1 w}B/r{p 2 w}B/s{p 3 w}B/t{p 4 w}B/x{0 S rmoveto}B/y{3 2 roll p a}B/bos{/SS save N}B/eos{SS restore}B end %%EndProcSet TeXDict begin 40258431 52099146 1000 600 600 (Basic.dvi) @start %DVIPSBitmapFont: Fa cmbx12 12 26 /Fa 26 122 df45 DI49 DII80 D<923807FFC092B512FE0207ECFFC002 1F15F091267FFE0013FC902601FFF0EB1FFF010701C0010713C04990C700017F49486E7F 49486F7E49486F7E49486F7E48496F7E48496F1380A248496F13C0A24819E091C97E4819 F0A248487013F8A3007F19FCA249177FA300FF19FEAD007F19FCA36D17FF003F19F8A300 1F19F06D5EA26C19E06E01FE5B6C912603FF8014C06C6D486D4813804B13E06C9028E01F 83F00F13006C903BF01E00F81FFE90267FF83E90387C3FFC90263FFC3C6D485AD91FFE91 381EFFF0D90FFF021F5B6D01FE5D010194C7FC6D6D6CB45A023F90B512F8020703E01302 02006F1307030713C792C7EA07F8716C130F72131F9538FF80FF96B5FC7114FEA3831AFC A27213F81AF0847213E07213C0721300F001FC48587AC454>I83 D<903801FFE0011F13FE017F6D7E48B612E03A03FE007F F84848EB1FFC6D6D7E486C6D7EA26F7FA36F7F6C5A6C5AEA00F090C7FCA40203B5FC91B6 FC1307013F13F19038FFFC01000313E0000F1380381FFE00485A5B127F5B12FF5BA35DA2 6D5B6C6C5B4B13F0D83FFE013EEBFFC03A1FFF80FC7F0007EBFFF86CECE01FC66CEB8007 D90FFCC9FC322F7DAD36>97 DIIII103 DI<137C48B4FC4813804813C0A24813E0A56C13C0A26C13806C1300EA007C90 C7FCAAEB7FC0EA7FFFA512037EB3AFB6FCA518467CC520>I108 D<90277F8007FEEC0FFCB590263FFFC090387FFF8092 B5D8F001B512E002816E4880913D87F01FFC0FE03FF8913D8FC00FFE1F801FFC0003D99F 009026FF3E007F6C019E6D013C130F02BC5D02F86D496D7EA24A5D4A5DA34A5DB3A7B600 81B60003B512FEA5572D7CAC5E>I<90397F8007FEB590383FFF8092B512E0028114F891 3987F03FFC91388F801F000390399F000FFE6C139E14BC02F86D7E5CA25CA35CB3A7B600 83B512FEA5372D7CAC3E>II<90397FC00FF8B590B57E02C314E002CF14F89139DFC03FFC9139FF001FFE000301FCEB 07FF6C496D13804A15C04A6D13E05C7013F0A2EF7FF8A4EF3FFCACEF7FF8A318F017FFA2 4C13E06E15C06E5B6E4913806E4913006E495A9139DFC07FFC02CFB512F002C314C002C0 91C7FCED1FF092C9FCADB67EA536407DAC3E>I<90387F807FB53881FFE0028313F0028F 13F8ED8FFC91389F1FFE000313BE6C13BC14F8A214F0ED0FFC9138E007F8ED01E092C7FC A35CB3A5B612E0A5272D7DAC2E>114 D<90391FFC038090B51287000314FF120F381FF0 03383FC00049133F48C7121F127E00FE140FA215077EA27F01E090C7FC13FE387FFFF014 FF6C14C015F06C14FC6C800003806C15806C7E010F14C0EB003F020313E0140000F0143F A26C141F150FA27EA26C15C06C141FA26DEB3F8001E0EB7F009038F803FE90B55A00FC5C D8F03F13E026E007FEC7FC232F7CAD2C>III121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fb cmmi5 5 7 /Fb 7 116 df100 D<137013F8A213F013E01300A6EA0F80EA1FC0EA31E01261A2EAC3C01203EA0780 A3EA0F001308EA1E18A213301370EA0FE0EA07800D1D7D9C16>105 DI<3803C0F8380FE3 FE380CFF0F3918FC07803830F80313F01200A23801E007A3EC0F00EA03C0141E6D5A6D5A 3807BFE0EB8F800180C7FCA248C8FCA4EA7FE012FF191A7F911F>112 DI<380F07E0383F8F F83833D81CEA63F038C3E03CEBC07C1203143838078000A448C7FCA4121E120C16127D91 1C>I<137E3801FF80EA0381380703C0380E0780EB0300EA0F80EA07F86CB4FC6C1380EA 000FEA3003127812F8EB0700EAF00EEA7FFCEA1FF012127C911C>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fc cmr5 5 5 /Fc 5 52 df<14E0B0B712C0A3C700E0C7FCB022237C9B2B>43 D48 D<1360EA01E0120F12FF12F1 1201B3A3387FFF80A2111C7B9B1C>III E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fd cmmib10 10 1 /Fd 1 79 df<0103B500C0020FB5FC496E4A1480821C00D900076D9138003F8070031EC7 FC1A3E4A7F033F163C826F6D147C4A7E021E6E1478817114F8DA3E037FDA3C015E836F15 01027C8002786D6C5C163F71130302F87F4A03805B7013C0701407010116E04A6D5D18F0 70EBF80F0103804A03FC90C8FC177F725A0107ED3FFF4A6E131E199E7113BE010F17FE91 C86C5B83A24981011E5F83187F133E013C705AA2181F017C160FD801FC5FB500F81507A2 1803725A51397CB84F>78 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fe cmsy5 5 2 /Fe 2 49 df0 D48 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ff cmex10 10 13 /Ff 13 92 df<1430147014E0EB01C01303EB0780EB0F00A2131E5BA25B13F85B12015B 1203A2485AA3485AA3121F90C7FCA25AA3123EA2127EA6127C12FCB3A2127C127EA6123E A2123FA37EA27F120FA36C7EA36C7EA212017F12007F13787FA27F7FA2EB0780EB03C013 01EB00E0147014301462738226>0 D<12C07E12707E123C7E7EA26C7E6C7EA26C7E7F12 007F1378137CA27FA37FA31480130FA214C0A31307A214E0A6130314F0B3A214E01307A6 14C0A2130FA31480A2131F1400A3133EA35BA2137813F85B12015B485AA2485A48C7FCA2 121E5A12385A5A5A14627C8226>I<12F0B3B3B2043674811C>12 D40 D50 DI<12FCB3B3B3 B3B3B3B3B0B612F0A61C94668237>II< 12FCB3B3B00634668037>I<12FCB3B3B006346A8037>I80 D88 D<007C1A1FA200FEF23F80B3B3B3B3A76C1A7FA26C1B00A26D61A2003F626D1801A2001F 626D1803A26C6C4E5A6D180F0007626C6C4E5A6D183F6C6C4E5A6C6D4D5A6E5E6D6C4C90 C7FCD93FF8EE0FFE6D6C4C5A6DB4EE7FF86D01C04A485A6D01F002075B6D01FC021F5B90 28007FFFE003B5C8FC6E90B65A020F16F8020316E002001680033F4AC9FC030714F09226 003FFECAFC51747B7F5C>91 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fg lasy10 10 1 /Fg 1 51 df<003FB712FEB9FCA300F0C9120FB3B3A4B9FCA4303079B43E>50 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fh cmti10 10 48 /Fh 48 123 df<04FFEB03F003039038E00FFC923A0FC0F01F1E923A3F00783E0F923A7E 01F87C3FDB7C03EBFC7F03FC14F8DA01F813F905F1137EDC01E1133C913B03F00003F000 A314074B130760A3140F4B130F60A3010FB812C0A3903C001F80001F8000A3023F143F92 C790C7FCA44A5C027E147EA402FE14FE4A5CA413014A13015FA313034A13035FA313074A 495AA44948495AA44948495AA3001CD9038090C8FC007E90380FC03F013E143E00FE011F 5B133C017C5C3AF8780F01E0D878F0EB07C0273FE003FFC9FC390F8000FC404C82BA33> 11 DI< 150C151C153815F0EC01E0EC03C0EC0780EC0F00141E5C147C5C5C495A1303495A5C130F 49C7FCA2133EA25BA25BA2485AA212035B12075BA2120F5BA2121FA290C8FCA25AA2123E A2127EA2127CA412FC5AAD1278A57EA3121C121EA2120E7EA26C7E6C7EA212001E5274BD 22>40 D<140C140E80EC0380A2EC01C015E0A2140015F0A21578A4157C153CAB157CA715 FCA215F8A21401A215F0A21403A215E0A21407A215C0140F1580A2141F1500A2143EA25C A25CA2495AA2495A5C1307495A91C7FC5B133E133C5B5B485A12035B48C8FC120E5A1278 5A12C01E527FBD22>I44 D<387FFFF8A2B5FCA214 F0150579941E>I<120EEA3F80127F12FFA31300127E123C0909778819>I<151815381578 15F0140114031407EC0FE0141F147FEB03FF90383FEFC0148FEB1C1F13001580A2143FA2 1500A25CA2147EA214FEA25CA21301A25CA21303A25CA21307A25CA2130FA25CA2131FA2 5CA2133FA291C7FC497EB61280A31D3877B72A>49 DI65 D<0107B612FCEFFF8018C0903B000FF0001FF04BEB07F81703021F15FC17014B14FEA202 3F1400A24B1301A2147F18FC92C7120318F84A140718F04AEC0FE0EF1FC00101ED3F80EF 7F004AEB01FEEE07F849B612E05F9139F80007F0EE01FC01076E7E177F4AEC3F80A2010F 16C0171F5CA2131F173F5CA2133FEF7F805C1800017F5D4C5A91C7485A5F49140FEE1FE0 494A5A00014AB45AB748C7FC16F816C037397BB83A>I<0107B8FCA3903A000FF000034B EB007F183E141F181E5DA2143FA25D181C147FA29238000380A24A130718004A91C7FC5E 13015E4A133E167E49B512FEA25EECF8000107147C163C4A1338A2010F147818E04A1370 1701011F16C016004A14031880013F150718004A5CA2017F151E173E91C8123C177C4915 FC4C5A4914070001ED7FF0B8FCA25F38397BB838>69 D<0107B712FEA3903A000FF00007 4B1300187C021F153CA25DA2143FA25D1838147FA292C8FCEE03804A130718004A91C7FC A201015CA24A131E163E010314FE91B5FC5EA2903807F800167C4A1378A2130FA24A1370 A2011F14F0A24A90C8FCA2133FA25CA2137FA291CAFCA25BA25B487EB6FCA337397BB836 >II<0103B5D8F80FB512E0A390260007F8C7381FE0004B5DA2020F153F615DA202 1F157F96C7FC5DA2023F5D605DA2027F14016092C7FCA24A1403605CA249B7FC60A202FC C712070103150F605CA20107151F605CA2010F153F605CA2011F157F95C8FC5CA2013F5D 5F5CA2017F14015F91C7FC491403007FD9FE01B512F8B55BA243397CB83E>I<0103B512 F8A390390007F8005DA2140FA25DA2141FA25DA2143FA25DA2147FA292C7FCA25CA25CA2 1301A25CA21303A25CA21307A25CA2130FA25CA2131FA25CA2133FA25CA2137FA291C8FC 497EB6FCA25C25397CB820>I<0107B512FCA25E9026000FF8C7FC5D5D141FA25DA2143F A25DA2147FA292C8FCA25CA25CA21301A25CA21303A25CA21307A25CA2130F170C4A141C A2011F153C17384A1478A2013F157017F04A14E01601017F140317C091C71207160F49EC 1F80163F4914FF000102071300B8FCA25E2E397BB834>76 D<902603FFF891B512E0A281 D90007923807F8006F6E5A61020F5E81DA0E7F5DA2021E6D1307033F92C7FC141C82DA3C 1F5C70130EEC380FA202786D131E0307141C147082DAF003143C70133814E0150101016E 1378030014705C8201036E13F0604A1480163F010715C1041F5B91C7FC17E149EC0FE360 010E15F31607011E15FF95C8FC011C80A2013C805F1338160013785F01F8157CEA03FC26 7FFFE0143CB51538A243397CB83E>78 D<0107B612F817FF1880903B000FF0003FE04BEB 0FF0EF03F8141FEF01FC5DA2023F15FEA25DA2147FEF03FC92C7FCA24A15F817074A15F0 EF0FE01301EF1FC04AEC3F80EFFE0001034A5AEE0FF091B612C04CC7FCD907F8C9FCA25C A2130FA25CA2131FA25CA2133FA25CA2137FA291CAFCA25BA25B1201B512FCA337397BB8 38>80 D<92383FC00E913901FFF01C020713FC91391FC07E3C91393F001F7C027CEB0FF8 4A130749481303495A4948EB01F0A2495AA2011F15E091C7FCA34915C0A36E90C7FCA280 6D7E14FCECFF806D13F015FE6D6D7E6D14E0010080023F7F14079138007FFC150F150315 01A21500A2167C120EA3001E15FC5EA3003E4A5AA24B5AA2007F4A5A4B5A6D49C7FC6D13 3ED8F9F013FC39F8FC03F839F07FFFE0D8E01F138026C003FCC8FC2F3D7ABA2F>83 D<0007B812E0A25AD9F800EB001F01C049EB07C0485AD900011403121E001C5C003C1780 1403123800785C00701607140700F01700485CA2140FC792C7FC5DA2141FA25DA2143FA2 5DA2147FA292C9FCA25CA25CA21301A25CA21303A25CA21307A25CA2130FA25CEB3FF000 7FB512F8B6FCA2333971B83B>I<003FB539800FFFFEA326007F80C7EA7F8091C8EA3F00 173E49153CA2491538A20001167817705BA2000316F05F5BA2000715015F5BA2000F1503 5F5BA2001F150794C7FC5BA2003F5D160E5BA2007F151E161C90C8FCA2163C4815385A16 781670A216F04B5A5E1503007E4A5A4BC8FC150E6C143E6C6C5B15F0390FC003E03907F0 1FC00001B5C9FC38007FFCEB1FE0373B70B83E>II<14 F8EB07FE90381F871C90383E03FE137CEBF801120148486C5A485A120FEBC001001F5CA2 EA3F801403007F5C1300A21407485C5AA2140F5D48ECC1C0A2141F15831680143F158700 7C017F1300ECFF076C485B9038038F8E391F0F079E3907FE03FC3901F000F0222677A42A >97 D<133FEA1FFFA3C67E137EA313FE5BA312015BA312035BA31207EBE0F8EBE7FE9038 EF0F80390FFC07C013F89038F003E013E0D81FC013F0A21380A2123F1300A214075A127E A2140F12FE4814E0A2141F15C05AEC3F80A215005C147E5C387801F8007C5B383C03E038 3E07C0381E1F80D80FFEC7FCEA01F01C3B77B926>I<147F903803FFC090380FC1E09038 1F0070017E13784913383901F801F83803F003120713E0120FD81FC013F091C7FC485AA2 127F90C8FCA35A5AA45AA3153015381578007C14F0007EEB01E0003EEB03C0EC0F806CEB 3E00380F81F83803FFE0C690C7FC1D2677A426>II<147F903803FFC090380FC1E0 90383F00F0017E13785B485A485A485A120F4913F8001F14F0383F8001EC07E0EC1F8039 7F81FF00EBFFF891C7FC90C8FC5A5AA55AA21530007C14381578007E14F0003EEB01E0EC 03C06CEB0F806CEB3E00380781F83803FFE0C690C7FC1D2677A426>IIIII<150E153F157FA3157E151C1500ABEC1F80EC7FC0ECF1F0EB01C090 380380F813071401130F130E131EEB1C03133C013813F0A2EB0007A215E0A2140FA215C0 A2141FA21580A2143FA21500A25CA2147EA214FEA25CA21301A25CA213035C121C387E07 E0A238FE0FC05C49C7FCEAF83EEA787CEA3FF0EA0FC0204883B619>IIIII<147F903803FFC090380FC1F090381F 00F8017E137C5B4848137E4848133E0007143F5B120F485AA2485A157F127F90C7FCA215 FF5A4814FEA2140115FC5AEC03F8A2EC07F015E0140F007C14C0007EEB1F80003EEB3F00 147E6C13F8380F83F03803FFC0C648C7FC202677A42A>I<9039078007C090391FE03FF0 90393CF0787C903938F8E03E9038787FC00170497EECFF00D9F0FE148013E05CEA01E113 C15CA2D80003143FA25CA20107147FA24A1400A2010F5C5E5C4B5A131F5EEC80035E013F 495A6E485A5E6E48C7FC017F133EEC70FC90387E3FF0EC0F8001FEC9FCA25BA21201A25B A21203A25B1207B512C0A3293580A42A>I<3903C003F0390FF01FFC391E783C0F381C7C 703A3C3EE03F8038383FC0EB7F800078150000701300151CD8F07E90C7FCEAE0FE5BA212 0012015BA312035BA312075BA3120F5BA3121F5BA3123F90C9FC120E212679A423>114 D<14FE903807FF8090380F83C090383E00E04913F00178137001F813F00001130313F0A2 15E00003EB01C06DC7FC7FEBFFC06C13F814FE6C7F6D13807F010F13C01300143F141F14 0F123E127E00FE1480A348EB1F0012E06C133E00705B6C5B381E03E06CB45AD801FEC7FC 1C267AA422>II<13F8D8 03FEEB01C0D8078FEB03E0390E0F8007121E121C0038140F131F007815C01270013F131F 00F0130000E015805BD8007E133FA201FE14005B5D120149137EA215FE120349EBFC0EA2 0201131E161C15F813E0163CD9F003133814070001ECF07091381EF8F03A00F83C78E090 393FF03FC090390FC00F00272679A42D>I<01F0130ED803FC133FD8071EEB7F80EA0E1F 121C123C0038143F49131F0070140FA25BD8F07E140000E08013FEC6485B150E12015B15 1E0003141C5BA2153C000714385B5DA35DA24A5A140300035C6D48C7FC0001130E3800F8 3CEB7FF8EB0FC0212679A426>I<01F01507D803FC903903801F80D8071E903907C03FC0 D80E1F130F121C123C0038021F131F49EC800F00701607A249133FD8F07E168000E0ED00 0313FEC64849130718000001147E5B03FE5B0003160E495BA2171E00070101141C01E05B 173C1738A217781770020314F05F0003010713016D486C485A000190391E7C07802800FC 3C3E0FC7FC90393FF81FFE90390FE003F0322679A437>I<903907E007C090391FF81FF8 9039787C383C9038F03E703A01E01EE0FE3803C01F018013C0D8070014FC481480000E15 70023F1300001E91C7FC121CA2C75AA2147EA214FEA25CA21301A24A1370A2010314F016 E0001C5B007E1401010714C000FEEC0380010F1307010EEB0F0039781CF81E9038387C3C 393FF03FF03907C00FC027267CA427>I<13F0D803FCEB01C0D8071EEB03E0D80E1F1307 121C123C0038140F4914C01270A249131FD8F07E148012E013FEC648133F160012015B5D 0003147E5BA215FE00075C5BA214015DA314035D14070003130FEBF01F3901F87FE03800 7FF7EB1FC7EB000F5DA2141F003F5C48133F92C7FC147E147C007E13FC387001F8EB03E0 6C485A383C1F80D80FFEC8FCEA03F0233679A428>I<903903C0038090380FF007D91FF8 1300496C5A017F130E9038FFFE1E9038F83FFC3901F007F849C65A495B1401C7485A4A5A 4AC7FC141E5C5C5C495A495A495A49C8FC131E5B49131C5B4848133C4848133849137800 0714F8390FF801F0391FFF07E0383E1FFFD83C0F5B00785CD8700790C7FC38F003FC38E0 00F021267BA422>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fi cmbx12 14.4 25 /Fi 25 124 df<157815FC14031407141F14FF130F0007B5FCB6FCA2147F13F0EAF800C7 FCB3B3B3A6007FB712FEA52F4E76CD43>49 DI<9138 0FFFC091B512FC0107ECFF80011F15E090263FF8077F9026FF800113FC4848C76C7ED803 F86E7E491680D807FC8048B416C080486D15E0A4805CA36C17C06C5B6C90C75AD801FC16 80C9FC4C13005FA24C5A4B5B4B5B4B13C04B5BDBFFFEC7FC91B512F816E016FCEEFF80DA 000713E0030113F89238007FFE707E7013807013C018E07013F0A218F8A27013FCA218FE A2EA03E0EA0FF8487E487E487EB57EA318FCA25E18F891C7FC6C17F0495C6C4816E001F0 4A13C06C484A1380D80FF84A13006CB44A5A6CD9F0075BC690B612F06D5D011F15800103 02FCC7FCD9001F1380374F7ACD43>I<171F4D7E4D7EA24D7EA34C7FA24C7FA34C7FA34C 7FA24C7FA34C8083047F80167E8304FE804C7E03018116F8830303814C7E03078116E083 030F814C7E031F81168083033F8293C77E4B82157E8403FE824B800201835D840203834B 800207835D844AB87EA24A83A3DA3F80C88092C97E4A84A2027E8202FE844A82010185A2 4A820103854A82010785A24A82010F855C011F717FEBFFFCB600F8020FB712E0A55B547B D366>65 D69 D<932601FFFCEC01C0047FD9FFC013030307B600F81307033F03FE131F92B8EA803F0203 DAE003EBC07F020F01FCC7383FF0FF023F01E0EC0FF94A01800203B5FC494848C9FC4901 F8824949824949824949824949824990CA7E494883A2484983485B1B7F485B481A3FA248 49181FA3485B1B0FA25AA298C8FC5CA2B5FCAE6C057FB712E0A280A36C94C7003FEBC000 A36C7FA36C7FA27E6C7FA26C7F6C7FA26D7E6D7F6D7F6D6D5E6D7F6D01FC93B5FC6D13FF 6D6C6D5C6E01F0EC07FB020F01FEEC1FF10203903AFFF001FFE0020091B6EAC07F033FEE 001F030703FC1307DB007F02E01301040149CAFC5B5479D26A>71 D85 DI97 DI<913801FFF8021FEBFF8091B612 F0010315FC010F9038C00FFE903A1FFE0001FFD97FFC491380D9FFF05B4817C048495B5C 5A485BA2486F138091C7FC486F1300705A4892C8FC5BA312FFAD127F7FA27EA2EF03E06C 7F17076C6D15C07E6E140F6CEE1F806C6DEC3F006C6D147ED97FFE5C6D6CEB03F8010F90 38E01FF0010390B55A01001580023F49C7FC020113E033387CB63C>I<4DB47E0407B5FC A5EE001F1707B3A4913801FFE0021F13FC91B6FC010315C7010F9038E03FE74990380007 F7D97FFC0101B5FC49487F4849143F484980485B83485B5A91C8FC5AA3485AA412FFAC12 7FA36C7EA37EA26C7F5F6C6D5C7E6C6D5C6C6D49B5FC6D6C4914E0D93FFED90FEFEBFF80 903A0FFFC07FCF6D90B5128F0101ECFE0FD9003F13F8020301C049C7FC41547CD24B>I< 913803FFC0023F13FC49B6FC010715C04901817F903A3FFC007FF849486D7E49486D7E48 49130F48496D7E48178048497F18C0488191C7FC4817E0A248815B18F0A212FFA490B8FC A318E049CAFCA6127FA27F7EA218E06CEE01F06E14037E6C6DEC07E0A26C6DEC0FC06C6D 141F6C6DEC3F806D6CECFF00D91FFEEB03FE903A0FFFC03FF8010390B55A010015C0021F 49C7FC020113F034387CB63D>I103 DI<137F497E000313E0487FA2487FA76C5BA26C5BC613806DC7FC 90C8FCADEB3FF0B5FCA512017EB3B3A6B612E0A51B547BD325>I110 D<913801FFE0021F13FE91B612C0010315F0010F9038807FFC903A1FFC000FFED97FF86D 6C7E49486D7F48496D7F48496D7F4A147F48834890C86C7EA24883A248486F7EA3007F18 80A400FF18C0AC007F1880A3003F18006D5DA26C5FA26C5F6E147F6C5F6C6D4A5A6C6D49 5B6C6D495B6D6C495BD93FFE011F90C7FC903A0FFF807FFC6D90B55A010015C0023F91C8 FC020113E03A387CB643>I<903A3FF001FFE0B5010F13FE033FEBFFC092B612F002F301 017F913AF7F8007FFE0003D9FFE0EB1FFFC602806D7F92C76C7F4A824A6E7F4A6E7FA271 7FA285187F85A4721380AC1A0060A36118FFA2615F616E4A5BA26E4A5B6E4A5B6F495B6F 4990C7FC03F0EBFFFC9126FBFE075B02F8B612E06F1480031F01FCC8FC030313C092CBFC B1B612F8A5414D7BB54B>I<90397FE003FEB590380FFF80033F13E04B13F09238FE1FF8 9139E1F83FFC0003D9E3E013FEC6ECC07FECE78014EF150014EE02FEEB3FFC5CEE1FF8EE 0FF04A90C7FCA55CB3AAB612FCA52F367CB537>114 D<903903FFF00F013FEBFE1F90B7 FC120348EB003FD80FF81307D81FE0130148487F4980127F90C87EA24881A27FA27F01F0 91C7FC13FCEBFFC06C13FF15F86C14FF16C06C15F06C816C816C81C681013F1580010F15 C01300020714E0EC003F030713F015010078EC007F00F8153F161F7E160FA27E17E07E6D 141F17C07F6DEC3F8001F8EC7F0001FEEB01FE9039FFC00FFC6DB55AD8FC1F14E0D8F807 148048C601F8C7FC2C387CB635>I<143EA6147EA414FEA21301A313031307A2130F131F 133F13FF5A000F90B6FCB8FCA426003FFEC8FCB3A9EE07C0AB011FEC0F8080A26DEC1F00 15806DEBC03E6DEBF0FC6DEBFFF86D6C5B021F5B020313802A4D7ECB34>I<007FB500F0 90387FFFFEA5C66C48C7000F90C7FC6D6CEC07F86D6D5C6D6D495A6D4B5A6F495A6D6D91 C8FC6D6D137E6D6D5B91387FFE014C5A6E6C485A6EEB8FE06EEBCFC06EEBFF806E91C9FC A26E5B6E5B6F7E6F7EA26F7F834B7F4B7F92B5FCDA01FD7F03F87F4A486C7E4A486C7E02 0F7FDA1FC0804A486C7F4A486C7F02FE6D7F4A6D7F495A49486D7F01076F7E49486E7E49 486E7FEBFFF0B500FE49B612C0A542357EB447>120 DI123 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fj cmmi7 7 25 /Fj 25 122 df14 D<14FCEB03FF903807878090381E03C0EB3C01017813E0A213F0000114F013E01203 A23907C003E0A4390F8007C0A21580EC0F00EA1F00141E6D5A6D5A383EE1F0EB7FC0011F C7FC90C8FC5AA45AA45A5A1C267D9922>26 D<1238127C12FE12FFA2127F123B1203A312 06A3120C121812381270122008127A8614>59 D<160E163E16FEED03F8ED0FE0ED3F80ED FE00EC03F8EC0FE0EC3F8002FEC7FCEB03F8EB0FE0EB3F8001FEC8FCEA03F8EA0FE0EA3F 8000FEC9FC12F812FEEA3F80EA0FE0EA03F8EA00FEEB3F80EB0FE0EB03F8EB00FEEC3F80 EC0FE0EC03F8EC00FEED3F80ED0FE0ED03F8ED00FE163E160E27277AA134>II<4B7E1503150782 150F151FA2153FA2156F15CF82EC0187140315071406140E140C02187FA2EC30031460A2 14C013011480D903007F91B5FC5B90380C0001A25B13380130805B01E013005B12011203 000F4A7ED8FFF890381FFFE0A22B2A7DA932>65 D<4AB41308020FEBE01891397F80F038 903A01F8001870D903E0EB0CF0D90F80130749C71203013E15E05B491401485A484815C0 485A120F5B001F168090C8FC4892C7FCA2127EA4127C12FCA21606007C5DA35E007E5D12 3E5E6C5D6C6C495A00074AC7FCD803E0130E6C6C13383900FE01F090383FFFC0D907FCC8 FC2D2A7DA830>67 D<013FB612F0A2903901FC00074A1301160001031560A25CA21307A2 5CED0180010F0103130093C7FC14C05D131F151EECFFFEA290383F801E150C1400A24913 1C1518137E92C8FC13FEA25BA21201A25BA21203B512F0A22C287DA72A>70 D<90383FFFF0A2903801FC005CA21303A25CA21307A25CA2130FA25CA2131FA25CA2133F A291C7FCA25BA2137EA213FEA25BA21201A25BA21203B512C0A21C287DA71D>73 D<91387FFFE0A2913800FE005DA214015DA314035DA314075DA3140F5DA3141F5DA3143F 92C7FCA35C001E137E127FA214FE00FE5B387E01F8387803F0387007E0383C1FC0D81FFF C8FCEA03F823297CA725>I<90263FFFF0EB7FF8A2D901FCC7EA1FC04AEC1E005F010315 704C5A4AEB03804CC7FC0107141C5E4A13E04B5A010FEB0780030EC8FC4A5A157C011F13 FE14C3EC877F149E90393FB83F8014F09138C01FC0148049486C7EA2017E6D7EA201FE6D 7EA2496D7EA200016E7EA249147FA2000382B539C007FFF8A235287DA738>I78 D<91381FE0089138FFFC18 903903E01E3890390780077090390E0003F0491301491300017814E0137013F0A2000115 C0A216007F7F6CB47E14F86DB47E6D13F06D7F01077F01007F1407EC00FF153F81A30018 80A20038141E12300038141C153C00781438007C5C007E5C0077EB03C026E3E00FC7FC38 C0FFFE38801FF0252A7CA829>83 D<3B7FFFE003FFF0A2D803F8C7EA3E0049143C161800 07153816305BA2000F157016605BA2001F15E05E5BA2003F14015E90C7FCA248140393C7 FC127EA200FE5C15065AA2150E150C151C5D007C5C5D6C495A003F495A261F800FC8FC38 07C07C3801FFF038007F802C297BA72D>85 D<143C147E14E6EB01C3EB038313071402EB 0F06130E131EA2EB3E0C133CEB7C18A2EB783013F8146014E03801F0C0EBF180EBF30013 F7EA03E613EC13F85B5B5BA31207120F121B123300E313040043130E0001131C14383800 E0E0EBF7C0EB7F00182A7FA81C>96 DI<15F8141FA2EC01F0A21403A215E0A21407A215 C0A2140FEB1F8F90387FCF80EBF0EF3803C03FEA0780390F001F00A2001E5B123E003C13 3E127C147E5A147CA214FC5AECF830A3903801F060A2EA7803010E13C0393C1CF980381F F07F3907C01E001D297CA723>100 D<130E131F5BA2133E131C90C7FCA7EA03E0487EEA 0C78EA187C1230A212605B12C0A2EA01F0A3485AA2485AA2EBC180EA0F81A2381F0300A2 13066C5A131CEA07F06C5A11287DA617>105 D<1407EC0F80141FA21500140E91C7FCA7 EB03E0EB07F8EB0C3C1318EB303E136013C0A248485AA2C7FCA25CA4495AA4495AA4495A A4495AA21238D87C1FC7FC12FC133E485AEA70F8EA7FE0EA1F80193380A61B>I<133EEA 07FEA2EA007CA213FCA25BA21201A25BA21203EC07809038E01FC0EC38600007EB61E014 C3EBC187EBC307D80FC613C09038CC038001B8C7FC13E0487E13FEEB3F80EB0FC0486C7E 1303003E1460A2127EECC0C0127CECC18012FC903801E30038F800FE0070137C1B297CA7 23>I<3B07801FC007E03B0FE07FF01FF83B18F0E0F8783C3B30F1807CE03E903AFB007D 801ED860FEEB3F005B49133E00C14A133E5B1201A24848495BA35F4848485A1830EE01F0 A23C0F8003E003E060A218C0933801E180271F0007C013E3933800FF00000E6D48137C34 1B7D993B>109 D<3907801FC0390FE07FF03918F0E0F83930F1807CEBFB00D860FE133C 5B5B00C1147C5B1201A248485BA34A5AEA07C01660EC03E0A23A0F8007C0C0A2EDC18091 3803C300D81F0013C7EC01FE000EEB00F8231B7D9929>I<9038F007C03901FC1FF03903 1E78780006EBE03C90381FC01C000CEB801E14005B0018141F133E1200137E153E137CA2 13FC157C5B1578000114F0A2EC01E0EC03C03903FC07809038FE1F00EBE7FCEBE1F0D807 E0C7FCA25BA2120FA25B121FEAFFF8A22025809922>112 D<90387C03C03901FF0FF039 07079C30390E03B078000CEBF0F8001813E1123015F0396007C0E015001200A2495AA449 C7FC15301238007C1460EAFC3E15C0EAF87E39F06F03803970C70700383F83FE381F01F8 1D1B7D9926>120 DI E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fk cmr7 7 9 /Fk 9 62 df<1306130C13181330136013E0EA01C0EA0380A2EA07005A120E121EA2121C 123CA35AA512F85AAB7E1278A57EA3121C121EA2120E120F7EEA0380A2EA01C0EA00E013 6013301318130C13060F3B7AAB1A>40 D<12C012607E7E7E120E7EEA0380A2EA01C013E0 120013F0A213701378A3133CA5133E131EAB133E133CA51378A3137013F0A213E0120113 C0EA0380A2EA0700120E120C5A5A5A5A0F3B7DAB1A>I<140EB3A2B812E0A3C7000EC8FC B3A22B2B7DA333>43 D48 D<13381378EA01F8121F12FE12E01200B3AB487E B512F8A215267BA521>I<13FF000313E0380E03F0381800F848137C48137E00787F12FC 6CEB1F80A4127CC7FC15005C143E147E147C5C495A495A5C495A010EC7FC5B5B90387001 8013E0EA0180390300030012065A001FB5FC5A485BB5FCA219267DA521>I<13FF000313 E0380F01F8381C007C0030137E003C133E007E133FA4123CC7123E147E147C5C495AEB07 E03801FF8091C7FC380001E06D7E147C80143F801580A21238127C12FEA21500485B0078 133E00705B6C5B381F01F03807FFC0C690C7FC19277DA521>I<1238127C12FEA3127C12 381200AB1238127C12FEA3127C123807197B9813>58 D<007FB712C0B812E0A2CBFCABB8 12E0A26C16C02B117D9633>61 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fl cmsy10 10 27 /Fl 27 111 df<007FB81280B912C0A26C17803204799641>0 D<121C127FEAFF80A5EA 7F00121C0909799917>I<0060150600F8150F6C151F007E153F6C157E6C6C14FC6C6CEB 01F86C6CEB03F06C6CEB07E06C6CEB0FC06C6CEB1F80017EEB3F006D137E6D6C5A90380F C1F8903807E3F0903803F7E06DB45A6D5B6EC7FCA24A7E497F903803F7E0903807E3F090 380FC1F890381F80FC90383F007E017E7F49EB1F804848EB0FC04848EB07E04848EB03F0 4848EB01F84848EB00FC48C8127E007E153F48151F48150F00601506282874A841>II8 D15 D<020FB6128091B712C01303010F1680D91FF8C9FCEB7F8001FECA FCEA01F8485A485A485A5B48CBFC5A123E123C127CA2127812F8A25AA77EA21278127CA2 123C123E123F7E6C7E7F6C7E6C7E6C7EEA00FEEB7F80EB1FF86DB71280010316C0130002 0F158091CAFCAD001FB812804817C0A26C1780324279B441>18 D20 D<127012FCB4FCEA7FC0EA1FF0EA07FCEA01FF38007FC0EB1FF0EB07FCEB01FF9038007F C0EC1FF0EC07FCEC01FF9138007FC0ED1FF0ED07FCED01FF9238007FC0EE1FF0EE07FCEE 01FF9338007FC0171F177F933801FF80933807FC00EE1FF0EE7FC04B48C7FCED07FCED1F F0ED7FC04A48C8FCEC07FCEC1FF0EC7FC04948C9FCEB07FCEB1FF0EB7FC04848CAFCEA07 FCEA1FF0EA7FC048CBFC12FC1270CCFCAD007FB81280B912C0A26C1780324279B441>I< 181EA4181F84A285180785727EA2727E727E85197E85F11F80F10FC0F107F0007FBA12FC BCFCA26C19FCCCEA07F0F10FC0F11F80F13F00197E61614E5A4E5AA24E5A61180F96C7FC A260181EA4482C7BAA53>33 D<0278151EA402F8151F4A81A20101834A15070103834948 6F7EA249486F7E49CA7E4983017E177E49834848EF1F804848EF0FC0D80FE0EF07F0003F BA12FCBCFCA2003F19FCD80FE0CAEA07F0D803F0EF0FC06C6CEF1F806C6CEF3F00017E17 7E6D5F6D5F6D6C4B5A6D6C4B5AA26D6C4B5A01015F6E150F010094C7FCA26E5D0278151E A4482C7BAA53>36 D<91381FFFFE91B6FC1303010F14FED91FF0C7FCEB7F8001FEC8FCEA 01F8485A485A485A5B48C9FCA2123EA25AA2127812F8A25AA2B712FE16FFA216FE00F0C9 FCA27EA21278127CA27EA27EA26C7E7F6C7E6C7E6C7EEA00FEEB7F80EB1FF06DB512FE01 0314FF1300021F13FE283279AD37>50 D54 D<0060161800F0163C6C167CA200781678007C16F8A2003C16F0003E1501A26CED03E0A2 6C16C06D1407A2000716806D140FA26C6CEC1F00A26CB612FEA36C5D01F8C7127CA2017C 5CA2013C5C013E1301A2011E5C011F1303A26D6C485AA201075CECC00FA2010391C7FC6E 5AA2903801F03EA20100133CECF87CA2EC7878EC7CF8A2EC3FF0A26E5AA36E5AA36E5A6E C8FC2E3C80B92F>56 D<156015F0A21401EB07F190383FFFE0EB7C1FEBF00748486C5AD8 03C07F4848487ED80F007FA248497E001E14BC153C003E143E141FA248EB1E1F143EA214 3CA2147C00FC1580147814F8A214F0A21301A214E01303A214C0A21307A21480A2130FA2 14005B007C1500131EA2D87E3E5BA2D83E3C133E137CA21378001F5C13F8000F14784913 F800075C0003495AEBE0033901F007802603FC1FC7FCEBFFFEEBC7F0D807C0C8FCA25BA2 6CC9FC21477CBF2A>59 D<0307B612FE033FEDFF804AB812C0140791260F807EC7FC9126 3C00FEEC3F004A161E4A491418010194C7FC495A01071301A2D90FC05B14801400011813 0390C75BA34B5AA3150F5EA34B5AA293B512FC4B5C604B14C0037ECAFCA25DA25D1401A2 4A5AA25D14075D140F5D141F92CBFC5C0006133E003E137E007E137CB413FC6D5AEBC1F0 EBF1E06CB45A6C90CCFC6C5AEA07F0423C7EB83C>70 DII<0203B512F8027FECFF8049B712F0010F8290273FC3F003 13FED978039038003FFF2601E00702071380D803C06F13C0D807801500000F177FD81F00 EE3FE0484A141F123E5A0078010F150F12C0C7FC4B15C0A3021FED1F80A24B1500183EA2 023F5D6092C85A4D5A4D5A4A4A5A027E020EC7FC173C17F84AEB03E0EE3F80DB1FFEC8FC 0101EB7FF89138F8FFC0DAF9FCC9FC02F8CAFC495AA3495AA3495AA3495AA291CBFC5BA2 137EA35B13F013C03B3D7FB83A>80 D<0060161800F0163CB3B26C167CA2007C16F8A26C ED01F0003F15036C6CEC07E06C6CEC0FC0D807F0EC3F80D803FE903801FF003A00FFC00F FC6DB55A011F14E0010391C7FC9038007FF82E347CB137>91 DI102 D<12FCEAFFC0EA07F0EA01FCEA007E7F80131F80130F B3A7801307806D7E6D7EEB007EEC1FF0EC07F8EC1FF0EC7E00495A495A495A5C130F5CB3 A7131F5C133F91C7FC137E485AEA07F0EAFFC000FCC8FC1D537ABD2A>I<14C0EB01E013 03A214C01307A21480130FA2EB1F00A2131E133EA25BA2137813F8A2485AA25B1203A25B 1207A2485AA290C7FC5AA2123EA2123C127CA2127812F8A41278127CA2123C123EA27EA2 7E7FA26C7EA212037FA212017FA26C7EA21378137CA27FA2131E131FA2EB0F80A2130714 C0A2130314E0A21301EB00C0135278BD20>I<126012F07EA21278127CA2123C123EA27E A27E7FA26C7EA212037FA26C7EA212007FA21378137CA27FA2131E131FA2EB0F80A21307 14C0A2130314E0A414C01307A21480130FA2EB1F00A2131E133EA25BA2137813F8A25B12 01A2485AA25B1207A2485AA290C7FC5AA2123EA2123C127CA2127812F8A25A126013527C BD20>I<126012F0B3B3B3B3A91260045377BD17>I<126012F07EA21278127CA2123C123E A2121E121FA27E7FA212077FA212037FA212017FA212007FA21378137CA2133C133EA213 1E131FA27F80A2130780A26D7EA2130180A2130080A21478147CA2143C143EA2141E141F A2801580A2140715C0A2140315E0A2140115F0A2140015F8A21578157CA2153C153EA215 1E150C1F537BBD2A>110 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fm cmsy7 7 13 /Fm 13 111 df0 D<1338A50060130C00F8133E00FC137E00FE 13FE383FBBF83807FFC000011300EA007C48B4FC000713C0383FBBF838FE38FE00FC137E 00F8133E0060130C00001300A517197B9A22>3 D<160E163E16FEED03F8ED0FE0ED3F80 EDFE00EC03F8EC0FE0EC3F8002FEC7FCEB03F8EB0FE0EB3F8001FEC8FCEA03F8EA0FE0EA 3F8000FEC9FC12F812FEEA3F80EA0FE0EA03F8EA00FEEB3F80EB0FE0EB03F8EB00FEEC3F 80EC0FE0EC03F8EC00FEED3F80ED0FE0ED03F8ED00FE163E160E1600AA007FB612FCB712 FEA227347AA734>20 D<13E0EA01F0EA03F8A3EA07F0A313E0A2120F13C0A3EA1F80A213 00A25A123EA35AA3127812F8A25A12100D1E7D9F13>48 D<49B5FC130F133F01FFC7FCEA 01F8EA03E0EA078048C8FC121E121C123C123812781270A212F05AA2B7FCA300E0C8FCA2 7E1270A212781238123C121C121E7E6C7EEA03E0EA01F86CB4FC013FB5FC130F13012027 7AA12D>50 D<140C141CA2143CEB3FB8EBFFF8EA03E03807807C380F007E001E13FF001C 13E7003C1480A2D87C0113C0007813C3A2130300F8EB83E0A213071403A2130F130EA313 1E131CA2133C1338A21378D8787013C0A2387CF00713E0003C1480A2001FEB0F0013C000 0F131E00075B3803E0F8EBFFF03807BF8090C8FCA31B317DAC22>59 D<0207B612C0023F15E091B7FC903A01E07C0007D90780EC03C090260F00781400011E01 F890C7FC5B137C01785BEB70011300A25D1403A25D1407A292B512C05C5FDB0006C7FC4A 90C8FCA2141E143E143C147C147814F85C13015CEA180300785BEAFC0700FE5BD8FF8FCA FCEA7FFEEA3FF8EA0FE0332A7EA730>70 DI92 D<147EEB03FEEB0FE0EB1F00133E5BB35BA2485AEA07E0EAFF 8000FCC7FCB47EEA07E0EA01F06C7EA2137CB37F7FEB0FE0EB03FEEB007E173B7BAB22> 102 D<12FCB47EEA0FE0EA01F06C7E137CB37FA27FEB0FC0EB03FEEB007EEB03FEEB0FC0 EB1F00133EA25BB35B485AEA0FE0EAFF8000FCC7FC173B7BAB22>I<12E0B3B3B3A5033B 78AB14>106 D<12E0A27E1270A212781238123C121CA2121E120E120F7EA27F1203A27F 12017F1200A27F137013781338A2133C131C131E130EA2130F7F801303A2801301801300 A2801470A214781438143C141CA2141E140E140F80A2158014031401193B7CAB22>110 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fn cmmi10 10 54 /Fn 54 123 df<1403EC3FF891387FFF80D901E313C014800103133F9138001F80ED0700 92C7FC80A280A2808013018080130080147F81143F8149B47E130790380F8FF0EB3E0F49 6C7E13F83801F003D803E07F1207380FC0011380121FEA3F0014005A127EA212FE5D4813 01A35DA24813035D6C13075D127C4A5A6C91C7FC5C6C133E6C6C5A3807C0F03801FFE0D8 003FC8FC223D7DBB25>14 DI<15FE913803FF8091380F83 E091383E01F091387C00F85C494813FC0103147C4948137E5C130F495AA249C7FC16FE5B 137EA2150113FE4914FCA20001140316F85BED07F01203ED0FE04914C0151F000715806D EB3F00157E6D5B390FEE01F09038E707E09038C3FF80D9C0FCC7FC001F90C8FCA25BA212 3FA290C9FCA25AA2127EA212FEA25AA2127027377EA42B>26 D<027FB512C00103B612E0 130F5B017F15C09026FF81FEC7FC3901FC007E48487F485A497F484880485AA248C7FCA2 127EA2153F00FE92C7FC5AA25D157E5A5DA24A5AA24A5A007C495A5D003C495A003E013F C8FC6C137C380F81F83803FFE0C66CC9FC2B257DA32F>I<121C127FEAFF80A5EA7F0012 1C0909798817>58 D<121C127FEAFF80A213C0A3127F121C1200A412011380A212031300 5A1206120E5A5A5A12600A19798817>II<150C151E153EA2153C157CA2157815F8A215F01401A215E01403A2 15C01407A21580140FA215005CA2141E143EA2143C147CA2147814F8A25C1301A25C1303 A2495AA25C130FA291C7FC5BA2131E133EA2133C137CA2137813F8A25B1201A25B1203A2 5B1207A25B120FA290C8FC5AA2121E123EA2123C127CA2127812F8A25A12601F537BBD2A >I<126012FCB4FCEA7FC0EA1FF0EA07FCEA01FF38007FC0EB1FF0EB07FCEB01FF903800 7FC0EC1FF0EC07FCEC01FF9138007FC0ED1FF0ED07FCED01FF9238007FC0EE1FF0EE07FC EE01FF9338007F80EF1FC0A2EF7F80933801FF00EE07FCEE1FF0EE7FC04B48C7FCED07FC ED1FF0ED7FC04A48C8FCEC07FCEC1FF0EC7FC04948C9FCEB07FCEB1FF0EB7FC04848CAFC EA07FCEA3FF0EA7FC048CBFC12FC1270323279AD41>I<1760177017F01601A21603A216 07160FA24C7EA216331673166316C3A2ED0183A2ED0303150683150C160115181530A215 60A215C014011580DA03007FA202061300140E140C5C021FB5FC5CA20260C7FC5C83495A 8349C8FC1306A25BA25B13385B01F01680487E000716FFB56C013F13FF5EA2383C7DBB3E >65 D<0103B77E4916F018FC903B0007F80003FE4BEB00FFF07F80020FED3FC0181F4B15 E0A2141FA25DA2143F19C04B143F1980027F157F190092C812FE4D5A4A4A5AEF0FF04AEC 1FC005FFC7FC49B612FC5F02FCC7B4FCEF3FC00103ED0FE0717E5C717E1307844A1401A2 130F17035CA2131F4D5A5C4D5A133F4D5A4A4A5A4D5A017F4BC7FC4C5A91C7EA07FC49EC 3FF0B812C094C8FC16F83B397DB83F>I<9339FF8001C0030F13E0037F9038F80380913A 01FF807E07913A07F8000F0FDA1FE0EB079FDA3F80903803BF0002FFC76CB4FCD901FC80 495A4948157E495A495A4948153E017F163C49C9FC5B1201484816385B1207485A183012 1F4993C7FCA2485AA3127F5BA312FF90CCFCA41703A25F1706A26C160E170C171C5F6C7E 5F001F5E6D4A5A6C6C4A5A16076C6C020EC8FC6C6C143C6C6C5C6CB4495A90393FE00FC0 010FB5C9FC010313FC9038007FC03A3D7CBA3B>I<0103B7FC4916E018F8903B0007F800 07FE4BEB00FFF03F80020FED1FC0180F4B15E0F007F0021F1503A24B15F81801143F19FC 5DA2147FA292C8FCA25C18035CA2130119F84A1507A2130319F04A150FA2010717E0181F 4A16C0A2010FEE3F80A24AED7F00187E011F16FE4D5A4A5D4D5A013F4B5A4D5A4A4A5A05 7FC7FC017F15FEEE03FC91C7EA0FF049EC7FC0B8C8FC16FC16C03E397DB845>I<0103B8 12F05BA290260007F8C7123F4B1407F003E0020F150118005DA2141FA25D19C0143FA24B 1330A2027F1470190092C7126017E05C16014A495A160F49B6FCA25F9138FC000F010314 07A24A6DC8FCA201075C18034A130660010F160693C7FC4A150E180C011F161C18184A15 38A2013F5E18F04A4A5AA2017F15074D5A91C8123F49913803FF80B9FCA295C7FC3C397D B83D>I<0103B812E05BA290260007F8C7123F4B140FF003C0140F18015DA2141FA25D19 80143FA25D1760027F14E095C7FC92C75AA24A1301A24A495A16070101141F91B6FC94C8 FCA2903903FC001F824A130EA21307A24A130CA2010F141CA24A90C9FCA2131FA25CA213 3FA25CA2137FA291CBFC497EB612C0A33B397DB835>II<0103B5D8F803B512F8495DA290260007F8C73807F8004B5DA2020F150F615DA202 1F151F615DA2023F153F615DA2027F157F96C7FC92C8FCA24A5D605CA249B7FC60A202FC C7120101031503605CA201071507605CA2010F150F605CA2011F151F605CA2013F153F60 5CA2017F157F95C8FC91C8FC496C4A7EB690B6FCA345397DB845>I<0107B512FCA216F8 90390007F8005DA2140FA25DA2141FA25DA2143FA25DA2147FA292C7FCA25CA25CA21301 A25CA21303A25CA21307A25CA2130FA25CA2131FA25CA2133FA25CA2137FA291C8FC497E B6FCA326397DB824>I<0203B512FCA3DA000113006F5AA215015EA315035EA315075EA3 150F5EA3151F5EA3153F5EA3157F93C7FCA35D5DA31401A25DA21403120FD83F805B127F EBC007D8FF805BA24A5AEB001F00FC5C00E0495A006049C8FC007013FE383801F8381E07 F03807FFC0D801FEC9FC2E3B7AB82E>I<0103B500F8903807FFFC5BA290260007F8C813 804BEDFC0019F0020F4B5AF003804B4AC7FC180E021F1538604B5CEF0380023F4AC8FC17 0E4B133C1770027F5C4C5ADB0007C9FC160E4A5B167E4A13FE4B7E01015B92380E7F80EC FC1CED383F010301E07FECFDC04A486C7EECFF00D907FC6D7E5C4A130783130F707E5C16 01011F81A24A6D7EA2013F6F7EA24A143F84137F717E91C8123F496C81B60107B512C0A2 6146397DB847>I<0103B6FC5B5E90260007FCC8FC5D5D140FA25DA2141FA25DA2143FA2 5DA2147FA292C9FCA25CA25CA21301A25CA21303A25CA2130718404A15C0A2010F150118 804A1403A2011F16005F4A1406170E013F151E171C4A143C177C017F5D160391C7120F49 EC7FF0B8FCA25F32397DB839>I<902603FFF893383FFF80496081D900079438FF800002 06DC01BFC7FCA2020E4C5A1A7E020C1606190CDA1C7E16FE4F5A02181630A20238166162 023016C1F00181DA703F158395380303F002601506A202E0ED0C076202C0151818300101 6D6C140F06605B028015C0A20103923801801FDD03005B140092380FC00649173F4D91C8 FC01065DA2010E4B5B4D137E130C6F6C5A011C17FEDCE1805B011802E3C7FCA2013802E6 130104EC5C1330ED03F8017016034C5C01F05CD807FC4C7EB500E0D9C007B512F0168015 0151397CB851>I<902603FFF891381FFFF8496D5CA2D90007030113006FEC007C020616 78DA0EFF157081020C6D1460A2DA1C3F15E0705CEC181F82023815016F6C5C1430150702 706D1303030392C7FC02607FA2DAE0015C701306ECC0008201016E130EEF800C5C163F01 03EDC01C041F131891C713E0160F49EDF03818300106140717F8010E02031370EFFC6013 0CEE01FE011C16E004005B011815FF177F1338600130153FA20170151F95C8FC01F081EA 07FCB512E01706A245397DB843>I<4BB4FC031F13F09238FE01FC913903F0007EDA07C0 EB1F80DA1F80EB0FC0023EC7EA07E002FCEC03F0495A4948EC01F8495A4948EC00FC495A 49C912FE49167E13FE49167F1201485AA2485AA2120F5B001F17FFA2485AA34848ED01FE A400FFEE03FC90C9FCA2EF07F8A2EF0FF0A218E0171F18C0EF3F806C167F180017FE4C5A 6C6C5D1603001F4B5A6D4A5A000FED1F806C6C4AC7FC6D147E0003EC01F8D801FC495AD8 007EEB0FC090263F807FC8FC903807FFF801001380383D7CBA3F>I<0103B7FC4916E018 F8903B0007F80007FC4BEB00FE187F020FED3F80F01FC05DA2021F16E0A25DA2143FF03F C05DA2027FED7F80A292C8130018FE4A4A5A604AEC07F04D5A0101ED3FC04CB4C7FC91B6 12FC17E0D903FCCAFCA25CA21307A25CA2130FA25CA2131FA25CA2133FA25CA2137FA291 CBFC497EB6FCA33B397DB835>I<92391FE00380DBFFFC130002036D5A91390FE01F8F91 393F0007DF027EEB01FE02F81300495A4948147E177C4948143C495AA2011F153891C8FC A3491530A28094C7FC80806D7E14FEECFFE06D13FE6DEBFFC06D14F06D806D80021F7F02 037FEC003F03037F1500167F163F161FA3120C160FA2001C151F94C7FCA3003C153EA25E 003E5D127E007F4A5A6D495A6DEB0FC0D8F9F0495AD8F0FE01FEC8FC39E03FFFF8010F13 E0D8C00190C9FC313D7CBA33>83 D<0003B812FEA25A903AF8003FC00101C0913880007E 4848163C90C7007F141C121E001C92C7FCA2485CA200305C007017180060130112E0485C A21403C716005DA21407A25DA2140FA25DA2141FA25DA2143FA25DA2147FA292C9FCA25C A25CA21301A25CA21303A25CEB0FFC003FB6FC5AA237397EB831>I<003FB56C48B51280 485DA226007F80C7381FF00091C8EA07C0604993C7FCA2491506A20001160E170C5BA200 03161C17185BA20007163817305BA2000F167017605BA2001F16E05F5BA2003F15015F5B A2007F150394C8FC90C8FCA25E4815065A160E160C161C161816385E127E5E4B5A6C4A5A 4BC9FC6C6C131E6C6C5B6C6C13F83903F807E06CB55A6C6C48CAFCEB0FF0393B7BB839> I<267FFFFC91383FFFC0B55DA2000390C83807FC006C48ED03E06060000094C7FC5F1706 5FA25F6D5DA26D5D17E05F4C5AA24CC8FC6E1306A2013F5C161C16185EA25E6E5BA2011F 495A150393C9FC1506A25D6E5AA2010F5B157015605DA2ECE18002E3CAFC14F3EB07F614 FE5C5CA25C5CA26D5AA25C91CBFC3A3B7CB830>I<277FFFFC01B500F890B51280B5FC60 000390C7D807FCC7380FF80001FC4BEC03E000016204035E98C7FC621A0604075DA2040F 5DA2041B5D6216336D02735D1663000003C34A5A83DB01834AC8FC04815CDB0301140603 075D1506030C5DA203185D1970033015606115606D01E04A5A15C090267F01804AC9FC17 FEDA030014060400130E0206150C020E5D140C4A5DA24A5D18E04A5D715A5C4A92CAFCA2 6DC85AA2013E157C1778133C1770133801301560513B7CB84E>I<49B500F890387FFFF0 95B5FC1AE0D90003018090380FFC004BC713E00201ED07804EC7FC6E6C140E606F5C705B 606F6C485A4D5A031F91C8FCEEE0065F6F6C5A5F03075B705A16F96FB45A94C9FC6F5AA3 6F7EA34B7FED037F9238063FC0150E4B6C7E1538ED700F03E07F15C04A486C7EEC030002 0613034A805C4A6D7E14704A1300494880495A49C86C7E130E011E153F017E4B7ED803FF 4B7E007F01E0011FEBFFC0B5FC6144397EB845>I<1578EC01FEEC07C6EC0F861507EC1E 03143E147C1507ECF806A2EB01F00103130EECE00C1307A2ECC01C010F1318153890381F 80301570156090383F00E015C01401017F1380EB7E03EC07001406EBFE0E495A5C143000 011370495AEBF9C0EBFB8001FFC7FC5B5B485AA25BA4485A120F121DEA39F0127100E114 0C0080143C0000147015E090387801C0EC078090383C1E00EB1FF8EB07E0203C7FBA23> 96 D<147E903803FF8090390FC1C38090391F00EFC0017E137F49133F485A4848EB1F80 12075B000F143F48481400A2485A5D007F147E90C7FCA215FE485C5AA214015D48150CA2 1403EDF01C16181407007C1538007E010F1330003E131F027B13706C01E113E03A0F83C0 F9C03A03FF007F80D800FCEB1F0026267DA42C>I<133FEA1FFFA3C67E137EA313FE5BA3 12015BA312035BA31207EBE0FCEBE3FF9038E707C0390FFE03E09038F801F001F013F8EB E000485A15FC5BA2123F90C7FCA214015A127EA2140312FE4814F8A2140715F05AEC0FE0 A215C0EC1F80143F00781400007C137E5C383C01F86C485A380F07C06CB4C7FCEA01FC1E 3B7CB924>II<163FED1FFFA3ED007F167EA216FEA216FCA21501A216F8A21503A216F0 A21507A2027E13E0903803FF8790380FC1CF90381F00EF017EEB7FC049133F485A484813 1F000715805B000F143F485A1600485A5D127F90C7127EA215FE5A485CA21401A248ECF8 0CA21403161CEDF0181407007C1538007E010F1330003E131F027B13706C01E113E03A0F 83C0F9C03A03FF007F80D800FCEB1F00283B7DB92B>II<16F8ED03FEED0F8792 381F0F80ED3E3F167F157CA215FC1700161C4A48C7FCA414035DA414075DA20107B512F0 A39026000FE0C7FC5DA4141F5DA4143F92C8FCA45C147EA514FE5CA413015CA4495AA45C 1307A25C121E123F387F8F80A200FF90C9FC131E12FEEA7C3CEA7878EA1FF0EA07C0294C 7CBA29>III<14E0EB03F8A21307A314F0EB01C090 C7FCAB13F8EA03FEEA070F000E1380121C121812381230EA701F1260133F00E0130012C0 5BEA007EA213FE5B1201A25B12035BA20007131813E01438000F133013C01470EB806014 E014C01381EB838038078700EA03FEEA00F815397EB71D>I<150FED3F80A2157FA31600 151C92C7FCABEC0F80EC3FE0ECF0F0903801C0F849487E14005B130E130C131CEB180113 3801305BA2EB0003A25DA21407A25DA2140FA25DA2141FA25DA2143FA292C7FCA25CA214 7EA214FEA25CA21301001E5B123F387F83F0A238FF87E0495A00FE5BD87C1FC8FCEA707E EA3FF8EA0FC0214981B722>II109 DII<90390F8003F0 90391FE00FFC903939F03C1F903A70F8700F80903AE0FDE007C09038C0FF80030013E000 01491303018015F05CEA038113015CA2D800031407A25CA20107140FA24A14E0A2010F14 1F17C05CEE3F80131FEE7F004A137E16FE013F5C6E485A4B5A6E485A90397F700F80DA38 3FC7FC90387E1FFCEC07E001FEC9FCA25BA21201A25BA21203A25B1207B512C0A32C3583 A42A>I<3903E001F83907F807FE390E3C1E07391C3E381F3A183F703F800038EBE07F00 30EBC0FF00705B00601500EC007E153CD8E07F90C7FCEAC07EA2120013FE5BA312015BA3 12035BA312075BA3120F5BA3121F5B0007C9FC21267EA425>114 D<13F8D803FE1438D8070F147C000E6D13FC121C1218003814011230D8701F5C12601503 EAE03F00C001005B5BD8007E1307A201FE5C5B150F1201495CA2151F120349EC80C0A215 3F1681EE0180A2ED7F0303FF130012014A5B3A00F8079F0E90397C0E0F1C90393FFC07F8 903907F001F02A267EA430>117 D<01F8EB03C0D803FEEB07E0D8070F130F000E018013 F0121C12180038140700301403D8701F130112601500D8E03F14E000C090C7FC5BEA007E 16C013FE5B1501000115805B150316001203495B1506150E150C151C151815385D00015C 6D485A6C6C485AD97E0FC7FCEB1FFEEB07F024267EA428>I<01F816F0D803FE9138E001 F8D8070F903801F003000ED9800314FC121C12180038020713010030EDE000D8701F167C 1260030F143CD8E03F163800C001005B5BD8007E131F183001FE5C5B033F147000011760 4991C7FCA218E000034A14C049137E17011880170318005F03FE1306170E000101015C01 F801BF5B3B00FC039F8070903A7E0F0FC0E0903A1FFC03FFC0902703F0007FC7FC36267E A43B>I<903907E001F090391FF807FC9039783E0E0F9039E01F1C1FD801C09038383F80 3A03800FF07F0100EBE0FF5A000E4A1300000C157E021F133C001C4AC7FC1218A2C7123F A292C8FCA25CA2147EA214FEA24A130CA20101141C001E1518003F5BD87F81143801835C 00FF1560010714E03AFE0E7C01C0D87C1C495A2778383E0FC7FC391FF00FFC3907C003F0 29267EA42F>I<13F8D803FE1470D8070F14F8000EEB8001121C121800381403003015F0 EA701F1260013F130700E0010013E012C05BD8007E130F16C013FE5B151F000115805BA2 153F000315005BA25D157EA315FE5D1401000113033800F80790387C1FF8EB3FF9EB0FE1 EB00035DA2000E1307D83F805B007F495AA24A5A92C7FCEB003E007C5B00705B6C485A38 1E07C06CB4C8FCEA01FC25367EA429>II E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fo cmr10 10 78 /Fo 78 126 df0 D<011FB512FEA39026001FFEC8 FCEC07F8A8EC3FFE0103B512E0D91FF713FC90397F07F87F01FCEC1F80D803F8EC0FE0D8 07F06E7ED80FE06E7E001F82D83FC06E7EA2007F8201808000FF1780A7007F170001C05C 003F5EA2D81FE04A5A000F5ED807F04A5AD803F84A5AD800FCEC1F80017F027FC7FC9039 1FF7FFFC0103B512E09026003FFEC8FCEC07F8A8EC1FFE011FB512FEA331397BB83C>8 D11 DI22 D<121C127FEAFF80A8EA7F00AB123EAB121CABC7FCA8121C127FEAFF80 A5EA7F00121C093C79BB17>33 D<001C131C007F137F39FF80FF80A26D13C0A3007F137F 001C131C00001300A40001130101801380A20003130301001300485B00061306000E130E 485B485B485B006013601A197DB92A>I<121C127FEAFF80A213C0A3127F121C1200A412 011380A2120313005A1206120E5A5A5A12600A1979B917>39 D<146014E0EB01C0EB0380 EB0700130E131E5B5BA25B485AA2485AA212075B120F90C7FCA25A121EA2123EA35AA65A B2127CA67EA3121EA2121F7EA27F12077F1203A26C7EA26C7E1378A27F7F130E7FEB0380 EB01C0EB00E01460135278BD20>I<12C07E12707E7E7E120F6C7E6C7EA26C7E6C7EA213 78A2137C133C133E131EA2131F7FA21480A3EB07C0A6EB03E0B2EB07C0A6EB0F80A31400 A25B131EA2133E133C137C1378A25BA2485A485AA2485A48C7FC120E5A5A5A5A5A13527C BD20>II<15301578B3A6007FB812F8B912FCA26C17F8C80078C8FCB3A6153036367BAF41>I<12 1C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E5A5A5A1260 0A19798817>II<121C127FEAFF80A5EA7F00121C0909798817> I<150C151E153EA2153C157CA2157815F8A215F01401A215E01403A215C01407A2158014 0FA215005CA2141E143EA2143C147CA2147814F8A25C1301A25C1303A2495AA25C130FA2 91C7FC5BA2131E133EA2133C137CA2137813F8A25B1201A25B1203A25B1207A25B120FA2 90C8FC5AA2121E123EA2123C127CA2127812F8A25A12601F537BBD2A>IIIII<1538A2157815F8A21401140314 07A2140F141F141B14331473146314C313011483EB030313071306130C131C1318133013 70136013C01201EA038013005A120E120C5A123812305A12E0B712F8A3C73803F800AB4A 7E0103B512F8A325397EB82A>I<0006140CD80780133C9038F003F890B5FC5D5D158092 C7FC14FC38067FE090C9FCABEB07F8EB3FFE9038780F803907E007E090388003F0496C7E 12066E7EC87EA28181A21680A4123E127F487EA490C71300485C12E000605C1270003049 5A00385C6C1303001E495A6C6C485A3907E03F800001B5C7FC38007FFCEB1FE0213A7CB7 2A>II<12301238123E003FB612E0A316C05A168016 000070C712060060140E5D151800E01438485C5D5DC712014A5A92C7FC5C140E140C141C 5CA25CA214F0495AA21303A25C1307A2130FA3495AA3133FA5137FA96DC8FC131E233B7B B82A>III<121C127FEAFF80A5EA 7F00121CC7FCB2121C127FEAFF80A5EA7F00121C092479A317>I<007FB812F8B912FCA3 CCFCAEB912FCA36C17F836167B9F41>61 D63 D<1538A3157CA315FEA34A7EA34A6C7EA202077F EC063FA2020E7FEC0C1FA2021C7FEC180FA202387FEC3007A202707FEC6003A202C07F15 01A2D901807F81A249C77F167FA20106810107B6FCA24981010CC7121FA2496E7EA3496E 7EA3496E7EA213E0707E1201486C81D80FFC02071380B56C90B512FEA3373C7DBB3E>65 DI<913A01FF800180020FEBE003027F13F8903A01FF807E07903A03 FC000F0FD90FF0EB039F4948EB01DFD93F80EB00FF49C8127F01FE153F12014848151F48 48150FA248481507A2485A1703123F5B007F1601A35B00FF93C7FCAD127F6DED0180A312 3F7F001F160318006C7E5F6C7E17066C6C150E6C6C5D00001618017F15386D6C5CD91FE0 5C6D6CEB03C0D903FCEB0F80902701FF803FC7FC9039007FFFFC020F13F002011380313D 7BBA3C>I69 DIIII76 DIIII82 DI<003FB812E0A3D9C003EB001F273E 0001FE130348EE01F00078160000701770A300601730A400E01738481718A4C71600B3B0 913807FF80011FB612E0A335397DB83C>II87 D<007FB590383FFFFCA3C601 F801071380D97FE0D903FCC7FC013FEC01F06D6C5C5F6D6C5C6D6C13034CC8FC6D6C1306 160E6D6C5B6DEB8018163891387FC0306E6C5A16E06E6C5A91380FF18015FB6EB4C9FC5D 14036E7EA26E7F6F7EA24B7E15DF9138019FF09138038FF8150F91380607FC91380E03FE 140C4A6C7EEC38000230804A6D7E14E04A6D7E49486D7E130391C76C7E01066E7E130E01 0C6E7E011C1401013C8101FE822607FF80010713E0B500E0013FEBFF80A339397EB83E> I91 D<3901800180000313033907 000700000E130E485B0018131800381338003013300070137000601360A200E013E0485B A400CE13CE39FF80FF806D13C0A3007F137FA2393F803F80390E000E001A1974B92A>I< EAFFF8A4EA0078B3B3B3B3A3EAFFF8A40D537FBD17>I97 DIIII<147E903803FF8090380FC1E0EB1F8790383F0FF0137EA213 FCA23901F803C091C7FCADB512FCA3D801F8C7FCB3AB487E387FFFF8A31C3B7FBA19>I< ED03F090390FF00FF890393FFC3C3C9039F81F707C3901F00FE03903E007C03A07C003E0 10000FECF000A248486C7EA86C6C485AA200075C6C6C485A6D485A6D48C7FC38073FFC38 060FF0000EC9FCA4120FA213C06CB512C015F86C14FE6CECFF804815C03A0F80007FE048 C7EA0FF0003E140348140116F8481400A56C1401007C15F06CEC03E0003F1407D80F80EB 0F80D807E0EB3F003901FC01FC39007FFFF0010790C7FC26387EA52A>IIIIII<2703F00FF0EB1FE000FFD93FFCEB7FF8913AF03F01E07E903BF1C01F8380 3F3D0FF3800FC7001F802603F70013CE01FE14DC49D907F8EB0FC0A2495CA3495CB3A348 6C496CEB1FE0B500C1B50083B5FCA340257EA445>I<3903F00FF000FFEB3FFCECF03F90 39F1C01F803A0FF3800FC03803F70013FE496D7EA25BA35BB3A3486C497EB500C1B51280 A329257EA42E>II<3903F01FE000FFEB7FF89038F1E07E9039F3801F 803A07F7000FC0D803FEEB07E049EB03F04914F849130116FC150016FEA3167FAA16FEA3 ED01FCA26DEB03F816F06D13076DEB0FE001F614C09039F7803F009038F1E07E9038F0FF F8EC1FC091C8FCAB487EB512C0A328357EA42E>II<3807E01F00FFEB7FC09038E1E3 E09038E387F0380FE707EA03E613EE9038EC03E09038FC0080491300A45BB3A2487EB512 F0A31C257EA421>II<1318A51338A31378A313F8120112031207001FB5FCB6FCA2D801F8C7FCB215 C0A93800FC011580EB7C03017E13006D5AEB0FFEEB01F81A347FB220>IIIIII<003FB5 12FCA2EB8003D83E0013F8003CEB07F00038EB0FE012300070EB1FC0EC3F800060137F15 0014FE495AA2C6485A495AA2495A495A495AA290387F000613FEA2485A485A0007140E5B 4848130C4848131CA24848133C48C7127C48EB03FC90B5FCA21F247EA325>I<000F133C 381F807EA3003F13FEEB00FC003E13F8A2387C01F0007813E0007013C0EAF00300E01380 00C01300A2170F75B92A>125 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fp cmbx10 10 47 /Fp 47 122 df<141C143C14F8EB01F0EB03E01307EB0FC0EB1F8014005B137E13FE5B12 015B1203A2485AA2120F5B121FA25B123FA4485AA512FFB1127FA56C7EA4121F7FA2120F 7F1207A26C7EA212017F12007F137E7F7F1480EB0FC0EB07E01303EB01F0EB00F8143C14 1C165377BD25>40 D<12E07E127C7E7E7F6C7E6C7E12037F6C7E7F12007F137E137FA2EB 3F80A214C0131F14E0A2130F14F0A4EB07F8A514FCB114F8A5EB0FF0A414E0131FA214C0 133F1480A2EB7F00A2137E13FE5B12015B485A5B1207485A485A90C7FC123E5A12F05A16 537BBD25>I45 DI<49B4FC010F13E0017F13FC9038FF83FE4848C67E4848EB 7F804848EB3FC04848EB1FE0A2001F15F0A24848EB0FF8A3007F15FCA500FF15FEB3007F 15FCA4003F15F8A26D131F001F15F0A2000F15E06D133F000715C06C6CEB7F806C6CEBFF 003900FF83FE6DB45A011F13F0010190C7FC27387CB630>48 D<141E143E14FE1307133F B5FCA313CFEA000FB3B3A6007FB61280A4213779B630>IIII<001C15C0D81F80130701F8137F90B61280A21600 5D5D15F05D15804AC7FC14F090C9FCA8EB07FE90383FFFE090B512F89038FC07FC9038E0 03FFD98001138090C713C0120EC813E0157F16F0A216F8A21206EA3F80EA7FE012FF7FA4 4914F0A26C4813FF90C713E0007C15C06C5B6C491380D9C0071300390FF01FFE6CB512F8 000114E06C6C1380D90FF8C7FC25387BB630>II<123C123EEA3FE090B71280A41700485D5E5E5EA25E007CC7EA0FC000784A5A 4BC7FC00F8147E48147C15FC4A5A4A5AC7485A5D140F4A5A143F92C8FC5C147E14FE1301 A2495AA31307A2130F5CA2131FA5133FA96D5A6D5A6D5A293A7BB830>I<49B47E010F13 F0013F13FC9038FE01FF3A01F8007F804848EB3FC04848EB1FE0150F485AED07F0121FA2 7FA27F7F01FEEB0FE0EBFF809138E01FC06CEBF03F02FC13809138FF7F006C14FC6C5C7E 6C14FE6D7F6D14C04914E048B612F0EA07F848486C13F8261FE01F13FC383FC007EB8001 007F6D13FE90C7123F48140F48140715031501A21500A216FC7E6C14016D14F86C6CEB03 F06D13076C6CEB0FE0D80FFEEB7FC00003B61200C614FC013F13F00103138027387CB630 >II65 D67 D69 D71 D76 D78 D80 D83 D<003FB91280A4D9F800EBF003D87FC09238007FC049161F007E C7150FA2007C1707A200781703A400F818E0481701A4C892C7FCB3AE010FB7FCA43B387D B742>II97 D<13FFB5FCA412077EAF4AB47E020F13F0023F13FC9138FE03FFDAF00013804AEB7FC002 80EB3FE091C713F0EE1FF8A217FC160FA217FEAA17FCA3EE1FF8A217F06E133F6EEB7FE0 6E14C0903AFDF001FF80903AF8FC07FE009039F03FFFF8D9E00F13E0D9C00390C7FC2F3A 7EB935>I<903801FFC0010F13FC017F13FFD9FF8013802603FE0013C048485AEA0FF812 1F13F0123F6E13804848EB7F00151C92C7FC12FFA9127FA27F123FED01E06C7E15036C6C EB07C06C6C14806C6C131FC69038C07E006DB45A010F13F00101138023257DA42A>II<903803FF8001 1F13F0017F13FC3901FF83FE3A03FE007F804848133F484814C0001FEC1FE05B003FEC0F F0A2485A16F8150712FFA290B6FCA301E0C8FCA4127FA36C7E1678121F6C6C14F86D14F0 00071403D801FFEB0FE06C9038C07FC06DB51200010F13FC010113E025257DA42C>II<161FD907FE EBFFC090387FFFE348B6EAEFE02607FE07138F260FF801131F48486C138F003F15CF4990 387FC7C0EEC000007F81A6003F5DA26D13FF001F5D6C6C4890C7FC3907FE07FE48B512F8 6D13E0261E07FEC8FC90CAFCA2123E123F7F6C7E90B512F8EDFF8016E06C15F86C816C81 5A001F81393FC0000F48C8138048157F5A163FA36C157F6C16006D5C6C6C495AD81FF0EB 07FCD807FEEB3FF00001B612C06C6C91C7FC010713F02B377DA530>I<13FFB5FCA41207 7EAFED7FC0913803FFF8020F13FE91381F03FFDA3C01138014784A7E4A14C05CA25CA291 C7FCB3A3B5D8FC3F13FFA4303A7DB935>II<13FFB5FCA412077EAF92 380FFFE0A4923803FC0016F0ED0FE0ED1F804BC7FC157E5DEC03F8EC07E04A5A141FEC7F E04A7E8181A2ECCFFEEC0FFF496C7F806E7F6E7F82157F6F7E6F7E82150F82B5D8F83F13 F8A42D3A7EB932>107 D<13FFB5FCA412077EB3B3ACB512FCA4163A7DB91B>I<01FED97F E0EB0FFC00FF902601FFFC90383FFF80020701FF90B512E0DA1F81903983F03FF0DA3C00 903887801F000749DACF007F00034914DE6D48D97FFC6D7E4A5CA24A5CA291C75BB3A3B5 D8FC1FB50083B512F0A44C257DA451>I<01FEEB7FC000FF903803FFF8020F13FE91381F 03FFDA3C011380000713780003497E6D4814C05CA25CA291C7FCB3A3B5D8FC3F13FFA430 257DA435>I<903801FFC0010F13F8017F13FFD9FF807F3A03FE003FE048486D7E48486D 7E48486D7EA2003F81491303007F81A300FF1680A9007F1600A3003F5D6D1307001F5DA2 6C6C495A6C6C495A6C6C495A6C6C6CB45A6C6CB5C7FC011F13FC010113C029257DA430> I<9039FF01FF80B5000F13F0023F13FC9138FE07FFDAF00113800003496C13C00280EB7F E091C713F0EE3FF8A2EE1FFCA3EE0FFEAA17FC161FA217F8163F17F06E137F6E14E06EEB FFC0DAF00313809139FC07FE0091383FFFF8020F13E0020390C7FC91C9FCACB512FCA42F 357EA435>I<49B4EB0780010FEBE00F013FEBF81F9039FFC07C3F0003EB803E3A07FE00 0F7F4848EB07FF121F497F123F497F127FA25B12FFAA6C7EA36C7E5D6C7E000F5C6C6C5B 6C6C133F6CEBC0FD39007FFFF1011F13C10101130190C7FCAC037F13FEA42F357DA432> I<9038FE03F000FFEB0FFEEC3FFF91387C7F809138F8FFC000075B6C6C5A5CA29138807F 80ED3F00150C92C7FC91C8FCB3A2B512FEA422257EA427>I<90383FF0383903FFFEF800 0F13FF381FC00F383F0003007E1301007C130012FC15787E7E6D130013FCEBFFE06C13FC ECFF806C14C06C14F06C14F81203C614FC131F9038007FFE140700F0130114007E157E7E 157C6C14FC6C14F8EB80019038F007F090B512C000F8140038E01FF81F257DA426>I<13 0FA55BA45BA25B5BA25A1207001FEBFFE0B6FCA3000390C7FCB21578A815F86CEB80F014 816CEBC3E090383FFFC06D1380903803FE001D357EB425>I<01FFEC3FC0B5EB3FFFA400 0714016C80B3A35DA25DA26C5C6E4813E06CD9C03E13FF90387FFFFC011F13F001031380 30257DA435>I119 DII E %EndDVIPSBitmapFont end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%PaperSize: Letter %%EndSetup %%Page: 1 1 1 0 bop 1252 223 a Fp(Com)m(binatorial)30 b(Games)-85 454 y(Game)36 b(1)d Fo(Start)f(with)h Fn(n)g Fo(c)n(hips.)52 b(Pla)n(y)n(ers)30 b(A,B)j(alternately)e(tak)n(e)h(1,2,3,4)f(c)n(hips)i (un)n(til)g(there)f(are)g(none)g(left.)-85 553 y(The)27 b(winner)h(is)f(the)h(p)r(erson)f(who)g(tak)n(es)g(the)h(last)f(c)n (hip:)-85 707 y(Example)p 958 850 1498 4 v 956 949 4 100 v 1300 949 V 1351 920 a(A)p 1462 949 V 100 w(B)p 1620 949 V 100 w(A)p 1782 949 V 99 w(B)p 1940 949 V 100 w(A)p 2102 949 V 2454 949 V 958 953 1498 4 v 956 1052 4 100 v 1008 1022 a Fn(n)c Fo(=)g(10)p 1300 1052 V 109 w(3)p 1462 1052 V 118 w(2)p 1620 1052 V 118 w(4)p 1782 1052 V 118 w(1)p 1940 1052 V 2102 1052 V 272 w(B)k(wins)p 2454 1052 V 958 1056 1498 4 v 956 1155 4 100 v 1008 1125 a Fn(n)c Fo(=)g(11)p 1300 1155 V 109 w(1)p 1462 1155 V 118 w(2)p 1620 1155 V 118 w(3)p 1782 1155 V 118 w(4)p 1940 1155 V 118 w(1)p 2102 1155 V 110 w(A)28 b(wins)p 2454 1155 V 958 1159 1498 4 v -85 1340 a(What)g(is)f(the)h(optimal)g (strategy)e(for)h(this)h(game?)-85 1493 y Fp(Game)c(2)d Fo(Chip)h(placed)g(at)f(p)r(oin)n(t)h(\()p Fn(m;)14 b(n)p Fo(\).)35 b(Pla)n(y)n(ers)19 b(can)j(mo)n(v)n(e)e(c)n(hip)i(to)g(\()p Fn(m)2304 1463 y Fm(0)2327 1493 y Fn(;)14 b(n)p Fo(\))22 b(or)f(\()p Fn(m;)14 b(n)2756 1463 y Fm(0)2779 1493 y Fo(\))22 b(where)f(0)i Fl(\024)f Fn(m)3292 1463 y Fm(0)3338 1493 y Fn(<)h(m)-85 1593 y Fo(and)k(0)c Fl(\024)f Fn(n)278 1563 y Fm(0)325 1593 y Fn(<)g(n)p Fo(.)37 b(The)28 b(pla)n(y)n(er)e (who)h(mak)n(es)f(the)i(last)g(mo)n(v)n(e)e(and)i(puts)g(the)g(c)n(hip) f(on)n(to)g(\(0)p Fn(;)14 b Fo(0\))27 b(wins.)-85 1746 y(What)h(is)f(the)h(optimal)g(strategy)e(for)h(this)h(game?)-85 1899 y Fp(Game)33 b(3)d Fn(W)41 b Fo(is)30 b(a)g(set)g(of)f(w)n(ords.) 43 b(A)30 b(and)f(B)h(alternatel)f(remo)n(v)n(e)f(w)n(ords)h Fn(w)2361 1911 y Fk(1)2399 1899 y Fn(;)14 b(w)2495 1911 y Fk(2)2532 1899 y Fn(;)g(:)g(:)g(:)28 b(;)i Fo(from)f Fn(W)12 b Fo(.)44 b(The)30 b(rule)f(is)-85 1999 y(that)i(the)h(\014rst) f(letter)h(of)f Fn(w)803 2011 y Fj(i)p Fk(+1)946 1999 y Fo(m)n(ust)h(b)r(e)g(the)f(same)g(as)g(the)g(last)g(letter)h(of)f Fn(w)2427 2011 y Fj(i)2455 1999 y Fo(.)48 b(The)32 b(pla)n(y)n(er)d (who)i(mak)n(es)g(the)-85 2099 y(last)c(legal)g(mo)n(v)n(e)f(wins.)-85 2426 y Fi(1)134 b(Abstraction)-85 2661 y Fo(Represen)n(t)25 b(eac)n(h)g(p)r(osition)h(b)n(y)g(a)g(v)n(ertex)f(of)h(a)g(digraph)f Fn(D)g Fo(=)d(\()p Fn(X)r(;)14 b(A)p Fo(\).)37 b(\()p Fn(x;)14 b(y)s Fo(\))27 b(is)f(an)g(arc)f(of)h Fn(D)i Fo(i\013)f(one)f(can)f(mo)n(v)n(e)-85 2761 y(from)i(p)r(osition)g Fn(x)i Fo(to)e(p)r(osition)g Fn(y)s Fo(.)-85 2914 y(W)-7 b(e)28 b(assume)f(that)g(the)h(digraph)f(is)h(\014nite)g(and)f(that)h (it)g(is)g Fp(acyclic)g Fo(i.e.)37 b(there)28 b(are)e(no)i(directed)f (cycles.)-85 3067 y(The)h(game)f(starts)g(with)h(a)f(c)n(hip)h(on)g(v)n (ertex)f Fn(x)1386 3079 y Fk(0)1451 3067 y Fo(sa)n(y)-7 b(,)27 b(and)h(pla)n(y)n(ers)e(alternately)h(mo)n(v)n(e)f(the)j(c)n (hip)e(to)h Fn(x)3155 3079 y Fk(1)3193 3067 y Fn(;)14 b(x)3277 3079 y Fk(2)3315 3067 y Fn(;)g(:)g(:)g(:)27 b(;)-85 3167 y Fo(where)j Fn(x)205 3179 y Fj(i)p Fk(+1)345 3167 y Fl(2)f Fo(\000)481 3137 y Fk(+)536 3167 y Fo(\()p Fn(x)615 3179 y Fj(i)644 3167 y Fo(\),)j(the)f(set)f(of)h(out-neigh)n (b)r(ours)e(of)i Fn(x)1823 3179 y Fj(i)1851 3167 y Fo(.)47 b(The)30 b(game)g(ends)h(when)g(the)g(c)n(hip)g(is)g(on)f(a)g Fp(sink)-85 3267 y Fo(i.e.)37 b(a)27 b(v)n(ertex)g(of)g(out-degree)f (zero.)36 b(The)28 b(last)f(pla)n(y)n(er)f(to)h(mo)n(v)n(e)g(is)g(the)h (winner.)-85 3420 y(Example)f(1:)36 b Fn(D)25 b Fo(=)e(\()p Fl(f)p Fo(0)p Fn(;)14 b Fo(1)p Fn(;)g(:)g(:)g(:)26 b(;)14 b(n)p Fl(g)p Fn(;)g(A)p Fo(\))27 b(where)g(\()p Fn(x;)14 b(y)s Fo(\))24 b Fl(2)f Fn(A)28 b Fo(i\013)g Fn(x)19 b Fl(\000)f Fn(y)26 b Fl(2)e(f)p Fo(1)p Fn(;)14 b Fo(2)p Fn(;)g Fo(3)p Fn(;)g Fo(4)p Fl(g)p Fo(.)-85 3573 y(Example)26 b(2:)36 b Fn(D)25 b Fo(=)e(\()p Fl(f)p Fo(0)p Fn(;)14 b Fo(1)p Fn(;)g(:)g(:)g(:)26 b(;)14 b(m)p Fl(g)j(\002)g(f)p Fo(0)p Fn(;)d Fo(1)p Fn(;)g(:)g(:)g(:)26 b(;)14 b(n)p Fl(g)p Fn(;)g(A)p Fo(\))27 b(where)g(\()p Fn(x;)14 b(y)s Fo(\))23 b Fl(2)h Fo(\000)2344 3543 y Fk(+)2399 3573 y Fo(\(\()p Fn(x)2510 3543 y Fm(0)2534 3573 y Fn(;)14 b(y)2615 3543 y Fm(0)2638 3573 y Fo(\)\)\))28 b(i\013)g Fn(x)23 b Fo(=)g Fn(x)3066 3543 y Fm(0)3117 3573 y Fo(and)k Fn(y)e(>)e(y)3476 3543 y Fm(0)-85 3673 y Fo(or)j Fn(x)e(>)f(x)222 3643 y Fm(0)273 3673 y Fo(and)k Fn(y)f Fo(=)d Fn(y)633 3643 y Fm(0)656 3673 y Fo(.)-85 3826 y(Example)j(3:)36 b Fn(D)25 b Fo(=)d(\()p Fl(f)p Fo(\()p Fn(W)737 3796 y Fm(0)761 3826 y Fn(;)14 b(w)r Fo(\))24 b(:)46 b Fn(W)1074 3796 y Fm(0)1120 3826 y Fl(\022)23 b Fn(W)29 b Fl(n)16 b(f)p Fn(w)r Fl(gg)p Fn(;)e(A)p Fo(\).)36 b Fn(w)30 b Fo(is)c(the)i(last)e(w)n(ord)g(used)g(and)h Fn(W)2864 3796 y Fm(0)2914 3826 y Fo(is)g(the)g(remaining)-85 3926 y(set)g(of)g(un)n(used)h(w)n(ords.)35 b(\()p Fn(A)782 3896 y Fm(0)806 3926 y Fn(;)14 b(w)904 3896 y Fm(0)928 3926 y Fo(\))23 b Fl(2)g Fo(\000)1113 3896 y Fk(+)1168 3926 y Fo(\(\()p Fn(A;)14 b(w)r Fo(\)\))30 b(i\013)e Fn(w)1646 3896 y Fm(0)1693 3926 y Fl(2)23 b Fn(A)28 b Fo(and)f Fn(w)2083 3896 y Fm(0)2134 3926 y Fo(b)r(egins)h(with)f(the)h (last)f(letter)h(of)f Fn(w)r Fo(.)37 b(Also,)-85 4025 y(there)27 b(is)h(an)f(arc)g(from)g(\()p Fn(W)n(;)14 b Fl(\001)p Fo(\))28 b(to)g(\()p Fn(W)i Fl(n)18 b(f)p Fn(w)r Fl(g)p Fn(;)c(w)r Fo(\))28 b(for)f(all)h Fn(w)r Fo(,)g(corresp)r(onding)e(to)h(the)h(games)f(start.)-85 4179 y(W)-7 b(e)29 b(will)g(\014rst)g(argue)e(that)j(suc)n(h)e(a)h (game)f(m)n(ust)h(ev)n(en)n(tually)f(end.)41 b(A)29 b Fp(top)s(ological)j(n)m(um)m(b)s(ering)27 b Fo(of)i(digraph)-85 4278 y Fn(D)g Fo(is)f(a)f(map)h Fn(f)j Fo(:)23 b Fn(X)30 b Fl(!)23 b Fo([)p Fn(N)9 b Fo(],)27 b Fn(N)32 b Fo(=)23 b Fl(j)p Fn(X)7 b Fl(j)27 b Fo(whic)n(h)h(satis\014es)e(\()p Fn(x;)14 b(y)s Fo(\))24 b Fl(2)f Fn(A)28 b Fo(implies)g Fn(f)9 b Fo(\()p Fn(x)p Fo(\))24 b Fn(<)e(f)9 b Fo(\()p Fn(y)s Fo(\).)-85 4440 y Fp(Theorem)30 b(1.)41 b Fh(A)25 b(\014nite)h(digr)l(aph)h Fn(D)f Fo(=)c(\()p Fn(X)r(;)14 b(A)p Fo(\))26 b Fh(is)g(acyclic)i(i\013)e(it)g(admits)g(at)g(le)l(ast) g(one)g(top)l(olo)l(gic)l(al)i(numb)l(ering.)-85 4655 y Fp(Pro)s(of)191 b Fo(Supp)r(ose)28 b(\014rst)f(that)h Fn(D)j Fo(has)c(a)g(top)r(ological)g(n)n(um)n(b)r(ering.)37 b(W)-7 b(e)28 b(sho)n(w)g(that)g(it)g(is)g(acyclic.)37 b(Supp)r(ose)-85 4754 y(that)g Fn(C)44 b Fo(=)38 b(\()p Fn(x)389 4766 y Fk(1)427 4754 y Fn(;)14 b(x)511 4766 y Fk(2)549 4754 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(x)794 4766 y Fj(k)835 4754 y Fn(;)g(x)919 4766 y Fk(1)957 4754 y Fo(\))37 b(is)g(a)f(directed)h(cycle.)64 b(Then)36 b Fn(f)9 b Fo(\()p Fn(x)2144 4766 y Fk(1)2182 4754 y Fo(\))39 b Fn(<)e(f)9 b Fo(\()p Fn(x)2484 4766 y Fk(2)2522 4754 y Fo(\))39 b Fn(<)e Fl(\001)14 b(\001)g(\001)39 b Fn(<)e(f)9 b Fo(\()p Fn(x)3062 4766 y Fj(k)3104 4754 y Fo(\))38 b Fn(<)g(f)9 b Fo(\()p Fn(x)3406 4766 y Fk(1)3444 4754 y Fo(\),)-85 4854 y(con)n(tradiction.)-85 5007 y(Supp)r(ose)41 b(no)n(w)f(that)i Fn(D)h Fo(is)e(acyclic.)76 b(W)-7 b(e)41 b(\014rst)g(argue)f(that)h Fn(D)i Fo(has)e(at)g(least)f(one)h(sink.)77 b(Th)n(us)41 b(let)g Fn(P)57 b Fo(=)-85 5107 y(\()p Fn(x)-6 5119 y Fk(1)32 5107 y Fn(;)14 b(x)116 5119 y Fk(2)153 5107 y Fn(;)g(:)g(:)g(:)28 b(;)14 b(x)399 5119 y Fj(k)440 5107 y Fo(\))32 b(b)r(e)h(a)e(longest)h(simple)g(path)g(in)g Fn(D)r Fo(.)51 b(W)-7 b(e)32 b(claim)g(that)g Fn(x)2293 5119 y Fj(k)2367 5107 y Fo(is)g(a)f(sink.)51 b(If)32 b Fn(D)i Fo(con)n(tains)d(an)h(arc)-85 5207 y(\()p Fn(x)-6 5219 y Fj(k)35 5207 y Fn(;)14 b(y)s Fo(\))20 b(then)g(either)f Fn(y)26 b Fo(=)c Fn(x)777 5219 y Fj(i)805 5207 y Fn(;)14 b Fo(1)23 b Fl(\024)f Fn(i)h Fl(\024)g Fn(k)5 b Fl(\000)r Fo(1)18 b(and)i(this)f(means)g(that)h Fn(D)i Fo(con)n(tains)c(the)i (cycle)f Fn(x)2821 5219 y Fj(i)2849 5207 y Fn(;)14 b(x)2933 5219 y Fj(i)p Fk(+1)3045 5207 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(x)3290 5219 y Fj(k)3332 5207 y Fn(;)g(x)3416 5219 y Fj(i)3444 5207 y Fo(\),)-85 5306 y(con)n(tradiction)25 b(or)g Fn(y)35 b(=)-51 b Fl(2)24 b(f)p Fn(x)754 5318 y Fk(1)791 5306 y Fn(;)14 b(x)875 5318 y Fk(2)912 5306 y Fn(;)g(:)g(:)g(:)28 b(;)14 b(x)1158 5318 y Fj(k)1199 5306 y Fl(g)26 b Fo(and)g(then)h(\()p Fn(P)r(;)14 b(y)s Fo(\))27 b(is)g(a)f(longer)f(simple)i(path)f(than)h Fn(P)12 b Fo(,)26 b(con)n(tradiction.)1686 5555 y(1)p eop %%Page: 2 2 2 1 bop -85 223 a Fo(W)-7 b(e)30 b(can)f(no)n(w)g(pro)n(v)n(e)f(b)n(y)h (induction)h(on)g Fn(N)38 b Fo(that)30 b(there)g(is)f(at)h(least)f(one) g(top)r(ological)f(n)n(um)n(b)r(ering.)43 b(Ifg)29 b Fn(N)35 b Fo(=)26 b(1)-85 323 y(and)h Fn(X)j Fo(=)22 b Fl(f)p Fn(x)p Fl(g)27 b Fo(then)h Fn(f)9 b Fo(\()p Fn(x)p Fo(\))24 b(=)f(1)k(de\014nes)g(a)h(top)r(ological)e(n)n(um)n(b)r (ering.)-85 476 y(No)n(w)j(asssume)f(that)i Fn(N)k(>)26 b Fo(1.)42 b(Let)29 b Fn(z)k Fo(b)r(e)d(a)f(sink)g(of)g Fn(D)j Fo(and)d(de\014ne)h Fn(f)9 b Fo(\()p Fn(z)t Fo(\))25 b(=)h Fn(N)9 b Fo(.)42 b(The)29 b(digraph)g Fn(D)3057 446 y Fm(0)3106 476 y Fo(=)d Fn(D)21 b Fl(\000)e Fn(z)33 b Fo(is)-85 576 y(acyclic)27 b(and)i(b)n(y)f(the)h(induction)g(h)n(yp)r (othesis)f(it)h(admits)f(a)g(top)r(ological)f(n)n(um)n(b)r(ering,)i Fn(f)k Fo(:)24 b Fn(X)i Fl(n)18 b(f)p Fn(z)t Fl(g)23 b(!)i Fo([)p Fn(N)j Fl(\000)18 b Fo(1].)-85 675 y(The)31 b(function)g(w)n(e)g(ha)n(v)n(e)e(de\014ned)j(on)e Fn(X)37 b Fo(is)31 b(a)g(top)r(ological)e(n)n(um)n(b)r(ering.)46 b(If)32 b(\()p Fn(x;)14 b(y)s Fo(\))29 b Fl(2)g Fn(A)i Fo(then)g(either)g Fn(x;)14 b(y)32 b Fl(6)p Fo(=)c Fn(z)-85 775 y Fo(and)f(then)h Fn(f)9 b Fo(\()p Fn(x)p Fo(\))24 b Fn(<)e(f)9 b Fo(\()p Fn(y)s Fo(\))28 b(b)n(y)f(our)g(assumption)g(on) g Fn(f)9 b Fo(,)27 b(or)g Fn(y)f Fo(=)c Fn(z)31 b Fo(and)c(then)h Fn(f)9 b Fo(\()p Fn(x)p Fo(\))24 b Fn(<)f(N)32 b Fo(=)22 b Fn(f)9 b Fo(\()p Fn(z)t Fo(\))27 b(\()p Fn(x)d Fl(6)p Fo(=)f Fn(z)30 b Fo(b)r(ecause)-85 874 y Fn(z)h Fo(is)c(a)g(sink\).) 3099 b Fg(2)-85 1028 y Fo(The)25 b(fact)g(that)h Fn(D)h Fo(has)e(a)f(top)r(ological)g(n)n(um)n(b)r(ering)g(implies)i(that)f (the)h(game)e(m)n(ust)h(end.)37 b(Eac)n(h)24 b(mo)n(v)n(e)g(increases) -85 1127 y(the)32 b Fn(f)41 b Fo(v)-5 b(alue)32 b(of)g(the)h(curren)n (t)e(p)r(osition)h(b)n(y)g(at)g(least)f(one)h(and)g(so)f(after)h(at)g (most)g Fn(N)41 b Fo(mo)n(v)n(es)31 b(a)g(sink)h(m)n(ust)h(b)r(e)-85 1227 y(reac)n(hed.)-85 1380 y(The)27 b(p)r(ositions)h(of)f(a)g(game)g (are)g(partitioned)g(in)n(to)g(2)g(sets:)39 1591 y Fl(\017)41 b Fo(P-p)r(ositions:)32 b(The)21 b(next)f(pla)n(y)n(er)f(cannot)g(win.) 35 b(The)20 b(previous)f(pla)n(y)n(er)g(can)h(win)g(regardless)e(of)i (the)h(curren)n(t)122 1691 y(pla)n(y)n(er's)26 b(strategy)-7 b(.)39 1853 y Fl(\017)41 b Fo(N-p)r(ositions:)c(The)27 b(next)h(pla)n(y)n(er)e(has)h(a)g(strategy)g(for)g(winning)g(the)h (game.)-85 2064 y(The)22 b(main)g(problem)g(is)g(to)g(determine)h(N)f (and)g(P)g(and)g(what)h(the)f(strategy)f(is)h(for)g(winning)g(from)g (an)g(N-p)r(osition.)-85 2217 y(F)-7 b(or)27 b Fn(x)c Fl(2)h Fn(X)34 b Fo(let)28 b(\000)488 2187 y Fk(+)543 2217 y Fo(\()p Fn(x)p Fo(\))c(=)e Fl(f)p Fn(y)k Fl(2)d Fn(X)29 b Fo(:)46 b(\()p Fn(x;)14 b(y)s Fo(\))24 b Fl(2)g Fn(A)p Fl(g)j Fo(b)r(e)h(the)g(set)g(of)f(p)r(out-neigh)n(b)r(ours)g (of)g Fn(x)p Fo(.)-85 2370 y Fp(Lab)s(elling)j(pro)s(cedure)16 2582 y Fo(1.)41 b(Lab)r(el)28 b(all)f(sinks)g(with)h(P)-7 b(.)16 2743 y(2.)41 b(Lab)r(el)28 b(with)g(N,)g(ev)n(ery)e(p)r(osition) i Fn(x)g Fo(for)f(whic)n(h)g(there)h(exists)f Fn(y)f Fl(2)d Fo(\000)2268 2713 y Fk(+)2323 2743 y Fo(\()p Fn(x)p Fo(\))29 b(whic)n(h)e(is)h(lab)r(elled)g(with)g(P)-7 b(.)16 2905 y(3.)41 b(Lab)r(el)28 b(with)g(P)-7 b(,)27 b(ev)n(ery)f(p)r(osition)i Fn(x)g Fo(for)f(whic)n(h)h(\000)1669 2875 y Fk(+)1724 2905 y Fo(\()p Fn(x)p Fo(\))g(is)g(lab)r(elled)g(with) g(N.)-85 3116 y(A)h(p)r(osition)f Fn(x)h Fo(is)f(an)g(N-p)r(osition)h (\(winning\))g(i\013)g(there)f(is)g(a)g(mo)n(v)n(e)g(from)g Fn(x)h Fo(to)f(a)g(losing)g(p)r(osition)g(for)g(the)h(next)-85 3216 y(pla)n(y)n(er.)-85 3369 y(The)e(lab)r(elling)h(should)f(b)r(e)h (carried)e(out)i(in)g(rev)n(erse)d(top)r(ological)i(order.)-85 3522 y(Th)n(us)g(there)g(is)h(a)f(unique)h(partition)f(of)h Fn(X)34 b Fo(in)n(to)27 b Fn(N)t(;)14 b(P)40 b Fo(whic)n(h)27 b(satis\014es)g(the)h(follo)n(wing:)-85 3733 y Fp(P1)41 b Fo(All)28 b(sinks)f(are)g(in)h Fn(P)12 b Fo(.)-85 3895 y Fp(P2)41 b Fo(If)28 b Fn(x)c Fl(2)f Fn(N)37 b Fo(then)28 b(\000)646 3865 y Fk(+)701 3895 y Fo(\()p Fn(x)p Fo(\))19 b Fl(\\)g Fn(P)35 b Fl(6)p Fo(=)23 b Fl(;)p Fo(.)-85 4057 y Fp(P3)41 b Fo(If)28 b Fn(x)c Fl(2)f Fn(P)40 b Fo(then)28 b(\000)635 4027 y Fk(+)690 4057 y Fo(\()p Fn(x)p Fo(\))c Fl(\022)f Fn(N)9 b Fo(.)-85 4268 y(In)28 b(Game)f(1,)g Fn(P)35 b Fo(=)23 b Fl(f)p Fo(5)p Fn(k)i Fo(:)46 b Fn(k)26 b Fl(\025)c Fo(0)p Fl(g)27 b Fo(and)g(in)h(Game)g(2,) f Fn(P)35 b Fo(=)23 b Fl(f)p Fo(\()p Fn(x;)14 b(x)p Fo(\))23 b(:)47 b Fn(x)23 b Fl(\025)g Fo(0)p Fl(g)p Fo(.)-85 4421 y Fp(Sprague-Grundy)33 b(Num)m(b)s(ering)-85 4575 y Fo(F)-7 b(or)27 b Fn(S)g Fl(\022)c(f)p Fo(0)p Fn(;)14 b Fo(1)p Fn(;)g Fo(2)p Fn(;)g(:)g(:)g(:)25 b(;)14 b Fl(g)27 b Fo(let)1141 4674 y Fn(mex)p Fo(\()p Fn(S)5 b Fo(\))24 b(=)e(min)q Fl(f)p Fn(x)h Fl(\025)f Fo(0)h(:)46 b Fn(x)33 b(=)-51 b Fl(2)23 b Fn(S)5 b Fl(g)p Fn(:)-85 4817 y Fo(No)n(w)27 b(giv)n(en)g(an)g(acyclic)g(digraph)f Fn(D)g Fo(=)c Fn(X)r(;)14 b(A)28 b Fo(de\014ne)f Fn(g)k Fo(recursiv)n(ely)25 b(b)n(y)1086 5059 y Fn(g)s Fo(\()p Fn(x)p Fo(\))f(=)1352 4918 y Ff(\()1418 5003 y Fo(0)484 b Fn(x)28 b Fo(is)g(a)f(sink)1418 5122 y Fn(mex)p Fo(\(\000)1661 5092 y Fk(+)1717 5122 y Fo(\()p Fn(x)p Fo(\)\))84 b(otherwise)-85 5306 y Fn(g)s Fo(\()p Fn(x)p Fo(\))28 b(can)f(b)r(e)h(computed)g(in)g(rev)n(erse)e(top)r (ological)g(order.)1686 5555 y(2)p eop %%Page: 3 3 3 2 bop -85 223 a Fp(Lemma)29 b(1.)1370 323 y Fn(x)24 b Fl(2)f Fn(P)35 b Fl($)23 b Fn(g)s Fo(\()p Fn(x)p Fo(\))h(=)f(0)p Fn(:)-85 542 y Fp(Pro)s(of)191 b Fo(Clearly)26 b(P1)h(holds.)36 b(W)-7 b(e)28 b(c)n(hec)n(k)f(P2)g(and)g(P3.)-85 642 y(P2:)36 b(If)28 b Fn(g)s Fo(\()p Fn(x)p Fo(\))23 b Fn(>)g Fo(0)k(there)h(m)n(ust)f(b)r(e)h(a)g Fn(y)d Fl(2)f Fo(\000)1288 612 y Fk(+)1343 642 y Fo(\()p Fn(x)p Fo(\))k(with)g Fn(g)s Fo(\()p Fn(y)s Fo(\))23 b(=)g(0.)-85 742 y(P3:)36 b(If)28 b Fn(g)s Fo(\()p Fn(x)p Fo(\))23 b(=)g(0)k(there)h(cannot)f(b)r(e)h(a)f Fn(y)f Fl(2)d Fo(\000)1354 711 y Fk(+)1409 742 y Fo(\()p Fn(x)p Fo(\))29 b(with)f Fn(g)s Fo(\()p Fn(y)s Fo(\))23 b(=)f(0.)1373 b Fg(2)-85 895 y Fp(Sums)30 b(of)i(games)-85 1048 y Fo(Supp)r(ose)k(that)g(w)n(e)g(ha)n(v)n(e)e Fn(n)i Fo(games)f(with)i(digraphs)d Fn(D)1723 1060 y Fj(i)1788 1048 y Fo(=)i(\()p Fn(X)1990 1060 y Fj(i)2018 1048 y Fn(;)14 b(A)2117 1060 y Fj(i)2145 1048 y Fo(\))p Fn(;)28 b(i)36 b Fo(=)h(1)p Fn(;)14 b Fo(2)p Fn(;)g(:)g(:)g(:)26 b(;)14 b(n)p Fo(.)62 b(The)36 b(sum)g(of)g(these)-85 1148 y(games)25 b(is)h(pla)n(y)n(ed)f(as)g(follo)n(ws.)36 b(A)26 b(p)r(osition)g(is)g(a)f(v)n(ector)g(\()p Fn(x)1788 1160 y Fk(1)1826 1148 y Fn(;)14 b(x)1910 1160 y Fk(2)1948 1148 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(x)2193 1160 y Fj(n)2239 1148 y Fo(\))23 b Fl(2)h Fn(A)2435 1160 y Fk(1)2487 1148 y Fl(\002)15 b Fn(A)2629 1160 y Fk(2)2682 1148 y Fl(\002)g(\001)f(\001) g(\001)i(\002)f Fn(A)3017 1160 y Fj(n)3062 1148 y Fo(.)37 b(T)-7 b(o)25 b(mak)n(e)g(a)-85 1247 y(mo)n(v)n(e,)j(a)h(pla)n(y)n(er)e (c)n(ho)r(oses)h Fn(i)h Fo(suc)n(h)f(that)i Fn(x)1246 1259 y Fj(i)1303 1247 y Fo(is)f(not)g(a)g(sink)g(of)g Fn(D)1948 1259 y Fj(i)2004 1247 y Fo(and)g(then)h(replaces)e Fn(x)2721 1259 y Fj(i)2778 1247 y Fo(b)n(y)h Fn(y)f Fl(2)e Fo(\000)3097 1212 y Fk(+)3097 1270 y Fj(i)3152 1247 y Fo(\()p Fn(x)3231 1259 y Fj(i)3259 1247 y Fo(\).)42 b(The)-85 1347 y(game)27 b(ends)g(when)h(eac)n(h)f Fn(x)772 1359 y Fj(i)827 1347 y Fo(is)h(a)f(sink)h(of)f Fn(D)1317 1359 y Fj(i)1372 1347 y Fo(for)g Fn(i)c Fo(=)f(1)p Fn(;)14 b Fo(2)p Fn(;)g(:)g(:)g(:)27 b(;)14 b(n)p Fo(.)-85 1500 y Fp(Example)26 b Fo(Nim)-85 1653 y(In)33 b(a)f(one)g(pile)h(game,)g(w) n(e)f(start)h(with)g Fn(a)e Fl(\025)g Fo(0)h(c)n(hips)h(and)f(while)h (there)g(is)f(a)g(p)r(ositiv)n(e)h(n)n(um)n(b)r(er)f Fn(x)h Fo(of)g(c)n(hips,)g(a)-85 1753 y(mo)n(v)n(e)e(consists)g(of)h (deleting)g Fn(y)h Fl(\024)d Fn(x)i Fo(c)n(hips.)50 b(In)32 b(this)g(game)g(the)g(N-p)r(ositions)g(are)e(p)r(ositiv)n(e)i(in)n (tegers)f(and)h(the)-85 1853 y(unique)c(P-p)r(osition)e(is)i(0.)36 b(The)28 b(Sprague-Grundy)e(n)n(um)n(b)r(ering)h(is)g(de\014ned)h(b)n (y)g Fn(g)s Fo(\()p Fn(x)p Fo(\))23 b(=)g Fn(x)p Fo(.)-85 2006 y(In)k(general,)f(Nim)i(consists)e(of)i(the)f(sum)h(of)f Fn(n)g Fo(single)g(pile)g(games)g(stsrting)f(with)i Fn(a)2568 2018 y Fk(1)2605 2006 y Fn(;)14 b(a)2686 2018 y Fk(2)2723 2006 y Fn(;)g(:)g(:)g(:)28 b(;)14 b(a)2966 2018 y Fj(n)3034 2006 y Fn(>)22 b Fo(0.)37 b(A)27 b(mo)n(v)n(e)-85 2106 y(consists)g(of)g(deleting)h(some)f(c)n(hips)g(from)g(a)h(non-empt)n(y) f(pile.)-85 2259 y(W)-7 b(e)28 b(no)n(w)f(sho)n(w)f(ho)n(w)h(to)h (compute)g(the)g(Sprague-Grundy)e(n)n(um)n(b)r(ering)h(for)g(a)g(sum)h (of)f(games.)-85 2412 y(F)-7 b(or)27 b(binary)g(in)n(tegers)f Fn(a)e Fo(=)f Fn(a)832 2424 y Fj(m)895 2412 y Fn(a)939 2424 y Fj(m)p Fm(\000)p Fk(1)1100 2412 y Fl(\001)14 b(\001)g(\001)g Fn(a)1255 2424 y Fk(1)1292 2412 y Fn(a)1336 2424 y Fk(0)1401 2412 y Fo(and)28 b Fn(b)23 b Fo(=)g Fn(b)1746 2424 y Fj(m)1808 2412 y Fn(b)1844 2424 y Fj(m)p Fm(\000)p Fk(1)2006 2412 y Fl(\001)14 b(\001)g(\001)g Fn(b)2153 2424 y Fk(1)2189 2412 y Fn(b)2225 2424 y Fk(0)2290 2412 y Fo(w)n(e)28 b(de\014ne)g Fn(a)18 b Fl(\010)g Fn(b)23 b Fo(=)g Fn(c)2981 2424 y Fj(m)3044 2412 y Fn(c)3080 2424 y Fj(m)p Fm(\000)p Fk(1)3242 2412 y Fl(\001)14 b(\001)g(\001)g Fn(c)3389 2424 y Fk(1)3426 2412 y Fn(c)3462 2424 y Fk(0)-85 2512 y Fo(b)n(y)27 b Fn(c)66 2524 y Fj(i)117 2512 y Fo(=)22 b(1)27 b(if)i Fn(a)394 2524 y Fj(i)444 2512 y Fl(6)p Fo(=)23 b Fn(b)568 2524 y Fj(i)623 2512 y Fo(and)k Fn(c)820 2524 y Fj(i)871 2512 y Fo(=)22 b(0)28 b(if)g Fn(a)1148 2524 y Fj(i)1198 2512 y Fo(=)23 b Fn(b)1322 2524 y Fj(i)1377 2512 y Fo(for)k Fn(i)c Fo(=)f(1)p Fn(;)14 b Fo(2)p Fn(;)g(:)g(:)g(:)27 b(;)14 b(m)p Fo(.)-85 2665 y(So)27 b(for)g(example)g(11)18 b Fl(\010)g Fo(5)k(=)h(14.)-85 2831 y Fp(Theorem)30 b(2.)41 b Fh(If)22 b Fn(g)555 2843 y Fj(i)605 2831 y Fh(is)g(the)g(Spr)l (ague-Grundy)g(function)g(for)h(game)g Fn(i)f Fo(=)h(1)p Fn(;)14 b Fo(2)p Fn(;)g(:)g(:)g(:)26 b(;)14 b(n)22 b Fh(then)g(the)g(Spr)l(ague-Grundy)-85 2931 y(function)29 b Fn(g)k Fh(for)d(the)g(sum)f(of)i(the)f(games)g(is)g(de\014ne)l(d)g (by)1026 3113 y Fn(g)s Fo(\()p Fn(x)p Fo(\))24 b(=)f Fn(g)1332 3125 y Fk(1)1369 3113 y Fo(\()p Fn(x)1448 3125 y Fk(1)1486 3113 y Fo(\))18 b Fl(\010)g Fn(g)1659 3125 y Fk(2)1696 3113 y Fo(\()p Fn(x)1775 3125 y Fk(2)1813 3113 y Fo(\))h Fl(\010)f(\001)c(\001)g(\001)k(\010)g Fn(g)2185 3125 y Fj(n)2230 3113 y Fo(\()p Fn(x)2309 3125 y Fj(n)2355 3113 y Fo(\))-85 3296 y Fh(wher)l(e)30 b Fn(x)24 b Fo(=)e(\()p Fn(x)386 3308 y Fk(1)424 3296 y Fn(;)14 b(x)508 3308 y Fk(2)546 3296 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(x)791 3308 y Fj(n)837 3296 y Fo(\))p Fh(.)-85 3516 y Fp(Pro)s(of)191 b Fo(It)28 b(is)f(enough)g(to)g(sho)n(w)16 3735 y(1.)41 b(If)28 b Fn(x)c Fl(2)f Fn(X)34 b Fo(is)28 b(a)f(sink)g(of)h Fn(D)i Fo(then)e Fn(g)s Fo(\()p Fn(x)p Fo(\))23 b(=)g(0.)16 3901 y(2.)41 b(If)28 b Fn(x)c Fl(2)f Fn(X)34 b Fo(and)28 b Fn(g)s Fo(\()p Fn(x)p Fo(\))23 b(=)g Fn(b)g(>)f(a)h Fl(\025)g Fo(0)k(then)h(there)g(exists)f Fn(x)1932 3871 y Fm(0)1979 3901 y Fl(2)c Fo(\000)2109 3871 y Fk(+)2164 3901 y Fo(\()p Fn(x)p Fo(\))29 b(suc)n(h)e(that)h Fn(g)s Fo(\()p Fn(x)2793 3871 y Fm(0)2816 3901 y Fo(\))c(=)e Fn(a)p Fo(.)16 4067 y(3.)41 b(If)28 b Fn(x)c Fl(2)f Fn(X)34 b Fo(and)28 b Fn(g)s Fo(\()p Fn(x)p Fo(\))23 b(=)g Fn(b)k Fo(and)h Fn(x)1156 4037 y Fm(0)1202 4067 y Fl(2)c Fo(\000)1333 4037 y Fk(+)1388 4067 y Fo(\()p Fn(x)p Fo(\))29 b(then)f Fn(g)s Fo(\()p Fn(x)1839 4037 y Fm(0)1862 4067 y Fo(\))c Fl(6)p Fo(=)e Fn(g)s Fo(\()p Fn(x)p Fo(\).)-85 4287 y(1.)36 b(If)28 b Fn(x)c Fo(=)e(\()p Fn(x)336 4299 y Fk(1)374 4287 y Fn(;)14 b(x)458 4299 y Fk(2)496 4287 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(x)741 4299 y Fj(n)787 4287 y Fo(\))28 b(is)f(a)h(sink)f(then)h Fn(x)1409 4299 y Fj(i)1465 4287 y Fo(is)f(a)h(sink)f(of)g Fn(D)1954 4299 y Fj(i)2010 4287 y Fo(for)g Fn(i)22 b Fo(=)h(1)p Fn(;)14 b Fo(2)p Fn(;)g(:)g(:)g(:)26 b(;)14 b(n)p Fo(.)37 b(So)967 4470 y Fn(g)s Fo(\()p Fn(x)p Fo(\))83 b(=)g Fn(g)1392 4482 y Fk(1)1429 4470 y Fo(\()p Fn(x)1508 4482 y Fk(1)1546 4470 y Fo(\))18 b Fl(\010)g Fn(g)1719 4482 y Fk(2)1756 4470 y Fo(\()p Fn(x)1835 4482 y Fk(2)1873 4470 y Fo(\))h Fl(\010)f(\001)c(\001)g(\001)k(\010)g Fn(g)2245 4482 y Fj(n)2290 4470 y Fo(\()p Fn(x)2369 4482 y Fj(n)2415 4470 y Fo(\))1204 4594 y(=)83 b(0)18 b Fl(\010)g Fo(0)g Fl(\010)g(\001)c(\001)g(\001)k(\010)g Fo(0)1204 4719 y(=)83 b(0)p Fn(:)-85 4901 y Fo(2.)36 b(W)-7 b(rite)28 b Fn(d)23 b Fo(=)g Fn(a)18 b Fl(\010)g Fn(b)p Fo(.)37 b(Then)938 5084 y Fn(a)83 b Fo(=)f Fn(d)19 b Fl(\010)f Fn(b)1065 5209 y Fo(=)82 b Fn(d)19 b Fl(\010)f Fn(g)1397 5221 y Fk(1)1434 5209 y Fo(\()p Fn(x)1513 5221 y Fk(1)1551 5209 y Fo(\))h Fl(\010)f Fn(g)1725 5221 y Fk(2)1762 5209 y Fo(\()p Fn(x)1841 5221 y Fk(2)1879 5209 y Fo(\))g Fl(\010)g(\001)c (\001)g(\001)19 b(\010)f Fn(g)2251 5221 y Fj(n)2295 5209 y Fo(\()p Fn(x)2374 5221 y Fj(n)2420 5209 y Fo(\))p Fn(:)918 b Fo(\(1\))1686 5555 y(3)p eop %%Page: 4 4 4 3 bop -85 223 a Fo(No)n(w)32 b(supp)r(ose)g(that)h(w)n(e)g(can)f(sho) n(w)g(there)g(exists)h Fn(i)f Fo(suc)n(h)g(that)h Fn(d)22 b Fl(\010)g Fn(g)2189 235 y Fj(i)2216 223 y Fo(\()p Fn(x)2295 235 y Fj(i)2323 223 y Fo(\))32 b Fn(<)f(g)2523 235 y Fj(i)2551 223 y Fo(\()p Fn(x)2630 235 y Fj(i)2658 223 y Fo(\).)53 b(Then)32 b(since)h Fn(g)3236 235 y Fj(i)3263 223 y Fo(\()p Fn(x)3342 235 y Fj(i)3371 223 y Fo(\))e(=)-85 323 y Fn(mex)p Fo(\(\000)158 287 y Fk(+)158 346 y Fj(i)213 323 y Fo(\()p Fn(x)292 335 y Fj(i)320 323 y Fo(\)\))i(there)e(m)n(ust)h (exist)f Fn(x)1090 293 y Fm(0)1090 344 y Fj(i)1148 323 y Fl(2)f Fo(\000)1285 287 y Fk(+)1285 346 y Fj(i)1340 323 y Fo(\()p Fn(x)1419 335 y Fj(i)1447 323 y Fo(\))i(suc)n(h)f(that)h Fn(g)1926 335 y Fj(i)1954 323 y Fo(\()p Fn(x)2033 293 y Fm(0)2033 344 y Fj(i)2061 323 y Fo(\))e(=)f Fn(d)21 b Fl(\010)g Fn(g)2407 335 y Fj(i)2434 323 y Fo(\()p Fn(x)2513 335 y Fj(i)2542 323 y Fo(\).)49 b(Assume)31 b(without)h(loss)f(of)-85 422 y(generalit)n(y)26 b(that)i Fn(i)22 b Fo(=)h(1.)36 b(Then)28 b(from)f(\(1\))h(w)n(e)f(ha)n(v)n(e)713 573 y Fn(a)c Fo(=)f Fn(g)907 585 y Fk(1)944 573 y Fo(\()p Fn(x)1023 539 y Fm(0)1023 593 y Fk(1)1061 573 y Fo(\))d Fl(\010)f Fn(g)1235 585 y Fk(2)1272 573 y Fo(\()p Fn(x)1351 585 y Fk(2)1389 573 y Fo(\))g Fl(\010)g(\001)c(\001)g(\001)19 b(\010)f Fn(g)1761 585 y Fj(n)1806 573 y Fo(\()p Fn(x)1885 585 y Fj(n)1931 573 y Fo(\))23 b(=)g Fn(g)s Fo(\()p Fn(x)2196 539 y Fm(0)2196 593 y Fk(1)2233 573 y Fn(;)14 b(x)2317 585 y Fk(2)2355 573 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(x)2600 585 y Fj(n)2646 573 y Fo(\))p Fn(:)-85 723 y Fo(F)-7 b(urthermore,)26 b(\()p Fn(x)498 693 y Fm(0)498 744 y Fk(1)536 723 y Fn(;)14 b(x)620 735 y Fk(2)658 723 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(x)903 735 y Fj(n)949 723 y Fo(\))23 b Fl(2)h Fo(\000)1135 693 y Fk(+)1190 723 y Fo(\()p Fn(x)p Fo(\))k(and)g(so)f(w) n(e)g(will)h(ha)n(v)n(e)e(v)n(eri\014ed)h(2.)-85 877 y(Let)i(us)f(pro)n(v)n(e)f(that)i(suc)n(h)f(an)h Fn(i)f Fo(exists.)39 b(Supp)r(ose)29 b(that)g(2)1754 846 y Fj(k)q Fm(\000)p Fk(1)1904 877 y Fl(\024)24 b Fn(d)h(<)g Fo(2)2193 846 y Fj(k)2233 877 y Fo(.)40 b(Then)29 b Fn(d)g Fo(has)f(a)g(1)g(in)h (p)r(osition)g Fn(k)i Fo(and)-85 976 y(no)f(higher.)44 b(Since)30 b Fn(d)589 988 y Fj(k)658 976 y Fo(=)d Fn(a)794 988 y Fj(k)855 976 y Fl(\010)20 b Fn(b)976 988 y Fj(k)1047 976 y Fo(and)30 b Fn(a)d(<)h(b)i Fo(w)n(e)f(m)n(ust)i(ha)n(v)n(e)e Fn(a)2012 988 y Fj(k)2080 976 y Fo(=)e(0)j(and)g Fn(b)2444 988 y Fj(k)2512 976 y Fo(=)d(1.)45 b(Th)n(us)30 b(there)g(is)g(at)g (least)-85 1076 y(one)25 b Fn(i)h Fo(suc)n(h)g(that)h Fn(g)525 1088 y Fj(i)552 1076 y Fo(\()p Fn(x)631 1088 y Fj(i)659 1076 y Fo(\))g(has)e(a)h(1)g(in)g(p)r(osition)g Fn(k)s Fo(.)36 b(But)27 b(then)g Fn(d)15 b Fl(\010)g Fn(g)2045 1088 y Fj(i)2073 1076 y Fo(\()p Fn(x)2152 1088 y Fj(i)2180 1076 y Fo(\))23 b Fn(<)g(g)2363 1088 y Fj(i)2390 1076 y Fo(\()p Fn(x)2469 1088 y Fj(i)2498 1076 y Fo(\))j(since)g Fn(d)h Fo(\\destro)n(ys")c(the)k Fn(k)s Fo(th)-85 1175 y(bit)h(of)f Fn(g)178 1187 y Fj(i)206 1175 y Fo(\()p Fn(x)285 1187 y Fj(i)313 1175 y Fo(\))h(and)f(do)r(es)h(not)f(c)n (hange)g(an)n(y)g(higher)f(bit.)-85 1329 y(3.)35 b(Supp)r(ose)26 b(without)f(loss)g(of)g(generalit)n(y)f(that)h Fn(g)s Fo(\()p Fn(x)1573 1299 y Fm(0)1573 1349 y Fk(1)1611 1329 y Fn(;)14 b(x)1695 1341 y Fk(2)1732 1329 y Fn(;)g(:)g(:)g(:)28 b(;)14 b(x)1978 1341 y Fj(n)2023 1329 y Fo(\))23 b(=)g Fn(g)s Fo(\()p Fn(x)2288 1341 y Fk(1)2326 1329 y Fn(;)14 b(x)2410 1341 y Fk(2)2447 1329 y Fn(;)g(:)g(:)g(:)28 b(;)14 b(x)2693 1341 y Fj(n)2738 1329 y Fo(\))26 b(where)e Fn(x)3080 1299 y Fm(0)3080 1349 y Fk(1)3141 1329 y Fl(2)g Fo(\000)3272 1299 y Fk(+)3327 1329 y Fo(\()p Fn(x)3406 1341 y Fk(1)3444 1329 y Fo(\).)-85 1428 y(Then)j Fn(g)171 1440 y Fk(1)208 1428 y Fo(\()p Fn(x)287 1398 y Fm(0)287 1449 y Fk(1)325 1428 y Fo(\))18 b Fl(\010)f Fn(g)497 1440 y Fk(2)534 1428 y Fo(\()p Fn(x)613 1440 y Fk(2)651 1428 y Fo(\))h Fl(\010)g(\001)c(\001)g(\001)j(\010)h Fn(g)1021 1440 y Fj(n)1065 1428 y Fo(\()p Fn(x)1144 1440 y Fj(n)1190 1428 y Fo(\))24 b(=)e Fn(g)1373 1440 y Fk(1)1410 1428 y Fo(\()p Fn(x)1489 1440 y Fk(1)1527 1428 y Fo(\))c Fl(\010)f Fn(g)1699 1440 y Fk(2)1736 1428 y Fo(\()p Fn(x)1815 1440 y Fk(2)1853 1428 y Fo(\))h Fl(\010)g(\001)c(\001)g(\001)j(\010)h Fn(g)2223 1440 y Fj(n)2267 1428 y Fo(\()p Fn(x)2346 1440 y Fj(n)2392 1428 y Fo(\))28 b(implies)f(that)h Fn(g)2953 1440 y Fk(1)2990 1428 y Fo(\()p Fn(x)3069 1398 y Fm(0)3069 1449 y Fk(1)3107 1428 y Fo(\))23 b(=)g Fn(g)3290 1440 y Fk(1)3327 1428 y Fo(\()p Fn(x)3406 1440 y Fk(1)3444 1428 y Fo(\),)-85 1528 y(con)n(tradition.)3057 b Fg(2)-85 1681 y Fo(If)29 b(w)n(e)g(apply)g(this)g(theorem)g(to)g(the)g(game)f (of)h(Nim)h(then)g(if)f(the)h(p)r(osition)f Fn(x)g Fo(consists)f(of)h (piles)h(of)f Fn(x)3131 1693 y Fj(i)3188 1681 y Fo(c)n(hips)g(for)-85 1781 y Fn(i)22 b Fo(=)h(1)p Fn(;)14 b Fo(2)p Fn(;)g(:)g(:)g(:)26 b(;)14 b(n)28 b Fo(then)g Fn(g)s Fo(\()p Fn(x)p Fo(\))c(=)e Fn(x)951 1793 y Fk(1)1007 1781 y Fl(\010)c Fn(x)1137 1793 y Fk(2)1193 1781 y Fl(\010)h(\001)14 b(\001)g(\001)k(\010)g Fn(x)1522 1793 y Fj(n)1567 1781 y Fo(.)-85 1934 y(Sums)28 b(of)f(other)g(subtraction)g(games:)-85 2087 y(In)h(our)e(\014rst)i (example,)f Fn(g)s Fo(\()p Fn(x)p Fo(\))d(=)e Fn(x)56 b Fo(mo)r(d)28 b(5)f(and)g(so)g(for)g(the)h(sum)g(of)g Fn(n)f Fo(suc)n(h)g(games)g(w)n(e)g(ha)n(v)n(e)442 2238 y Fn(g)s Fo(\()p Fn(x)564 2250 y Fk(1)602 2238 y Fn(;)14 b(x)686 2250 y Fk(2)723 2238 y Fn(;)g(:)g(:)g(:)28 b(;)14 b(x)969 2250 y Fj(n)1014 2238 y Fo(\))24 b(=)e(\()p Fn(x)1236 2250 y Fk(1)1357 2238 y Fo(mo)r(d)28 b(5\))18 b Fl(\010)g Fo(\()p Fn(x)1798 2250 y Fk(2)1919 2238 y Fo(mo)r(d)28 b(5\))18 b Fl(\010)h(\001)14 b(\001)g(\001)k(\010)g Fo(\()p Fn(x)2559 2250 y Fj(n)2688 2238 y Fo(mo)r(d)28 b(5\))p Fn(:)-85 2442 y Fo(Another)f(subtraction)g(game.)-85 2542 y(One)g(pile:)39 2736 y Fl(\017)41 b Fo(A)28 b(pla)n(y)n(er)e(can) h(remo)n(v)n(e)f(an)n(y)h(ev)n(en)g(n)n(um)n(b)r(er)h(of)f(c)n(hips,)h (but)g(not)f(the)h(whole)g(pile.)39 2889 y Fl(\017)41 b Fo(A)28 b(pla)n(y)n(er)e(can)h(remo)n(v)n(e)f(the)i(whole)g(pile)f (if)h(it)g(is)g(o)r(dd.)-85 3083 y(The)f(terminal)h(p)r(ositions)f(are) f(0)i(or)e(2.)-85 3223 y Fp(Lemma)j(2.)41 b Fn(g)s Fo(\(0\))23 b(=)f(0)p Fh(,)30 b Fn(g)s Fo(\(2)p Fn(k)s Fo(\))23 b(=)f Fn(k)g Fl(\000)c Fo(1)29 b Fh(and)h Fn(g)s Fo(\(2)p Fn(k)21 b Fl(\000)d Fo(1\))23 b(=)f Fn(k)33 b Fh(for)d Fn(k)c Fl(\025)d Fo(1)p Fh(.)-85 3417 y Fp(Pro)s(of)191 b Fo(0,2)31 b(are)f(terminal)i(p)r(ostions)f(and)h(so)f Fn(g)s Fo(\(0\))f(=)g Fn(g)s Fo(\(2\))f(=)h(0.)49 b Fn(g)s Fo(\(1\))30 b(=)g(1)h(b)r(ecause)h (the)g(only)f(p)r(osition)-85 3517 y(one)c(can)g(mo)n(v)n(e)g(to)g (from)g(1)h(is)f(0.)36 b(W)-7 b(e)28 b(pro)n(v)n(e)e(the)i(remainder)f (b)n(y)g(induction)h(on)g Fn(k)s Fo(.)-85 3670 y(Assume)f(that)h Fn(k)e(>)d Fo(1.)823 3820 y Fn(g)s Fo(\(2)p Fn(k)s Fo(\))82 b(=)h Fn(mex)p Fl(f)p Fn(g)s Fo(\(2)p Fn(k)20 b Fl(\000)e Fo(2\))p Fn(;)c(g)s Fo(\(2)p Fn(k)20 b Fl(\000)e Fo(4\))p Fn(;)c(:)g(:)g(:)27 b(;)14 b(g)s Fo(\(2\))p Fl(g)1100 3945 y Fo(=)83 b Fn(mex)p Fl(f)p Fn(k)20 b Fl(\000)f Fo(2)p Fn(;)14 b(k)20 b Fl(\000)e Fo(3)p Fn(;)c(:)g(:)g(:)27 b(;)14 b Fo(0)p Fl(g)1100 4069 y Fo(=)83 b Fn(k)21 b Fl(\000)d Fo(1)p Fn(:)680 4194 y(g)s Fo(\(2)p Fn(k)i Fl(\000)e Fo(1\))83 b(=)g Fn(mex)p Fl(f)p Fn(g)s Fo(\(2)p Fn(k)20 b Fl(\000)e Fo(3\))p Fn(;)c(g)s Fo(\(2)p Fn(k)20 b Fl(\000)e Fo(5\))p Fn(;)c(:)g(:)g(:)27 b(;)14 b(g)s Fo(\(1\))p Fn(;)g(g)s Fo(\(0\))p Fl(g)1100 4319 y Fo(=)83 b Fn(mex)p Fl(f)p Fn(k)20 b Fl(\000)f Fo(1)p Fn(;)14 b(k)20 b Fl(\000)e Fo(2)p Fn(;)c(:)g(:)g(:)27 b(;)14 b Fo(0)p Fl(g)1100 4443 y Fo(=)83 b Fn(k)s(:)3437 4594 y Fg(2)-85 4747 y Fp(A)32 b(more)e(complicated)g(one)i(pile)e(game)-85 4900 y Fo(Start)d(with)h Fn(n)g Fo(c)n(hips.)36 b(First)28 b(pla)n(y)n(er)e(can)h(remo)n(v)n(e)f(up)i(to)f Fn(n)19 b Fl(\000)f Fo(1)27 b(c)n(hips.)-85 5053 y(In)h(general,)e(if)i(the)g (previous)e(pla)n(y)n(er)g(to)r(ok)h Fn(x)i Fo(c)n(hips,)e(then)h(the)g (next)g(pla)n(y)n(er)e(can)h(tak)n(e)g Fn(y)f Fl(\024)c Fn(x)28 b Fo(c)n(hips.)-85 5207 y(Th)n(us)g(a)g(games)f(p)r(osition)h (can)g(b)r(e)g(represen)n(ted)g(b)n(y)g(\()p Fn(n;)14 b(x)p Fo(\))29 b(where)e Fn(n)i Fo(is)f(the)g(curren)n(t)g(size)g(of)g (the)h(pile)f(and)g Fn(x)h Fo(is)-85 5306 y(the)f(maxim)n(um)f(n)n(um)n (b)r(er)g(of)h(c)n(hips)f(that)h(can)f(b)r(e)h(remo)n(v)n(ed)e(in)i (this)g(round.)1686 5555 y(4)p eop %%Page: 5 5 5 4 bop -85 223 a Fp(Theorem)30 b(3.)41 b Fh(Supp)l(o)l(ose)30 b(that)g(the)g(p)l(osition)h(is)f Fo(\()p Fn(n;)14 b(x)p Fo(\))30 b Fh(wher)l(e)h Fn(n)23 b Fo(=)f Fn(m)p Fo(2)2237 193 y Fj(k)2307 223 y Fh(and)31 b Fn(m)e Fh(is)h(o)l(dd.)40 b(Then,)-85 443 y Fp(\(a\))i Fh(This)31 b(is)f(an)g(N-p)l(osition)g(if) h Fn(x)23 b Fl(\025)g Fo(2)1160 413 y Fj(k)1200 443 y Fh(.)-85 609 y Fp(\(b\))42 b Fh(This)30 b(is)h(a)f(P-p)l(osition)h(if)f Fn(m)23 b Fo(=)g(1)29 b Fh(and)h Fn(x)24 b(<)e(n)p Fh(.)-85 828 y Fp(Pro)s(of)191 b Fo(F)-7 b(or)33 b(a)g(non-negativ)n(e)f(in)n (teger)h Fn(n)g Fo(=)g Fn(m)p Fo(2)1640 798 y Fj(k)1681 828 y Fo(,)i(let)f Fl(h)p Fn(n)p Fl(i)g Fo(denote)g(the)g(n)n(um)n(b)r (er)g(of)g(bits)g(in)g(the)g(binary)-85 928 y(expansion)f(of)h Fn(n)h Fo(and)f(let)g Fn(k)j Fo(=)d Fn(\032)p Fo(\()p Fn(n)p Fo(\))h(determine)f(the)h(p)r(osition)f(of)g(the)h(righ)n (t-most)e(one)h(in)g(this)h(expansion.)-85 1028 y(W)-7 b(e)29 b(claim)g(that)g(the)g(follo)n(wing)f(strategy)f(is)i(a)g(win)g (for)f(the)h(pla)n(y)n(er)f(in)h(a)f(p)r(ostion)h(describ)r(ed)f(in)i (\(a\):)39 b(Remo)n(v)n(e)-85 1127 y Fn(y)25 b Fo(=)e(2)111 1097 y Fj(k)179 1127 y Fo(c)n(hips.)37 b(Supp)r(ose)27 b(this)h(pla)n(y)n(er)e(is)i(A.)-85 1281 y(If)h Fn(m)24 b Fo(=)h(1)j(then)h Fn(x)c Fl(\025)g Fn(n)j Fo(and)h(A)f(wins.)40 b(Otherwise,)28 b(after)h(suc)n(h)f(a)g(mo)n(v)n(e)g(the)h(p)r(osition) f(is)h(\()p Fn(n)2881 1250 y Fm(0)2904 1281 y Fn(;)14 b(y)s Fo(\))29 b(where)f(where)-85 1380 y Fn(\032)p Fo(\()p Fn(n)40 1350 y Fm(0)63 1380 y Fo(\))35 b Fn(>)e(\032)p Fo(\()p Fn(n)p Fo(\).)58 b(Note)34 b(\014rst)g(that)h Fl(h)p Fn(n)1120 1350 y Fm(0)1143 1380 y Fl(i)f Fo(=)g Fl(h)p Fn(n)p Fl(i)24 b(\000)e Fo(1)34 b Fn(>)g Fo(0.)56 b(Th)n(us)34 b(B)g(cannot)g(win)h(at)f(this)g(p)r(oin)n(t.)57 b(Second,)36 b(B)-85 1480 y(cannot)27 b(remo)n(v)n(e)f(more)h(than)h(2) 915 1450 y Fj(k)984 1480 y Fo(c)n(hips)f(and)h(so)f(if)h(B)g(mo)n(v)n (es)f(the)h(p)r(osition)g(to)f(\()p Fn(n)2512 1450 y Fm(0)q(0)2555 1480 y Fn(;)14 b(x)2639 1450 y Fm(00)2682 1480 y Fo(\))28 b(then)g Fl(h)p Fn(n)3013 1450 y Fm(00)3056 1480 y Fl(i)c(\025)f(h)p Fn(n)3282 1450 y Fm(0)3305 1480 y Fl(i)28 b Fo(and)-85 1579 y(furthermore,)f Fn(x)445 1549 y Fm(00)511 1579 y Fl(\025)d Fo(2)642 1549 y Fj(\032)p Fk(\()p Fj(n)743 1524 y Fe(00)783 1549 y Fk(\))813 1579 y Fo(,)29 b(since)e Fn(x)1115 1549 y Fm(0)q(0)1186 1579 y Fo(m)n(ust)h(ha)n(v)n(e)f(a)h(1)f(in)h(p)r(osition)g Fn(\032)p Fo(\()p Fn(n)2262 1549 y Fm(00)2305 1579 y Fo(\).)38 b(Th)n(us,)28 b(b)n(y)g(induction,)g(A)g(is)g(in)g(an)-85 1679 y(N-p)r(osition)f(and)h(wins)f(the)h(game.)-85 1832 y(T)-7 b(o)27 b(pro)n(v)n(e)f(\(b\),)i(note)g(that)g(after)f(the)h (\014rst)f(mo)n(v)n(e,)g(the)h(p)r(osition)f(satis\014es)g(the)h (conditions)f(of)h(\(a\).)350 b Fg(2)p Fo(.)-85 1986 y(Let)30 b(us)g(next)g(consider)f(a)h(generalisation)e(of)i(this)g (game.)43 b(There)30 b(are)f(2)h(pla)n(y)n(ers)e(A)i(and)g(B)g(and)g(A) g(go)r(es)f(\014rst.)-85 2085 y(W)-7 b(e)26 b(ha)n(v)n(e)f(a)h (non-decreasing)e(function)i Fn(f)35 b Fo(from)26 b Fd(N)32 b Fl(!)23 b Fd(N)36 b Fo(where)25 b Fd(N)33 b Fo(=)22 b Fl(f)p Fo(1)p Fn(;)14 b Fo(2)p Fn(;)g(:)g(:)g(:)e Fl(g)26 b Fo(whic)n(h)g(satis\014es)f Fn(f)9 b Fo(\()p Fn(x)p Fo(\))24 b Fl(\025)e Fn(x)p Fo(.)-85 2185 y(A)n(t)32 b(the)f(\014rst)h(mo)n(v)n(e)e(A)i(tak)n(es)f(an)n(y)f(n)n(um)n(b)r(er) i(less)f(than)g Fn(h)h Fo(from)f(the)h(pile,)h(where)e Fn(h)g Fo(is)g(the)h(size)f(of)h(the)g(initial)-85 2284 y(pile.)48 b(Then)31 b(on)g(a)g(subsequen)n(t)g(mo)n(v)n(e,)g(if)h(a)f (pla)n(y)n(er)e(tak)n(es)i Fn(x)g Fo(c)n(hips)g(then)h(the)g(next)f (pla)n(y)n(er)f(is)h(constrained)f(to)-85 2384 y(tak)n(e)d(at)g(most)g Fn(f)9 b Fo(\()p Fn(x)p Fo(\))29 b(c)n(hips.)36 b(Th)n(us)28 b(the)g(ab)r(o)n(v)n(e)e(considered)g(the)i(cases)f Fn(f)9 b Fo(\()p Fn(x)p Fo(\))24 b(=)e Fn(x)p Fo(.)-85 2537 y(There)32 b(is)h(a)g(set)f Fl(H)h Fo(=)f Fl(f)p Fn(H)769 2549 y Fk(1)838 2537 y Fo(=)f(1)h Fn(<)f(H)1173 2549 y Fk(2)1242 2537 y Fn(<)h(:)14 b(:)g(:)g Fl(g)32 b Fo(of)h(initial)g (pile)h(sizes)e(for)g(whic)n(h)h(the)h(\014rst)e(pla)n(y)n(er)g(will)h (lose,)-85 2637 y(assuming)d(that)h(the)g(second)f(pla)n(y)n(er)f(pla)n (ys)h(optimally)-7 b(.)47 b(Also,)31 b(if)g(the)g(initial)g(pile)g (size)g Fn(h)37 b(=)-51 b Fl(2)29 b(H)j Fo(then)f(the)g(\014rst)-85 2737 y(pla)n(y)n(er)26 b(has)h(a)g(winning)h(strategy)-7 b(.)35 b(It)28 b(will)g(turn)g(out)f(that)h(the)g(sequence)f (satis\014es)g(the)h(recurrence:)472 2919 y Fn(H)541 2931 y Fj(j)s Fk(+1)683 2919 y Fo(=)23 b Fn(H)840 2931 y Fj(j)893 2919 y Fo(+)18 b Fn(H)1045 2931 y Fj(`)1105 2919 y Fo(where)27 b Fn(H)1414 2931 y Fj(`)1469 2919 y Fo(=)c(min)1573 2973 y Fj(i)p Fm(\024)p Fj(j)1695 2919 y Fl(f)p Fn(H)1806 2931 y Fj(i)1856 2919 y Fl(j)h Fn(f)9 b Fo(\()p Fn(H)2054 2931 y Fj(i)2081 2919 y Fo(\))23 b Fl(\025)g Fn(H)2293 2931 y Fj(j)2328 2919 y Fl(g)p Fn(;)207 b Fo(for)27 b Fn(j)h Fl(\025)23 b Fo(0)p Fn(:)451 b Fo(\(2\))-85 3141 y(Note)27 b(that)1473 3324 y Fn(H)1542 3336 y Fj(j)s Fk(+1)1684 3324 y Fl(\024)c Fo(2)p Fn(H)1883 3336 y Fj(j)1917 3324 y Fn(:)1453 b Fo(\(3\))-85 3507 y([The)28 b(reader)f(should)i(c)n(hec)n(k)e(that)i(if)g Fn(f)9 b Fo(\()p Fn(x)p Fo(\))26 b(=)e Fn(x)29 b Fo(then)g Fn(H)1722 3519 y Fj(i)1774 3507 y Fo(=)24 b(2)1905 3477 y Fj(i)1933 3507 y Fo(.)39 b(Another)29 b(case)e(to)i(c)n(hec)n(k)e(is) i Fn(f)9 b Fo(\()p Fn(x)p Fo(\))25 b(=)f(2)p Fn(x)p Fo(.)40 b(This)-85 3606 y(giv)n(es)26 b Fl(H)e Fo(=)f Fl(f)p Fo(1)p Fn(;)14 b Fo(2)p Fn(;)g Fo(3)p Fn(;)g Fo(5)p Fn(;)g Fo(8)p Fn(;)g(:)g(:)g(:)24 b(;)14 b Fl(g)27 b Fo(i.e.)37 b(the)28 b(Fib)r(onacci)f(sequence.])-85 3760 y(The)g(k)n(ey)g(to)h (the)g(game)f(is)g(the)h(follo)n(wing)f(result.)-85 3926 y Fp(Theorem)j(4.)41 b Fh(Every)31 b(p)l(ositive)g(inte)l(ger)f Fn(n)f Fh(c)l(an)h(b)l(e)g Fp(uniquely)f Fh(written)g(as)i(the)e(sum) 1225 4108 y Fn(n)23 b Fo(=)g Fn(H)1455 4120 y Fj(j)1482 4128 y Fc(1)1537 4108 y Fo(+)18 b Fn(H)1689 4120 y Fj(j)1716 4128 y Fc(2)1772 4108 y Fo(+)g Fl(\001)c(\001)g(\001)k Fo(+)g Fn(H)2122 4120 y Fj(j)2149 4128 y Fb(p)3393 4108 y Fo(\(4\))-85 4291 y Fh(wher)l(e)30 b Fn(f)9 b Fo(\()p Fn(H)300 4303 y Fj(j)327 4311 y Fb(i)358 4291 y Fo(\))23 b Fn(<)g(H)570 4303 y Fj(j)597 4311 y Fb(i)p Fc(+1)729 4291 y Fh(for)30 b Fo(1)23 b Fl(\024)f Fn(i)h(<)g(p)p Fh(.)-85 4511 y Fp(Pro)s(of)191 b Fo(W)-7 b(e)28 b(pro)n(v)n(e)d(this)j (b)n(y)g(induction)g(on)f Fn(n)p Fo(.)37 b(If)28 b Fn(n)23 b Fo(=)f(1)28 b(then)g Fn(n)23 b Fo(=)f Fn(H)2307 4523 y Fk(1)2372 4511 y Fo(is)28 b(the)g(unique)f(decomp)r(osition.)-85 4664 y Fp(Existence)-85 4763 y Fo(Assume)k(that)h(an)n(y)f Fn(n)e(<)g(H)813 4775 y Fj(k)885 4763 y Fo(can)i(b)r(e)h(represen)n (ted)e(as)h(a)g(sum)h(of)f(distinct)h Fn(H)2433 4775 y Fj(j)2460 4783 y Fb(i)2491 4763 y Fo('s)f(with)h Fn(f)9 b Fo(\()p Fn(H)2922 4775 y Fj(j)2949 4783 y Fb(i)2980 4763 y Fo(\))30 b Fn(<)f(H)3205 4775 y Fj(j)3232 4783 y Fb(i)p Fc(+1)3365 4763 y Fo(and)-85 4863 y(supp)r(ose)e(that)h Fn(H)476 4875 y Fj(k)540 4863 y Fl(\024)22 b Fn(n)h(<)g(H)857 4875 y Fj(k)q Fk(+1)982 4863 y Fo(.)37 b(Inequalit)n(y)28 b(\(3\))g(implies)g(that)f Fn(n)19 b Fl(\000)f Fn(H)2251 4875 y Fj(k)2315 4863 y Fn(<)k(H)2471 4875 y Fj(k)2512 4863 y Fo(.)-85 5016 y(It)28 b(follo)n(ws)e(b)n(y)i(induction)g(that) 1218 5199 y Fn(n)19 b Fl(\000)f Fn(H)1439 5211 y Fj(k)1503 5199 y Fo(=)k Fn(H)1659 5211 y Fj(j)1686 5219 y Fc(1)1742 5199 y Fo(+)c Fl(\001)c(\001)g(\001)k Fo(+)g Fn(H)2092 5211 y Fj(j)2119 5219 y Fb(p)2159 5199 y Fn(;)1211 b Fo(\(5\))1686 5555 y(5)p eop %%Page: 6 6 6 5 bop -85 223 a Fo(where)24 b Fn(f)9 b Fo(\()p Fn(H)303 235 y Fj(j)330 243 y Fb(i)361 223 y Fo(\))23 b Fn(<)g(H)573 235 y Fj(j)600 243 y Fb(i)p Fc(+1)726 223 y Fo(for)h Fn(i)f Fo(=)g(1)p Fn(;)14 b Fo(2)p Fn(;)g(:::;)g(p)e Fl(\000)g Fo(1.)34 b(T)-7 b(o)24 b(establish)h(existence)f(w)n(e)g (need)h(only)f(sho)n(w)g(that)h Fn(f)9 b Fo(\()p Fn(H)3313 235 y Fj(j)3340 243 y Fb(p)3379 223 y Fo(\))23 b Fn(<)-85 323 y(H)-16 335 y Fj(k)25 323 y Fo(.)37 b(Assume)27 b(to)h(the)g(con)n (trary)d(that)j Fn(f)9 b Fo(\()p Fn(H)1300 335 y Fj(j)1327 343 y Fb(p)1366 323 y Fo(\))24 b Fl(\025)e Fn(H)1578 335 y Fj(k)1619 323 y Fo(.)37 b(But)28 b(then)g(for)f(some)g Fn(m)c Fl(\024)g Fn(j)2586 335 y Fj(p)2652 323 y Fo(w)n(e)k(ha)n(v)n(e) 1062 505 y Fn(H)1131 517 y Fj(k)q Fk(+1)1279 505 y Fo(=)c Fn(H)1436 517 y Fj(k)1495 505 y Fo(+)18 b Fn(H)1647 517 y Fj(m)1733 505 y Fl(\024)23 b Fn(H)1890 517 y Fj(k)1949 505 y Fo(+)18 b Fn(H)2101 517 y Fj(j)2128 525 y Fb(p)2191 505 y Fl(\024)23 b Fn(n;)-85 688 y Fo(con)n(tradicting)j(the)i(c)n (hoice)f(of)g Fn(n)p Fo(.)-85 841 y Fp(Uniqueness)-85 994 y Fo(W)-7 b(e)28 b(will)g(\014rst)f(pro)n(v)n(e)f(b)n(y)h (induction)h(on)f Fn(p)h Fo(that)g(if)g Fn(f)9 b Fo(\()p Fn(H)1686 1006 y Fj(j)1713 1014 y Fb(i)1744 994 y Fo(\))23 b Fn(<)g(H)1956 1006 y Fj(j)1983 1014 y Fb(i)p Fc(+1)2112 994 y Fo(for)k(1)c Fl(\024)f Fn(i)h(<)g(p)k Fo(then)1129 1177 y Fn(H)1198 1189 y Fj(j)1225 1197 y Fc(1)1280 1177 y Fo(+)18 b Fn(H)1432 1189 y Fj(j)1459 1197 y Fc(2)1515 1177 y Fo(+)g Fl(\001)c(\001)g(\001)k Fo(+)g Fn(H)1865 1189 y Fj(j)1892 1197 y Fb(p)1955 1177 y Fn(<)k(H)2111 1189 y Fj(j)2138 1197 y Fb(p)2174 1189 y Fk(+1)2262 1177 y Fn(:)1108 b Fo(\(6\))-85 1360 y(If)27 b Fn(p)c Fo(=)f(2)k(then)h(w)n (e)g(are)e(sa)n(ying)g(that)i(if)g Fn(f)9 b Fo(\()p Fn(H)1322 1372 y Fj(j)1349 1380 y Fc(1)1386 1360 y Fo(\))24 b Fn(<)e(H)1598 1372 y Fj(j)1625 1380 y Fc(2)1689 1360 y Fo(then)27 b Fn(H)1946 1372 y Fj(j)1973 1380 y Fc(1)2027 1360 y Fo(+)16 b Fn(H)2177 1372 y Fj(j)2204 1380 y Fc(2)2264 1360 y Fn(<)22 b(H)2420 1372 y Fj(j)2447 1380 y Fc(2)2480 1372 y Fk(+1)2568 1360 y Fo(.)37 b(But)27 b(this)g(follo)n(ws)e(directly)-85 1459 y(from)i Fn(H)180 1471 y Fj(j)207 1479 y Fc(2)240 1471 y Fk(+1)351 1459 y Fo(=)c Fn(H)508 1471 y Fj(j)535 1479 y Fc(2)590 1459 y Fo(+)18 b Fn(H)742 1471 y Fj(m)833 1459 y Fo(where)27 b Fn(f)9 b Fo(\()p Fn(H)1224 1471 y Fj(m)1287 1459 y Fo(\))23 b Fl(\025)g Fn(H)1499 1471 y Fj(j)1526 1479 y Fc(2)1591 1459 y Fo(i.e.)37 b Fn(H)1803 1471 y Fj(m)1889 1459 y Fn(>)23 b(H)2046 1471 y Fj(j)2073 1479 y Fc(1)2110 1459 y Fo(.)-85 1613 y(So)k(assume)g(that)h(\(6\))g (is)f(true)h(for)f Fn(p)22 b Fl(\025)h Fo(2.)37 b(No)n(w)908 1795 y Fn(H)977 1807 y Fj(j)1004 1815 y Fb(p)p Fc(+1)1111 1807 y Fk(+1)1222 1795 y Fo(=)23 b Fn(H)1379 1807 y Fj(j)1406 1815 y Fb(p)p Fc(+1)1534 1795 y Fo(+)18 b Fn(H)1686 1807 y Fj(m)1777 1795 y Fo(and)28 b Fn(f)9 b Fo(\()p Fn(H)2090 1807 y Fj(j)2117 1815 y Fb(p)2156 1795 y Fo(\))23 b Fn(<)g(H)2368 1807 y Fj(j)2395 1815 y Fb(p)p Fc(+1)-85 1978 y Fo(implies)28 b(that)f Fn(m)c Fl(\025)g Fn(j)594 1990 y Fj(p)651 1978 y Fo(+)18 b(1.)-85 2131 y(Th)n(us)853 2314 y Fn(H)922 2326 y Fj(j)949 2334 y Fb(p)p Fc(+1)1055 2326 y Fk(+1)1227 2314 y Fl(\025)82 b Fn(H)1443 2326 y Fj(j)1470 2334 y Fb(p)p Fc(+1)1599 2314 y Fo(+)18 b Fn(H)1751 2326 y Fj(j)1778 2334 y Fb(p)1813 2326 y Fk(+1)1227 2438 y Fn(>)82 b(H)1443 2450 y Fj(j)1470 2458 y Fb(p)p Fc(+1)1599 2438 y Fo(+)18 b Fn(H)1751 2450 y Fj(j)1778 2458 y Fb(p)1836 2438 y Fo(+)g Fn(H)1988 2450 y Fj(j)2015 2458 y Fb(p)p Fe(\000)p Fc(1)2146 2438 y Fo(+)g Fl(\001)c(\001)g(\001)19 b Fo(+)f Fn(H)2497 2450 y Fj(j)2524 2458 y Fc(1)-85 2621 y Fo(after)27 b(applying)g(induction)h(to)f(get)h(the)g(second)f(inequalit)n(y)-7 b(.)-85 2774 y(This)27 b(completes)h(the)g(induction)g(for)f(\(6\).)-85 2927 y(No)n(w)f(assume)g(b)n(y)g(induction)h(on)f Fn(k)k Fo(that)d Fn(n)c(<)f(H)1466 2939 y Fj(k)1534 2927 y Fo(has)k(a)g (unique)h(decomp)r(osition)f(\(4\).)36 b(This)27 b(is)f(true)h(for)f Fn(k)g Fo(=)c(2)-85 3027 y(and)27 b(so)g(no)n(w)g(assume)g(that)h Fn(k)e Fl(\025)c Fo(2)28 b(and)f Fn(H)1274 3039 y Fj(k)1338 3027 y Fl(\024)c Fn(n)f(<)h(H)1655 3039 y Fj(k)q Fk(+1)1780 3027 y Fo(.)37 b(Consider)27 b(a)g(decomp)r(osition)1214 3210 y Fn(n)c Fo(=)f Fn(H)1443 3222 y Fj(j)1470 3230 y Fc(1)1526 3210 y Fo(+)c Fn(H)1678 3222 y Fj(j)1705 3230 y Fc(2)1760 3210 y Fo(+)g Fl(\001)c(\001)g(\001)19 b Fo(+)f Fn(H)2111 3222 y Fj(j)2138 3230 y Fb(p)2177 3210 y Fn(:)-85 3392 y Fo(It)26 b(follo)n(ws)e(from)i(\(6\))g(that)f Fn(j)811 3404 y Fj(p)873 3392 y Fo(=)e Fn(k)s Fo(.)36 b(Indeed,)26 b Fn(j)1391 3404 y Fj(p)1453 3392 y Fl(\024)d Fn(k)28 b Fo(since)e Fn(n)c(<)h(H)2043 3404 y Fj(k)q Fk(+1)2194 3392 y Fo(and)i(if)h Fn(j)2461 3404 y Fj(p)2523 3392 y Fn(<)d(k)28 b Fo(then)e Fn(H)2938 3404 y Fj(j)2965 3412 y Fc(1)3017 3392 y Fo(+)14 b Fn(H)3165 3404 y Fj(j)3192 3412 y Fc(2)3244 3392 y Fo(+)g Fl(\001)g(\001)g(\001)g Fo(+)-85 3492 y Fn(H)-16 3504 y Fj(j)11 3512 y Fb(p)73 3492 y Fn(<)23 b(H)230 3504 y Fj(j)257 3512 y Fb(p)292 3504 y Fk(+1)404 3492 y Fl(\024)f Fn(H)560 3504 y Fj(k)601 3492 y Fo(,)28 b(con)n(tradicting)e(our)h(c)n(hoice)g(of)g Fn(n)p Fo(.)37 b(So)27 b Fn(H)1940 3504 y Fj(k)2009 3492 y Fo(app)r(ears)f(in)i(ev)n(ery)e(decomp)r(osition)h(of)h Fn(n)p Fo(.)-85 3645 y(No)n(w)20 b(\(3\))h(and)e Fn(n)k(<)g(H)607 3657 y Fj(k)q Fk(+1)752 3645 y Fo(implies)d Fn(n)s Fl(\000)s Fn(H)1216 3657 y Fj(k)1280 3645 y Fn(<)j(H)1437 3657 y Fj(k)1498 3645 y Fo(and)d(so,)h(b)n(y)e(induction,)j Fn(n)s Fl(\000)s Fn(H)2454 3657 y Fj(k)2515 3645 y Fo(has)e(a)f(unique) i(decomp)r(ositon.)-85 3745 y(But)k(then)g(if)g Fn(n)g Fo(had)f(t)n(w)n(o)g(distinct)i(decomp)r(ositions,)e Fn(H)1690 3757 y Fj(k)1756 3745 y Fo(w)n(ould)g(app)r(ear)g(in)h(eac)n (h,)f(implying)h(that)g Fn(n)13 b Fl(\000)g Fn(H)3296 3757 y Fj(k)3360 3745 y Fo(also)-85 3845 y(had)27 b(t)n(w)n(o)g (distinct)h(decomp)r(ositions,)f(con)n(tradiction.)1799 b Fg(2)-85 3998 y Fo(One)27 b(simple)h(consequence)e(of)i(the)g (uniqueness)f(of)h(the)g(decomp)r(osition)f(is)g(that)1195 4180 y Fn(H)1264 4192 y Fj(k)1328 4180 y Fl(6)p Fo(=)c Fn(H)1485 4192 y Fj(j)1512 4200 y Fc(1)1567 4180 y Fo(+)18 b Fn(H)1719 4192 y Fj(j)1746 4200 y Fc(2)1802 4180 y Fo(+)g Fl(\001)c(\001)g(\001)k Fo(+)g Fn(H)2152 4192 y Fj(j)2179 4200 y Fb(p)3393 4180 y Fo(\(7\))-85 4363 y(for)27 b(all)g Fn(k)k Fo(and)c(sequences)g Fn(j)803 4375 y Fk(1)840 4363 y Fn(;)14 b(j)911 4375 y Fk(2)949 4363 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(j)1181 4375 y Fj(p)1247 4363 y Fo(where)27 b Fn(f)9 b Fo(\()p Fn(H)1638 4375 y Fj(j)1665 4383 y Fb(i)1696 4363 y Fo(\))23 b Fn(<)g(H)1908 4375 y Fj(j)1935 4383 y Fb(i)p Fc(+1)2065 4363 y Fo(for)k Fn(i)22 b Fo(=)h(1)p Fn(;)14 b Fo(2)p Fn(;)g(:::;)g(p)j Fl(\000)h Fo(1.)-85 4516 y(It)28 b(follo)n(ws)e(from)h(the)h(ab)r(o)n (v)n(e)f(Lemma)g(that)h(the)g(in)n(tegers)e Fn(n)i Fo(can)f(b)r(e)h (giv)n(en)e(unique)i(\\binary")e(represen)n(tations)-85 4616 y(b)n(y)h(represen)n(ting)e Fn(n)e Fo(=)g Fn(H)728 4628 y Fj(j)755 4636 y Fc(1)810 4616 y Fo(+)17 b Fn(H)961 4628 y Fj(j)988 4636 y Fc(2)1043 4616 y Fo(+)g Fl(\001)d(\001)g(\001)j Fo(+)h Fn(H)1391 4628 y Fj(j)1418 4636 y Fb(p)1485 4616 y Fo(b)n(y)26 b(the)i(0-1)e(string)h(with)g(a)g(1)g(in)g(p)r(osiitons)g Fn(j)2921 4628 y Fk(1)2959 4616 y Fn(;)14 b(j)3030 4628 y Fk(2)3067 4616 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(j)3299 4628 y Fj(p)3365 4616 y Fo(and)-85 4716 y(0)27 b(ev)n(erywhere)f(else.) 36 b(W)-7 b(e)28 b(call)f(this)h(the)g Fn(H)7 b Fo(-represen)n(tation) 26 b(of)h Fn(n)p Fo(.)37 b(This)27 b(then)i(leads)e(to)g(the)h(follo)n (wing)-85 4882 y Fp(Theorem)i(5.)41 b Fh(Supp)l(ose)30 b(that)g(the)g(p)l(osition)h(is)f Fo(\()p Fn(n;)14 b Fl(\003)p Fo(\))p Fh(.)38 b(Then,)-85 5101 y Fp(\(a\))k Fh(This)31 b(is)f(an)g(N-p)l(osition)g(if)h Fn(n)h(=)-51 b Fl(2)23 b(H)h Fo(=)f Fl(f)p Fn(H)1404 5113 y Fk(1)1440 5101 y Fn(;)14 b(H)1546 5113 y Fk(2)1584 5101 y Fn(;)g(:)g(:)g(:)27 b(;)14 b Fl(g)p Fh(.)-85 5267 y Fp(\(b\))42 b Fh(This)30 b(is)h(a)f(P-p)l(osition)h(if)f Fn(n)23 b Fl(2)h(H)q Fh(.)1686 5555 y Fo(6)p eop %%Page: 7 7 7 6 bop -85 223 a Fp(Pro)s(of)-85 323 y Fo(\(a\))31 b(The)f(winning)h (strategy)f(is)g(to)h(delete)g(a)f(n)n(um)n(b)r(er)h(of)g(c)n(hips)f (equal)g(to)h Fn(H)2386 335 y Fj(j)2413 343 y Fc(1)2481 323 y Fo(where)f Fn(j)2758 335 y Fk(1)2826 323 y Fo(is)h(the)g(index)g (of)g(the)-85 422 y(righ)n(tmost)26 b(1)i(in)f(the)h Fn(H)7 b Fo(-represen)n(tation)26 b(of)h Fn(n)p Fo(.)-85 576 y(All)j(w)n(e)g(ha)n(v)n(e)e(to)i(do)g(is)g(v)n(erify)f(that)h (this)g(strategy)f(is)g(p)r(ossible.)44 b(Note)30 b(that)g(if)g(A)h (deletes)f Fn(H)2919 588 y Fj(j)2946 596 y Fc(1)3013 576 y Fo(c)n(hips,)g(then)g(B)-85 675 y(cannot)h(resp)r(ond)g(b)n(y)h (deleting)g Fn(H)1014 687 y Fj(j)1041 695 y Fc(2)1109 675 y Fo(c)n(hips,)h(b)r(ecause)e Fn(H)1728 687 y Fj(j)1755 695 y Fc(2)1822 675 y Fn(>)f(f)9 b Fo(\()p Fn(H)2068 687 y Fj(j)2095 695 y Fc(1)2132 675 y Fo(\))32 b(and)g(so)f(it)h(is)g (only)f(A)h(that)g(can)g(reduce)-85 775 y(the)c(n)n(um)n(b)r(er)f(of)h (1's)f(in)g(the)h Fn(H)7 b Fo(-represen)n(tation)26 b(of)h Fn(n)p Fo(.)-85 928 y(The)f(thing)h(to)f(c)n(hec)n(k)g(is)g(that)h(if)g (A)g(starts)e(in)i(\()p Fn(n;)14 b Fl(\003)p Fo(\))26 b(then)h(A)g(can)f(alw)n(a)n(ys)f(delete)h Fn(H)2593 940 y Fj(j)2620 948 y Fc(1)2684 928 y Fo(c)n(hips)g(i.e.)37 b(the)27 b(p)r(ositions)-85 1028 y(\()p Fn(m;)14 b(x)p Fo(\))22 b(that)g(A)g(will)g(face)f(satisfy)h Fn(f)9 b Fo(\()p Fn(x)p Fo(\))23 b Fl(\025)g Fn(H)1324 1040 y Fj(k)1359 1048 y Fc(1)1418 1028 y Fo(where)e Fn(m)i Fo(=)f Fn(H)1904 1040 y Fj(k)1939 1048 y Fc(1)1983 1028 y Fo(+)7 b Fn(H)2124 1040 y Fj(k)2159 1048 y Fc(2)2201 1028 y Fo(+)g Fl(\001)14 b(\001)g(\001)6 b Fo(+)h Fn(H)2517 1040 y Fj(k)2552 1048 y Fb(q)2588 1028 y Fo(.)35 b(W)-7 b(e)22 b(do)f(this)h(b)n(y)g(induction)-85 1127 y(on)32 b(the)g(n)n(um)n(b)r(er)g(of)g(pla)n(ys)f(in)i(the)f(game)f(so)h(far.) 50 b(It)32 b(is)g(true)g(in)h(the)f(\014rst)g(mo)n(v)n(e)f(and)h(supp)r (ose)g(it)h(is)f(true)g(for)-85 1227 y(\()p Fn(m;)14 b(x)p Fo(\))28 b(and)g(A)g(remo)n(v)n(es)d Fn(H)801 1239 y Fj(k)836 1247 y Fc(1)901 1227 y Fo(and)i(B)h(remo)n(v)n(es)d Fn(y)31 b Fo(where)c Fn(y)e Fl(\024)e Fo(min)p Fl(f)p Fn(m)18 b Fl(\000)g Fn(H)2354 1239 y Fj(k)2389 1247 y Fc(1)2426 1227 y Fn(;)c(f)9 b Fo(\()p Fn(H)2614 1239 y Fj(k)2649 1247 y Fc(1)2686 1227 y Fo(\))p Fl(g)23 b Fn(<)f(H)2939 1239 y Fj(k)2974 1247 y Fc(2)3011 1227 y Fo(.)37 b(No)n(w)618 1410 y Fn(m)19 b Fl(\000)f Fn(H)862 1422 y Fj(k)897 1430 y Fc(1)952 1410 y Fl(\000)g Fn(y)86 b Fo(=)c Fn(H)1378 1422 y Fj(k)1413 1430 y Fc(2)1469 1410 y Fl(\000)18 b Fn(y)j Fo(+)d Fn(H)1766 1422 y Fj(k)1801 1430 y Fc(3)1856 1410 y Fo(+)g Fl(\001)c(\001)g(\001)k Fo(+)h Fn(H)2207 1422 y Fj(k)2242 1430 y Fb(q)1162 1534 y Fo(=)82 b Fn(H)1378 1546 y Fj(`)1406 1554 y Fc(1)1461 1534 y Fo(+)18 b Fn(H)1613 1546 y Fj(`)1641 1554 y Fc(2)1696 1534 y Fo(+)g Fl(\001)c(\001)g(\001)k Fo(+)g Fn(H)2046 1546 y Fj(`)2074 1554 y Fb(r)2130 1534 y Fo(+)g Fn(H)2282 1546 y Fj(k)2317 1554 y Fc(2)2373 1534 y Fo(+)g Fl(\001)c(\001)g(\001)k Fo(+)g Fn(H)2723 1546 y Fj(k)2758 1554 y Fb(q)-85 1717 y Fo(and)27 b(w)n(e)g(need)h(to)g(argue)e(that)i Fn(H)969 1729 y Fj(`)997 1737 y Fc(1)1056 1717 y Fl(\024)23 b Fn(f)9 b Fo(\()p Fn(y)s Fo(\).)37 b(But)27 b(if)i Fn(f)9 b Fo(\()p Fn(y)s Fo(\))22 b Fn(<)h(H)1940 1729 y Fj(`)1968 1737 y Fc(1)2032 1717 y Fo(then)28 b(w)n(e)f(ha)n(v)n(e)778 1899 y Fn(H)847 1911 y Fj(k)882 1919 y Fc(2)1002 1899 y Fo(=)82 b Fn(y)22 b Fo(+)c Fn(H)1364 1911 y Fj(`)1392 1919 y Fc(1)1446 1899 y Fo(+)g Fn(H)1598 1911 y Fj(`)1626 1919 y Fc(2)1681 1899 y Fo(+)g Fl(\001)c(\001)g(\001)19 b Fo(+)f Fn(H)2032 1911 y Fj(`)2060 1919 y Fb(r)1002 2024 y Fo(=)82 b Fn(H)1218 2036 y Fj(a)1254 2044 y Fc(1)1309 2024 y Fo(+)18 b Fl(\001)c(\001)g(\001)19 b Fo(+)f Fn(H)1660 2036 y Fj(a)1696 2044 y Fb(s)1750 2024 y Fo(+)g Fn(H)1902 2036 y Fj(`)1930 2044 y Fc(1)1985 2024 y Fo(+)g Fn(H)2137 2036 y Fj(`)2165 2044 y Fc(2)2220 2024 y Fo(+)g Fl(\001)c(\001)g(\001)k Fo(+)g Fn(H)2570 2036 y Fj(`)2598 2044 y Fb(r)-85 2207 y Fo(where)35 b Fn(f)9 b Fo(\()p Fn(H)314 2219 y Fj(a)350 2227 y Fb(s)386 2207 y Fo(\))38 b Fl(\024)f Fn(f)9 b Fo(\()p Fn(y)s Fo(\))38 b Fn(<)f(H)925 2219 y Fj(`)953 2227 y Fc(1)989 2207 y Fo(,)i(con)n(tradicting)d(\(7\).)63 b(Th)n(us)36 b(A)g(can)g(remo)n(v)n(e)f Fn(H)2598 2219 y Fj(`)2626 2227 y Fc(1)2698 2207 y Fo(in)i(the)f(next)h(round,)h(as) -85 2306 y(required.)-85 2459 y(\(b\))28 b(Assume)g(that)g Fn(n)23 b Fo(=)f Fn(H)770 2471 y Fj(k)811 2459 y Fo(.)37 b(After)28 b(A)g(remo)n(v)n(es)e Fn(x)i Fo(c)n(hips)f(w)n(e)g(ha)n(v)n (e)1121 2642 y Fn(H)1190 2654 y Fj(k)1249 2642 y Fl(\000)18 b Fn(x)24 b Fo(=)e Fn(H)1559 2654 y Fj(j)1586 2662 y Fc(1)1642 2642 y Fo(+)c Fn(H)1794 2654 y Fj(j)1821 2662 y Fc(2)1876 2642 y Fo(+)g Fl(\001)c(\001)g(\001)19 b Fo(+)f Fn(H)2227 2654 y Fj(j)2254 2662 y Fb(p)-85 2825 y Fo(c)n(hips)27 b(left.)-85 2978 y(All)f(w)n(e)f(ha)n(v)n(e)g(to)h (sho)n(w)f(is)g(that)h(B)g(can)f(no)n(w)g(remo)n(v)n(e)f Fn(H)1679 2990 y Fj(j)1706 2998 y Fc(1)1769 2978 y Fo(c)n(hips)i(i.e.) 36 b Fn(H)2189 2990 y Fj(j)2216 2998 y Fc(1)2276 2978 y Fl(\024)23 b Fn(f)9 b Fo(\()p Fn(x)p Fo(\).)37 b(But)26 b(if)g(this)g(is)g(not)g(the)g(case)-85 3078 y(then)d(w)n(e)f(argue)f (as)g(ab)r(o)n(v)n(e)g(that)i Fn(H)1007 3090 y Fj(k)1071 3078 y Fo(=)f Fn(H)1227 3090 y Fj(a)1263 3098 y Fc(1)1308 3078 y Fo(+)8 b Fl(\001)14 b(\001)g(\001)7 b Fo(+)h Fn(H)1627 3090 y Fj(a)1663 3098 y Fb(s)1707 3078 y Fo(+)g Fn(H)1849 3090 y Fj(j)1876 3098 y Fc(1)1920 3078 y Fo(+)g Fn(H)2062 3090 y Fj(j)2089 3098 y Fc(2)2134 3078 y Fo(+)g Fl(\001)14 b(\001)g(\001)7 b Fo(+)h Fn(H)2453 3090 y Fj(j)2480 3098 y Fb(p)2519 3078 y Fo(,)24 b(where)d Fn(x)j Fo(=)f Fn(H)3028 3090 y Fj(a)3064 3098 y Fc(1)3108 3078 y Fo(+)8 b Fl(\001)14 b(\001)g(\001)7 b Fo(+)h Fn(H)3427 3090 y Fj(a)3463 3098 y Fb(s)-85 3177 y Fo(and)27 b Fn(f)9 b Fo(\()p Fn(H)227 3189 y Fj(j)254 3197 y Fc(1)291 3177 y Fo(\))23 b Fl(\024)g Fn(f)9 b Fo(\()p Fn(x)p Fo(\))24 b Fn(<)e(H)775 3189 y Fj(j)802 3197 y Fc(1)839 3177 y Fo(,)28 b(con)n(tradicting)g(\(7\).) 1911 b Fg(2)1480 3397 y Fp(Geograph)m(y)-85 3617 y Fo(Start)27 b(with)h(a)f(c)n(hip)h(sitting)g(on)f(a)g(v)n(ertex)g Fn(v)k Fo(of)c(a)g(graph)g(or)g(digraph)f Fn(G)p Fo(.)-85 3770 y(A)j(mo)n(v)n(e)f(consists)g(of)h(mo)n(ving)f(the)i(c)n(hip)f(to) g(a)f(neigh)n(b)r(ouring)g(v)n(ertex.)40 b(In)29 b(edge)g(geograph)n(y) -7 b(,)27 b(mo)n(ving)h(the)h(c)n(hip)-85 3869 y(from)h Fn(x)i Fo(to)f Fn(y)i Fo(deletes)e(the)h(edge)e(\()p Fn(x;)14 b(y)s Fo(\).)48 b(In)31 b(v)n(ertex)f(geograph)n(y)-7 b(,)29 b(mo)n(ving)h(the)h(c)n(hip)g(from)g Fn(x)g Fo(to)g Fn(y)j Fo(deletes)d(the)-85 3969 y(v)n(ertex)26 b Fn(x)p Fo(.)-85 4122 y(The)h(problem)g(is)h(giv)n(en)f(a)g(p)r(osition)g(\()p Fn(G;)14 b(v)s Fo(\),)29 b(to)f(determine)f(whether)h(this)g(is)f(a)g (P)g(or)g(N)h(p)r(osition.)-85 4276 y Fp(Complexit)m(y)34 b Fo(Both)h(edge)g(and)h(v)n(ertex)e(geograph)n(y)f(are)i(Pspace-hard)e (on)j(digraphs.)60 b(Edge)34 b(geograph)n(y)f(is)-85 4375 y(Pspace-hard)19 b(on)i(an)h(undirected)g(graph.)33 b(Only)22 b(v)n(ertex)e(geograph)n(y)f(on)i(a)h(graph)e(is)i(p)r (olynomial)f(time)h(solv)-5 b(able.)-85 4703 y Fi(2)134 b(Undirected)46 b(V)-11 b(ertex)45 b(Geograph)l(y)g({)h(UV)l(G)-85 4939 y Fp(Theorem)30 b(6.)41 b Fo(\()p Fn(G;)14 b(v)s Fo(\))31 b Fh(is)f(an)g(N-p)l(osition)g(in)g(UV)n(G)f(i\013)h(every)h (maximum)e(matching)h(of)h Fn(G)f Fh(c)l(overs)g Fn(v)s Fh(.)-85 5158 y Fp(Pro)s(of)191 b Fo(\(i\))27 b(Supp)r(ose)g(that)g Fn(M)35 b Fo(is)27 b(a)f(maxim)n(um)g(matc)n(hing)h(of)f Fn(G)h Fo(whic)n(h)g(co)n(v)n(ers)d Fn(v)s Fo(.)37 b(Pla)n(y)n(er)25 b(1's)h(strategy)f(is)-85 5258 y(no)n(w:)36 b(Mo)n(v)n(e)26 b(along)h(M-edge)g(that)h(con)n(tains)e(curren)n(t)h(v)n(ertex.)1686 5555 y(7)p eop %%Page: 8 8 8 7 bop -85 223 a Fo(If)22 b(Pla)n(y)n(er)d(1)j(w)n(ere)e(to)i(lose,)g (then)h(there)e(w)n(ould)g(exist)h(a)f(sequence)h(of)f(edges)g Fn(e)2330 235 y Fk(1)2367 223 y Fn(;)14 b(f)2445 235 y Fk(1)2482 223 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(e)2719 235 y Fj(k)2760 223 y Fn(;)g(f)2838 235 y Fj(k)2900 223 y Fo(suc)n(h)21 b(that)h Fn(v)27 b Fl(2)c Fn(e)3439 235 y Fk(1)3476 223 y Fo(,)-85 323 y Fn(e)-46 335 y Fk(1)-9 323 y Fn(;)14 b(e)67 335 y Fk(2)103 323 y Fn(;)g(:)g(:)g(:)28 b(;)14 b(e)341 335 y Fj(k)404 323 y Fl(2)24 b Fn(M)9 b Fo(,)24 b Fn(f)661 335 y Fk(1)698 323 y Fn(;)14 b(f)776 335 y Fk(2)812 323 y Fn(;)g(:)g(:)g(:)28 b(;)14 b(f)1052 335 y Fj(k)1124 323 y Fn(=)-51 b Fl(2)24 b Fn(M)32 b Fo(and)23 b Fn(f)1505 335 y Fj(k)1568 323 y Fo(=)g(\()p Fn(x;)14 b(y)s Fo(\))24 b(where)f Fn(y)j Fo(is)d(the)h(curren)n(t)e(v)n (ertex)g(for)h(Pla)n(y)n(er)e(1)i(and)-85 422 y Fn(y)29 b Fo(is)d(not)g(co)n(v)n(ered)f(b)n(y)h Fn(M)9 b Fo(.)36 b(But)26 b(then)h(if)g Fn(A)c Fo(=)g Fl(f)p Fn(e)1453 434 y Fk(1)1489 422 y Fn(;)14 b(e)1565 434 y Fk(2)1602 422 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(e)1839 434 y Fj(k)1880 422 y Fl(g)26 b Fo(and)g Fn(B)h Fo(=)c Fl(f)p Fn(f)2369 434 y Fk(1)2405 422 y Fn(;)14 b(f)2483 434 y Fk(2)2520 422 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(f)2759 434 y Fj(k)2800 422 y Fl(g)26 b Fo(then)g(\()p Fn(M)f Fl(n)15 b Fn(A)p Fo(\))i Fl([)f Fn(B)-85 522 y Fo(is)27 b(a)g(maxim)n(um)h(matc)n(hing)f (\(same)g(size)g(as)g Fn(M)9 b Fo(\))28 b(whic)n(h)g(do)r(es)f(not)g (co)n(v)n(er)f Fn(v)s Fo(,)i(con)n(tradiction.)-85 675 y(\(ii\))g(Supp)r(ose)g(no)n(w)g(that)g(there)g(is)g(some)f(maxim)n(um) h(matc)n(hing)f Fn(M)37 b Fo(whic)n(h)28 b(do)r(es)g(not)g(co)n(v)n(er) e Fn(v)s Fo(.)38 b(Then)28 b(if)h(\()p Fn(v)s(;)14 b(w)r Fo(\))-85 775 y(is)37 b(Pla)n(y)n(er)f(1's)h(mo)n(v)n(e,)i Fn(w)i Fo(m)n(ust)d(b)r(e)g(co)n(v)n(ered)e(b)n(y)h Fn(M)9 b Fo(,)40 b(else)e Fn(M)46 b Fo(is)38 b(not)f(a)h(maxim)n(um)f(matc)n (hing.)67 b(Pla)n(y)n(er)36 b(2's)-85 874 y(strategy)d(is)i(no)n(w:)50 b(Mo)n(v)n(e)33 b(along)h(M-edge)g(that)h(con)n(tains)f(curren)n(t)f(v) n(ertex.)58 b(If)35 b(Pla)n(y)n(er)d(2)i(w)n(ere)g(to)h(lose)f(then)-85 974 y(there)29 b(exists)h Fn(e)400 986 y Fk(1)464 974 y Fo(=)c(\()p Fn(v)s(;)14 b(w)r Fo(\))p Fn(;)g(f)838 986 y Fk(1)876 974 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(e)1113 986 y Fj(k)1154 974 y Fn(;)g(f)1232 986 y Fj(k)1272 974 y Fn(;)g(e)1348 986 y Fj(k)q Fk(+1)1499 974 y Fo(=)27 b(\()p Fn(x;)14 b(y)s Fo(\))30 b(where)g Fn(y)i Fo(is)e(the)g(curren)n (t)f(v)n(ertex)g(for)g(Pla)n(y)n(er)f(2)h(and)-85 1074 y Fn(y)g Fo(is)e(not)g(co)n(v)n(ered)e(b)n(y)h Fn(M)9 b Fo(.)36 b(But)28 b(then)f(w)n(e)f(ha)n(v)n(e)g(de\014ned)h(an)g (augmen)n(ting)e(path)i(from)g Fn(v)j Fo(to)d Fn(y)i Fo(and)e(so)f Fn(M)35 b Fo(is)27 b(not)-85 1173 y(a)g(maxim)n(um)g (matc)n(hing,)g(con)n(tradiction.)2179 b Fg(2)-85 1327 y Fo(Note)23 b(that)h(w)n(e)f(can)g(determine)h(whether)f(or)g(not)g Fn(v)k Fo(is)d(co)n(v)n(ered)d(b)n(y)j(all)f(maxim)n(um)g(matc)n(hings) g(as)g(follo)n(ws:)33 b(Find)-85 1426 y(the)22 b(size)f Fn(\033)k Fo(of)c(the)h(maxim)n(um)g(matc)n(hing)f Fn(G)p Fo(.)35 b(This)21 b(can)h(b)r(e)g(done)f(in)h Fn(O)r Fo(\()p Fn(n)2228 1396 y Fk(3)2266 1426 y Fo(\))g(time)g(on)f(an)g Fn(n)p Fo(-v)n(ertex)f(graph.)34 b(Then)-85 1526 y(\014nd)27 b(the)h(size)e Fn(\033)429 1496 y Fm(0)480 1526 y Fo(of)h(a)g(maxim)n (um)g(matc)n(hing)f(in)h Fn(G)18 b Fl(\000)f Fn(v)s Fo(.)37 b(Then)27 b Fn(v)j Fo(is)d(co)n(v)n(ered)f(b)n(y)g(all)h(maxim)n(um)g (matc)n(hings)f(of)-85 1625 y Fn(G)i Fo(i\013)g Fn(\033)e Fl(6)p Fo(=)d Fn(\033)318 1595 y Fm(0)342 1625 y Fo(.)-85 1954 y Fi(3)134 b(Undirected)46 b(Edge)f(Geograph)l(y)h({)f(UEG)g(on)g (a)g(bipartite)h(graph)-85 2189 y Fo(An)28 b Fh(even)i(kernel)e Fo(of)g Fn(G)g Fo(is)f(a)g(non-empt)n(y)h(set)f Fn(S)h Fl(\022)23 b Fn(V)46 b Fo(suc)n(h)28 b(that)g(\(i\))g Fn(S)k Fo(is)c(an)f(indep)r(enden)n(t)i(set)f(and)f(\(ii\))h Fn(v)36 b(=)-51 b Fl(2)23 b Fn(S)-85 2289 y Fo(implies)28 b(that)f Fn(deg)498 2301 y Fj(S)546 2289 y Fo(\()p Fn(v)s Fo(\))h(is)g(ev)n(en,)f(\(p)r(ossibly)h(zero\).)36 b(\()p Fn(deg)1723 2301 y Fj(S)1770 2289 y Fo(\()p Fn(v)s Fo(\))29 b(is)e(the)h(n)n(um)n(b)r(er)g(of)f(neigh)n(b)r(ours)g(of)g Fn(v)k Fo(in)d Fn(S)5 b Fo(.\))-85 2455 y Fp(Lemma)29 b(3.)41 b Fh(If)30 b Fn(S)35 b Fh(is)30 b(an)g(even)f(kernel)i(and)f Fn(v)c Fl(2)e Fn(S)34 b Fh(then)c Fo(\()p Fn(G;)14 b(v)s Fo(\))30 b Fh(is)g(a)g(P-p)l(osition)h(in)f(UEG.)-85 2674 y Fp(Pro)s(of)191 b Fo(An)n(y)27 b(mo)n(v)n(e)e(at)i(a)g(v)n (ertex)f(in)h Fn(S)32 b Fo(tak)n(es)26 b(the)h(c)n(hip)g(outside)g Fn(S)32 b Fo(and)27 b(then)g(Pla)n(y)n(er)e(2)h(can)h(immediately)-85 2774 y(put)f(the)h(c)n(hip)e(bac)n(k)h(in)g Fn(S)5 b Fo(.)36 b(After)26 b(a)g(mo)n(v)n(e)e(from)i Fn(x)d Fl(2)h Fn(S)31 b Fo(to)25 b Fn(y)35 b(=)-51 b Fl(2)24 b Fn(S)5 b Fo(,)26 b Fn(deg)2178 2786 y Fj(S)2225 2774 y Fo(\()p Fn(y)s Fo(\))g(will)h(b)r(ecome)e(o)r(dd)h(and)g(so)f(there)h(is)-85 2874 y(an)f(edge)g(bac)n(k)g(to)g Fn(S)5 b Fo(.)36 b(making)25 b(this)h(mo)n(v)n(e,)f(mak)n(es)f Fn(deg)1677 2886 y Fj(S)1725 2874 y Fo(\()p Fn(y)s Fo(\))h(ev)n(en)g(again.)35 b(Ev)n(en)n(tually)-7 b(,)25 b(there)h(will)f(b)r(e)h(no)f Fn(S)j Fo(:)3457 2853 y(\026)3443 2874 y Fn(S)-85 2973 y Fo(edges)f(and)g(Pla)n(y)n(er)e(1)j(will)f(b)r(e)h(stuc)n(k)g(in)f Fn(S)5 b Fo(.)2150 b Fg(2)-85 3127 y Fo(W)-7 b(e)29 b(no)n(w)g(discuss) g(Bipartite)f(UEG)i(i.e.)41 b(w)n(e)29 b(assume)g(that)g Fn(G)h Fo(is)f(bipartite,)g Fn(G)h Fo(has)e(bipartion)h(consisting)f (of)h(a)-85 3226 y(cop)n(y)e(of)g([)p Fn(m)p Fo(])h(and)g(a)f(disjoin)n (t)h(cop)n(y)f(of)h([)p Fn(n)p Fo(])g(and)f(edges)g(set)h Fn(E)5 b Fo(.)38 b(No)n(w)27 b(consider)g(the)h Fn(m)19 b Fl(\002)f Fn(n)28 b Fo(0-1)e(matrix)h Fn(A)i Fo(with)-85 3326 y Fn(A)p Fo(\()p Fn(i;)14 b(j)5 b Fo(\))23 b(=)g(1)k(i\013)h(\()p Fn(i;)14 b(j)5 b Fo(\))23 b Fl(2)h Fn(E)5 b Fo(.)-85 3479 y(W)-7 b(e)33 b(can)e(pla)n(y)h(our)g(game)f(on)h(this)h(matrix:) 46 b(W)-7 b(e)33 b(are)e(either)h(p)r(ositioned)h(at)f(ro)n(w)f Fn(i)h Fo(or)g(w)n(e)g(are)f(p)r(ositioned)h(at)-85 3579 y(column)27 b Fn(j)5 b Fo(.)37 b(If)28 b(sa)n(y)-7 b(,)26 b(w)n(e)h(are)g(p)r(ositioned)g(at)g(ro)n(w)g Fn(i)p Fo(,)g(then)h(w)n(e)f(c)n(ho)r(ose)f(a)h Fn(j)33 b Fo(suc)n(h)27 b(that)g Fn(A)p Fo(\()p Fn(i;)14 b(j)5 b Fo(\))24 b(=)e(1)27 b(and)h(\(i\))g(mak)n(e)-85 3678 y Fn(A)p Fo(\()p Fn(i;)14 b(j)5 b Fo(\))23 b(=)g(0)h(and)g(\(ii\))i(mo)n(v)n(e)d(the)i(p)r (osition)g(to)f(column)h Fn(j)5 b Fo(.)36 b(An)25 b(analogous)d(mo)n(v) n(e)i(is)g(tak)n(en)g(when)h(w)n(e)f(p)r(ositioned)-85 3778 y(at)j(column)h Fn(j)5 b Fo(.)-85 3944 y Fp(Lemma)29 b(4.)41 b Fh(Supp)l(ose)34 b(the)f(curr)l(ent)g(p)l(osition)h(is)g(r)l (ow)g Fn(i)p Fh(.)49 b(This)35 b(is)f(a)f(P-p)l(osition)i(i\013)f(r)l (ow)g Fn(i)f Fh(is)g(in)h(the)f(sp)l(an)h(of)-85 4044 y(the)g(r)l(emaining)h(r)l(ows)f(\(is)g(the)g(sum)g(\(mo)l(d)g(2\))g (of)h(a)f(subset)g(of)h(the)f(other)g(r)l(ows\))g(or)h(r)l(ow)f Fn(i)g Fh(is)g(a)g(zer)l(o)h(r)l(ow.)51 b(A)-85 4143 y(similar)31 b(statement)e(c)l(an)g(b)l(e)h(made)h(if)g(the)e(p)l (osition)i(is)f(c)l(olumn)g Fn(j)5 b Fh(.)-85 4363 y Fp(Pro)s(of)191 b Fo(If)23 b(ro)n(w)g Fn(i)g Fo(is)g(a)g(zero)f(ro)n(w) g(then)i(v)n(ertex)f Fn(i)g Fo(is)g(isolated)g(and)g(this)h(is)f (clearly)f(a)h(P-p)r(osition.)35 b(Otherwise,)-85 4462 y(assume)27 b(the)h(p)r(osition)f(is)g(ro)n(w)g(1)g(and)g(there)h (exists)f Fn(I)j Fl(\022)23 b Fo([)p Fn(m)p Fo(])k(suc)n(h)h(that)g(1) 22 b Fl(2)i Fn(I)34 b Fo(and)919 4662 y Fn(r)956 4674 y Fk(1)1017 4662 y Fo(=)1163 4583 y Ff(X)1104 4765 y Fj(i)p Fm(2)p Fj(I)5 b Fm(nf)p Fk(1)p Fm(g)1355 4662 y Fn(r)1392 4674 y Fj(i)1420 4662 y Fo(\()p Fn(mod)29 b Fo(2\))e(or)1854 4583 y Ff(X)1863 4761 y Fj(i)p Fm(2)p Fj(I)1988 4662 y Fn(r)2025 4674 y Fj(i)2076 4662 y Fo(=)22 b(0\()p Fn(mod)28 b Fo(2\))898 b(\(8\))-85 4937 y(where)27 b Fn(r)192 4949 y Fj(i)248 4937 y Fo(denotes)g(ro)n(w)f Fn(i)p Fo(.)-85 5090 y Fn(I)37 b Fo(is)30 b(an)g(ev)n(en)g(k)n(ernel:) 41 b(If)31 b Fn(x)37 b(=)-51 b Fl(2)27 b Fn(I)38 b Fo(then)31 b(either)f(\(i\))h Fn(x)f Fo(corresp)r(onds)f(to)h(a)g(ro)n(w)f(and)h (there)g(are)f(no)h Fn(x;)14 b(I)37 b Fo(edges)30 b(or)-85 5189 y(\(ii\))e Fn(x)h Fo(corresp)r(onds)d(to)h(a)h(column)g(and)f (then)1398 5127 y Ff(P)1485 5214 y Fj(i)p Fm(2)p Fj(I)1606 5189 y Fn(A)p Fo(\()p Fn(i;)14 b(x)p Fo(\))24 b(=)f(0\()p Fn(mod)28 b Fo(2\))g(from)f(\(8\))h(and)g(then)g Fn(x)h Fo(has)e(an)h(ev)n(en)-85 5289 y(n)n(um)n(b)r(er)f(of)h(neigh)n(b)r (ours)e(in)i Fn(I)7 b Fo(.)1686 5555 y(8)p eop %%Page: 9 9 9 8 bop -85 223 a Fo(No)n(w)27 b(supp)r(ose)g(that)h(\(8\))g(do)r(es)f (not)h(hold)g(for)f(an)n(y)g Fn(I)7 b Fo(.)37 b(W)-7 b(e)28 b(sho)n(w)f(that)h(there)f(exists)h(a)f Fn(`)g Fo(suc)n(h)h(that)g Fn(A)p Fo(\(1)p Fn(;)14 b(`)p Fo(\))23 b(=)f(1)-85 323 y(and)28 b(putting)i Fn(A)p Fo(\(1)p Fn(;)14 b(`)p Fo(\))25 b(=)f(0)29 b(mak)n(es)f(column)g Fn(`)h Fo(dep)r(enden)n(t)g(on)g(the)g(remaining)f(columns.)40 b(Then)29 b(w)n(e)g(will)g(b)r(e)g(in)-85 422 y(a)e(P-p)r(osition,)g(b) n(y)g(the)h(\014rst)f(part.)-85 576 y(Let)e Fn(e)100 588 y Fk(1)163 576 y Fo(b)r(e)h(the)g Fn(m)p Fo(-v)n(ector)e(with)i(a)f (1)g(in)h(ro)n(w)f(1)g(and)g(a)h(0)f(ev)n(erywhere)e(else.)36 b(Let)26 b Fn(A)2525 545 y Fm(\003)2589 576 y Fo(b)r(e)g(obtained)g(b)n (y)f(adding)g Fn(e)3462 588 y Fk(1)-85 675 y Fo(to)30 b Fn(A)g Fo(as)g(an)g(\()p Fn(n)20 b Fo(+)g(1\)th)31 b(column.)44 b(No)n(w)30 b(the)h(ro)n(w-rank)c(of)k Fn(A)1885 645 y Fm(\003)1953 675 y Fo(is)f(the)h(same)f(as)f(the)i(ro)n(w-rank)d (of)i Fn(A)g Fo(\(here)g(w)n(e)-85 775 y(are)c(doing)g(all)h (arithmetic)g(mo)r(dulo)g(2\).)36 b(Supp)r(ose)27 b(not,)h(then)f(if)h Fn(r)2023 745 y Fm(\003)2021 796 y Fj(i)2089 775 y Fo(is)f(the)g Fn(i)p Fo(th)g(ro)n(w)f(of)h Fn(A)2763 745 y Fm(\003)2828 775 y Fo(then)h(there)f(exists)f(a)-85 874 y(set)h Fn(J)36 b Fo(suc)n(h)27 b(that)1069 895 y Ff(X)1073 1073 y Fj(i)p Fm(2)p Fj(J)1202 974 y Fn(r)1239 986 y Fj(i)1290 974 y Fo(=)c(0\()p Fn(mod)28 b Fo(2\))23 b Fl(6)p Fo(=)1820 895 y Ff(X)1825 1073 y Fj(i)p Fm(2)p Fj(J)1954 974 y Fn(r)1993 940 y Fm(\003)1991 995 y Fj(i)2032 974 y Fo(\()p Fn(mod)28 b Fo(2\))p Fn(:)-85 1204 y Fo(No)n(w)k(1)41 b Fn(=)-51 b Fl(2)32 b Fn(J)41 b Fo(b)r(ecause)33 b Fn(r)707 1216 y Fk(1)777 1204 y Fo(is)g(indep)r(enden)n(t)h(of)f(the)g (remaining)f(ro)n(ws)g(of)h Fn(A)p Fo(,)h(but)g(then)2752 1141 y Ff(P)2840 1229 y Fj(i)p Fm(2)p Fj(J)2968 1204 y Fn(r)3005 1216 y Fj(i)3065 1204 y Fo(=)e(0\()p Fn(mod)h Fo(2\))-85 1303 y(implies)197 1241 y Ff(P)284 1328 y Fj(i)p Fm(2)p Fj(J)413 1303 y Fn(r)452 1273 y Fm(\003)450 1325 y Fj(i)514 1303 y Fo(=)22 b(0\()p Fn(mod)28 b Fo(2\))g(since)f (the)h(last)f(column)h(has)f(all)g(zeros,)f(except)i(in)g(ro)n(w)e(1.) -85 1457 y(Th)n(us)h(rank)g Fn(A)379 1426 y Fm(\003)445 1457 y Fo(=)g(rank)g Fn(A)h Fo(and)f(so)g(there)g(exists)h Fn(K)g Fl(\022)23 b Fo([)p Fn(n)p Fo(])k(suc)n(h)h(that)862 1651 y Fn(e)901 1663 y Fk(1)961 1651 y Fo(=)1059 1572 y Ff(X)1049 1751 y Fj(k)q Fm(2)p Fj(K)1204 1651 y Fn(c)1240 1663 y Fj(k)1281 1651 y Fo(\()p Fn(mod)g Fo(2\))f(or)g Fn(e)1739 1663 y Fk(1)1794 1651 y Fo(+)1888 1572 y Ff(X)1877 1751 y Fj(k)q Fm(2)p Fj(K)2033 1651 y Fn(c)2069 1663 y Fj(k)2132 1651 y Fo(=)c(0\()p Fn(mod)28 b Fo(2\))841 b(\(9\))-85 1913 y(where)30 b Fn(c)194 1925 y Fj(k)265 1913 y Fo(denotes)g(column)h Fn(k)i Fo(of)d Fn(A)p Fo(.)46 b(Th)n(us)30 b(there)h(exists)f Fn(`)d Fl(2)h Fn(K)36 b Fo(suc)n(h)30 b(that)h Fn(A)p Fo(\(1)p Fn(;)14 b(`)p Fo(\))28 b(=)f(1.)45 b(No)n(w)30 b(let)h Fn(c)3273 1883 y Fm(0)3273 1935 y Fj(j)3336 1913 y Fo(=)c Fn(c)3464 1925 y Fj(j)-85 2013 y Fo(for)h Fn(j)i Fl(6)p Fo(=)25 b Fn(`)k Fo(and)g Fn(c)460 1983 y Fm(0)460 2036 y Fj(`)521 2013 y Fo(b)r(e)g(obtained)g(from)g Fn(c)1212 2025 y Fj(`)1272 2013 y Fo(b)n(y)g(putting)h Fn(A)p Fo(\(1)p Fn(;)14 b(`)p Fo(\))25 b(=)g(0)j(i.e.)42 b Fn(c)2295 1983 y Fm(0)2295 2036 y Fj(`)2352 2013 y Fo(=)25 b Fn(c)2478 2025 y Fj(`)2529 2013 y Fo(+)19 b Fn(e)2652 2025 y Fk(1)2689 2013 y Fo(.)41 b(But)29 b(then)h(\(9\))f(implies)-85 2112 y(that)95 2050 y Ff(P)182 2137 y Fj(k)q Fm(2)p Fj(K)342 2112 y Fn(c)378 2082 y Fm(0)378 2136 y Fj(k)441 2112 y Fo(=)23 b(0\()p Fn(mod)28 b Fo(2\))f(\()p Fn(K)i Fo(=)23 b Fl(f)p Fn(k)s Fl(g)j Fo(is)i(a)f(p)r(ossibilit)n(y)g(here\)..)1394 b Fg(2)1134 2344 y Fp(Tic)32 b(T)-8 b(ac)33 b(T)-8 b(o)s(e)32 b(and)g(extensions)-85 2576 y Fo(W)-7 b(e)33 b(consider)e(the)i(follo)n (wing)e(m)n(ulti-dimensional)h(v)n(ersion)f(of)i(Tic)f(T)-7 b(ac)32 b(T)-7 b(o)r(e)32 b(\(Nough)n(ts)g(and)h(Crosses)d(to)j(the)-85 2676 y(English\).)57 b(The)35 b Fh(b)l(o)l(ar)l(d)g Fo(consists)f(of)h ([)p Fn(n)p Fo(])1208 2646 y Fj(d)1246 2676 y Fo(.)58 b(A)35 b(p)r(oin)n(t)g(on)f(the)h(b)r(oard)f(is)g(therefore)g(a)g(v)n (ector)g(\()p Fn(x)3023 2688 y Fk(1)3061 2676 y Fn(;)14 b(x)3145 2688 y Fk(2)3182 2676 y Fn(;)g(:)g(:)g(:)28 b(;)14 b(x)3428 2688 y Fj(d)3467 2676 y Fo(\))-85 2775 y(where)27 b(1)22 b Fl(\024)h Fn(x)354 2787 y Fj(i)405 2775 y Fl(\024)g Fn(n)k Fo(for)g(1)c Fl(\024)g Fn(i)f Fl(\024)h Fn(d)p Fo(.)-85 2929 y(A)31 b Fh(line)h Fo(is)g(a)f(set)g(p)r (oin)n(ts)g(\()p Fn(x)797 2885 y Fk(\(1\))797 2952 y Fj(j)887 2929 y Fn(;)14 b(x)971 2885 y Fk(\(2\))971 2952 y Fj(j)1060 2929 y Fn(;)g(:)g(:)g(:)28 b(;)14 b(x)1306 2885 y Fk(\()p Fj(d)p Fk(\))1306 2952 y Fj(j)1397 2929 y Fo(\),)33 b Fn(j)h Fo(=)29 b(1)p Fn(;)14 b Fo(2)p Fn(;)g(:)g(:)g(:)26 b(;)14 b(n)31 b Fo(where)g(eac)n(h)f(sequence)h Fn(x)2875 2898 y Fk(\()p Fj(i)p Fk(\))2987 2929 y Fo(is)g(either)g(\(i\))h(of)-85 3028 y(the)24 b(form)f Fn(k)s(;)14 b(k)s(;)g(:)g(:)g(:)27 b(;)14 b(k)27 b Fo(for)c(some)h Fn(k)i Fl(2)d Fo([)p Fn(n)p Fo(])h(or)f(is)g(\(ii\))i(1)p Fn(;)14 b Fo(2)p Fn(;)g(:)g(:)g(:)26 b(;)14 b(n)24 b Fo(or)f(is)h(\(iii\))g Fn(n;)14 b(n)d Fl(\000)g Fo(1)p Fn(;)j(:)g(:)g(:)26 b(;)14 b Fo(1.)35 b(Finally)-7 b(,)25 b(w)n(e)f(cannot)-85 3128 y(ha)n(v)n(e)i(Case)h(\(i\))h(for)f(all)h Fn(i)p Fo(.)-85 3281 y(Th)n(us)g(in)i(the)f(\(familiar\))g(3)19 b Fl(\002)f Fo(3)29 b(case,)f(the)i(top)f(ro)n(w)e(is)i(de\014ned)g(b)n(y)g Fn(x)2147 3251 y Fk(\(1\))2262 3281 y Fo(=)c(1)p Fn(;)14 b Fo(1)p Fn(;)g Fo(1)27 b(and)i Fn(x)2789 3251 y Fk(\(2\))2904 3281 y Fo(=)c(1)p Fn(;)14 b Fo(2)p Fn(;)g Fo(3)27 b(and)i(the)-85 3381 y(diagonal)d(from)h(the)h(b)r(ottom)g(left)g(to)g(the)g(top)f (righ)n(t)g(is)h(de\014ned)g(b)n(y)f Fn(x)2149 3350 y Fk(\(1\))2262 3381 y Fo(=)22 b(3)p Fn(;)14 b Fo(2)p Fn(;)g Fo(1)26 b(and)i Fn(x)2784 3350 y Fk(\(2\))2896 3381 y Fo(=)23 b(1)p Fn(;)14 b Fo(2)p Fn(;)g Fo(3)-85 3562 y Fp(Lemma)29 b(5.)41 b Fh(The)31 b(numb)l(er)e(of)h(winning)g(lines)h (in)e(the)h Fo(\()p Fn(n;)14 b(d)p Fo(\))31 b Fh(game)f(is)2221 3522 y Fk(\()p Fj(n)p Fk(+2\))2398 3497 y Fb(d)2433 3522 y Fm(\000)p Fj(n)2526 3497 y Fb(d)p 2221 3543 340 4 v 2374 3591 a Fk(2)2571 3562 y Fh(.)-85 3778 y Fp(Pro)s(of)191 b Fo(In)29 b(the)h(de\014nition)g(of)g(a)f(line)g(there)h(are)e Fn(n)i Fo(c)n(hoices)e(for)h Fn(k)k Fo(in)c(\(i\))i(and)e(then)h (\(ii\),)h(\(iii\))f(mak)n(e)f(it)h(up)-85 3878 y(to)c Fn(n)16 b Fo(+)g(2.)36 b(There)26 b(are)f Fn(d)i Fo(indep)r(enden)n(t)g (c)n(hoices)f(for)g(eac)n(h)f Fn(i)i Fo(making)e(\()p Fn(n)17 b Fo(+)e(2\))2368 3848 y Fj(d)2407 3878 y Fo(.)36 b(No)n(w)26 b(delete)h Fn(n)2943 3848 y Fj(d)3008 3878 y Fo(c)n(hoices)f(where)-85 3977 y(only)g(Case)f(\(i\))i(is)f(used.)37 b(Then)26 b(divide)h(b)n(y)f(2)f(b)r(ecause)h(replacing)f(\(ii\))i(b)n (y)f(\(iii\))i(and)e(vice-v)n(ersa)e(whenev)n(er)h(Case)-85 4077 y(\(i\))j(do)r(es)f(not)h(hold)f(pro)r(duces)g(the)h(same)f(set)h (of)f(p)r(oin)n(ts)h(\(tra)n(v)n(ersing)d(the)j(line)g(in)g(the)g (other)f(direction\).)165 b Fg(2)-85 4230 y Fo(The)35 b(game)e(is)i(pla)n(y)n(ed)f(b)n(y)g(2)h(pla)n(y)n(ers.)56 b(The)35 b(Red)g(pla)n(y)n(er)e(\(X)j(pla)n(y)n(er\))d(go)r(es)h (\014rst)g(and)h(colours)e(a)h(p)r(oin)n(t)h(red.)-85 4330 y(Then)30 b(the)g(Blue)g(pla)n(y)n(er)e(\(0)i(pla)n(y)n(er\))e (colours)g(a)i(di\013eren)n(t)g(p)r(oin)n(t)g(blue)g(and)g(so)f(on.)43 b(A)30 b(pla)n(y)n(er)e(wins)i(if)h(there)e(is)-85 4430 y(a)g(line,)i(all)e(of)h(whose)f(p)r(oin)n(ts)h(are)f(that)h(pla)n(y)n (ers)e(colour.)42 b(If)31 b(neither)e(pla)n(y)n(er)g(wins)g(then)i(the) f(game)f(is)h(a)f(dra)n(w.)-85 4529 y(The)e(second)g(pla)n(y)n(er)f(do) r(es)i(not)f(ha)n(v)n(e)g(a)g(wnning)g(strategy:)-85 4692 y Fp(Lemma)i(6.)41 b Fh(Player)31 b(1)f(c)l(an)g(always)h(get)f (at)g(le)l(ast)g(a)g(dr)l(aw.)-85 4908 y Fp(Pro)s(of)191 b Fo(W)-7 b(e)22 b(pro)n(v)n(e)f(this)h(b)n(y)g(considering)f Fh(str)l(ate)l(gy)j(ste)l(aling)p Fo(.)36 b(Supp)r(ose)22 b(that)g(Pla)n(y)n(er)e(2)i(did)g(ha)n(v)n(e)f(a)h(winning)-85 5007 y(strategy)-7 b(.)33 b(Then)20 b(Pla)n(y)n(er)e(1)i(can)g(mak)n(e) f(an)h(arbitrary)f(\014rst)h(mo)n(v)n(e)f Fn(x)2007 5019 y Fk(1)2044 5007 y Fo(.)35 b(Pla)n(y)n(er)18 b(2)i(will)g(then)h(mo)n (v)n(e)e(with)i Fn(y)3175 5019 y Fk(1)3212 5007 y Fo(.)34 b(Pla)n(y)n(er)-85 5107 y(1)e(will)h(no)n(w)f(win)h(pla)n(ying)e(the)i (winning)g(strategy)e(for)h(Pla)n(y)n(er)f(2)h(against)f(a)h(\014rst)h (mo)n(v)n(e)e(of)i Fn(y)2950 5119 y Fk(1)2987 5107 y Fo(.)52 b(This)32 b(can)h(b)r(e)-85 5207 y(carried)25 b(out)h(un)n(til)h(the)g(strategy)e(calls)h(for)g(mo)n(v)n(e)g Fn(x)1565 5219 y Fk(1)1629 5207 y Fo(\(if)h(at)f(all\).)37 b(But)27 b(then)g(Pla)n(y)n(er)d(1)i(can)g(mak)n(e)g(an)g(arbitrary)-85 5306 y(mo)n(v)n(e)g(and)i(con)n(tin)n(ue,)f(since)g Fn(x)896 5318 y Fk(1)962 5306 y Fo(has)g(already)f(b)r(een)i(made.)1621 b Fg(2)1686 5555 y Fo(9)p eop %%Page: 10 10 10 9 bop -85 223 a Fa(3.1)112 b(P)m(airing)36 b(Strategy)1299 361 y Ff(2)1299 507 y(6)1299 557 y(6)1299 607 y(6)1299 657 y(6)1299 710 y(4)1396 428 y Fo(11)82 b(1)g(8)h(1)f(12)1416 527 y(6)104 b(2)82 b(2)h(9)f(10)1416 627 y(3)104 b(7)82 b Fl(\003)h Fo(9)103 b(3)1416 727 y(6)h(7)82 b(4)h(4)f(10)1396 826 y(12)g(5)g(8)h(5)f(11)2060 361 y Ff(3)2060 507 y(7)2060 557 y(7)2060 607 y(7)2060 657 y(7)2060 710 y(5)-85 965 y Fo(The)32 b(ab)r(o)n(v)n(e)f(arra)n(y)f(giv)n(es)h(a)h(strategy)f (for)h(Pla)n(y)n(er)e(2)h(the)i(5)21 b Fl(\002)g Fo(5)32 b(game)g(\()p Fn(d)f Fo(=)g(2)p Fn(;)14 b(n)30 b Fo(=)g(5\).)51 b(F)-7 b(or)32 b(eac)n(h)f(of)h(the)h(12)-85 1065 y(lines)d(there)g(is) f(an)h(asso)r(ciated)f(pair)g(of)h(p)r(ositions.)44 b(If)30 b(Pla)n(y)n(er)e(1)h(c)n(ho)r(oses)g(a)h(p)r(osition)f(with)i(a)e(n)n (um)n(b)r(er)h Fn(i)p Fo(,)h(then)-85 1164 y(Pla)n(y)n(er)25 b(2)i(resp)r(onds)g(b)n(y)g(c)n(ho)r(osing)f(the)i(other)f(cell)g(with) h(the)g(n)n(um)n(b)r(er)f Fn(i)p Fo(.)37 b(This)27 b(ensures)g(that)g (Pla)n(y)n(er)e(1)j(cannot)-85 1264 y(tak)n(e)d(line)i Fn(i)p Fo(.)36 b(If)27 b(Pla)n(y)n(er)d(1)i(c)n(ho)r(oses)f(the)h(*)g (then)h(Pla)n(y)n(er)d(2)i(can)g(c)n(ho)r(ose)f(an)n(y)h(cell)g(with)h (an)f(un)n(used)g(n)n(um)n(b)r(er.)36 b(So,)-85 1363 y(later)25 b(in)h(the)g(game)g(if)g(Pla)n(y)n(er)e(1)h(c)n(ho)r(oses)g (a)g(cell)h(with)g Fn(j)31 b Fo(and)26 b(Pla)n(y)n(er)e(2)h(already)g (has)g(the)h(other)g Fn(j)5 b Fo(,)26 b(then)g(Pla)n(y)n(er)-85 1463 y(1)g(can)g(c)n(ho)r(ose)g(an)g(arbitrary)e(cell.)37 b(Pla)n(y)n(er)24 b(2's)i(strategy)g(is)g(to)h(ensure)f(that)h(after)f (all)g(cells)g(ha)n(v)n(e)g(b)r(een)h(c)n(hosen,)-85 1563 y(he/she)h(will)h(ha)n(v)n(e)f(c)n(hosen)g(one)h(of)g(the)g(n)n (um)n(b)r(ered)g(cells)g(aso)r(ciatded)f(with)h(eac)n(h)f(line.)41 b(This)29 b(prev)n(en)n(ts)f(Pla)n(y)n(er)-85 1662 y(1)f(from)g(taking) g(a)g(whole)h(line.)37 b(This)27 b(is)h(called)f(a)g Fh(p)l(airing)i Fo(strategy)-7 b(.)-85 1816 y(W)g(e)28 b(no)n(w)e(generalise)g(the)i(game)e(to)i(the)f(follo)n(wing:)36 b(W)-7 b(e)28 b(ha)n(v)n(e)e(a)h(family)h Fl(F)i Fo(=)23 b Fn(A)2492 1828 y Fk(1)2530 1816 y Fn(;)14 b(A)2629 1828 y Fk(2)2666 1816 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(A)2926 1828 y Fj(N)3013 1816 y Fl(\022)22 b Fn(A)p Fo(.)37 b(A)28 b(mo)n(v)n(e)-85 1915 y(consists)e(of)g(one)h(pla)n(y)n(er,)e(taking)h (an)h(uncoloured)e(mem)n(b)r(er)i(of)g Fn(A)g Fo(and)f(giving)g(it)i (his)e(colour.)36 b(A)27 b(pla)n(y)n(er)e(wins)i(if)-85 2015 y(one)g(of)g(the)h(sets)g Fn(A)529 2027 y Fj(i)584 2015 y Fo(is)g(completely)f(coloured)g(with)h(his)f(colour.)-85 2168 y(A)41 b(pairing)e(strategy)g(is)i(a)f(collection)g(of)g(distinct) i(elemen)n(ts)e Fn(X)51 b Fo(=)44 b Fl(f)p Fn(x)2298 2180 y Fk(1)2336 2168 y Fn(;)14 b(x)2420 2180 y Fk(2)2457 2168 y Fn(;)g(:)g(:)g(:)28 b(;)14 b(x)2703 2180 y Fk(2)p Fj(N)6 b Fm(\000)p Fk(1)2884 2168 y Fn(;)14 b(x)2968 2180 y Fk(2)p Fj(N)3064 2168 y Fl(g)41 b Fo(suc)n(h)f(that)-85 2268 y Fn(x)-38 2280 y Fk(2)p Fj(i)p Fm(\000)p Fk(1)108 2268 y Fn(;)14 b(x)192 2280 y Fk(2)p Fj(i)287 2268 y Fl(2)34 b Fn(A)438 2280 y Fj(i)500 2268 y Fo(for)g Fn(i)f Fl(\025)h Fo(1.)56 b(This)34 b(is)g(called)f(a)h Fh(dr)l(aw)i(for)l (cing)h(p)l(airing)p Fo(.)58 b(Pla)n(y)n(er)32 b(2)i(resp)r(onds)f(to)h (Pla)n(y)n(er)e(1's)-85 2367 y(c)n(hoice)24 b(of)h Fn(x)298 2379 y Fk(2)p Fj(i)p Fk(+)p Fj(\016)442 2367 y Fn(;)14 b(\016)26 b Fo(=)d(0)p Fn(;)14 b Fo(1)24 b(b)n(y)g(c)n(ho)r(osing)g Fn(x)1269 2379 y Fk(2)p Fj(i)p Fk(+3)p Fm(\000)p Fj(\016)1498 2367 y Fo(.)36 b(If)26 b(Pla)n(y)n(er)c(1)j(do)r(es)g(not)g(c)n(ho)r (ose)e(from)i Fn(X)7 b Fo(,)25 b(then)g(Pla)n(y)n(er)e(2)h(can)-85 2467 y(c)n(ho)r(ose)h(an)n(y)h(uncoloured)g(elemen)n(t)h(of)g Fn(X)7 b Fo(.)36 b(In)27 b(this)g(w)n(a)n(y)-7 b(,)26 b(Pla)n(y)n(er)e(2)j(a)n(v)n(oids)e(defeat,)i(b)r(ecause)f(at)h(the)g (end)g(of)g(the)-85 2567 y(game)f(Pla)n(y)n(er)f(2)h(will)i(ha)n(v)n(e) e(coloured)f(at)i(least)g(one)g(of)g(eac)n(h)f(of)h(the)g(pairs)f Fn(x)2348 2579 y Fk(2)p Fj(i)p Fm(\000)p Fk(1)2495 2567 y Fn(;)14 b(x)2579 2579 y Fk(2)p Fj(i)2667 2567 y Fo(and)27 b(so)f(Pla)n(y)n(er)f(1)i(cannot)-85 2666 y(ha)n(v)n(e)f(completely)i (coloured)e Fn(A)918 2678 y Fj(i)973 2666 y Fo(for)i Fn(i)22 b Fo(=)h(1)p Fn(;)14 b Fo(2)p Fn(;)g(:)g(:)g(:)26 b(;)14 b(N)9 b Fo(.)-85 2817 y Fp(Theorem)30 b(7.)41 b Fh(If)1221 2905 y Ff(\014)1221 2955 y(\014)1221 3005 y(\014)1221 3055 y(\014)1221 3104 y(\014)1272 2972 y([)1249 3150 y Fj(A)p Fm(2G)1401 3050 y Fn(A)1463 2905 y Ff(\014)1463 2955 y(\014)1463 3005 y(\014)1463 3055 y(\014)1463 3104 y(\014)1514 3050 y Fl(\025)23 b Fo(2)p Fl(jG)5 b(j)169 b(8G)28 b(\022)22 b(F)1167 b Fo(\(10\))-85 3293 y Fh(then)29 b(ther)l(e)h(is)g(a)g(dr)l(aw)h(for)l(cing)g(p)l(airing.)-85 3498 y Fp(Pro)s(of)191 b Fo(W)-7 b(e)26 b(de\014ne)g(a)g(bipartite)g (graph)f(\000.)36 b Fn(A)27 b Fo(will)f(b)r(e)h(one)e(side)h(of)g(the)h (bipartition)e(and)h Fn(B)i Fo(=)22 b Fl(f)p Fn(b)3205 3510 y Fk(1)3242 3498 y Fn(;)14 b(b)3315 3510 y Fk(2)3351 3498 y Fn(;)g(:)g(:)g(:)-85 3597 y(;)g(b)-12 3609 y Fk(2)p Fj(N)83 3597 y Fl(g)p Fo(.)65 b(Here)36 b Fn(b)454 3609 y Fk(2)p Fj(i)p Fm(\000)p Fk(1)637 3597 y Fo(and)h Fn(b)844 3609 y Fk(2)p Fj(i)941 3597 y Fo(b)r(oth)g(represen)n(t)f Fn(A)1576 3609 y Fj(i)1641 3597 y Fo(in)h(the)g(sense)g(that)g(if)h Fn(a)g Fl(2)h Fn(A)2635 3609 y Fj(i)2700 3597 y Fo(then)e(there)g(is)g (an)g(edge)-85 3697 y(\()p Fn(a;)14 b(b)64 3709 y Fk(2)p Fj(i)p Fm(\000)p Fk(1)209 3697 y Fo(\))24 b(and)g(an)f(edge)h(\()p Fn(a;)14 b(b)869 3709 y Fk(2)p Fj(i)929 3697 y Fo(\).)36 b(A)24 b(dra)n(w)f(forcing)g(pairing)g(corresp)r(onds)f(to)h(a)h (complete)f(matc)n(hing)h(of)f Fn(B)28 b Fo(in)n(to)-85 3797 y Fn(A)g Fo(and)f(the)h(condition)f(\(10\))h(implies)g(that)f (Hall's)h(condition)f(is)h(satis\014ed.)1130 b Fg(2)-85 3947 y Fp(Corollary)31 b(8.)41 b Fh(If)29 b Fl(j)p Fn(A)626 3959 y Fj(i)654 3947 y Fl(j)23 b(\025)g Fn(n)29 b Fh(for)g Fn(i)23 b Fo(=)f(1)p Fn(;)14 b Fo(2)p Fn(;)g(:)g(:)g(:)27 b(;)14 b(n)28 b Fh(and)h(every)h Fn(x)23 b Fl(2)h Fn(A)29 b Fh(is)g(c)l(ontaine)l(d)g(in)g(at)f(most)h Fn(n=)p Fo(2)e Fh(sets)i(of)g Fl(F)-85 4047 y Fh(then)g(ther)l(e)h(is)g(a)g(dr) l(aw)h(for)l(cing)g(p)l(airing.)-85 4251 y Fp(Pro)s(of)191 b Fo(The)29 b(degree)f(of)h Fn(a)d Fl(2)g Fn(A)k Fo(is)f(at)g(most)g (2\()p Fn(n=)p Fo(2\))f(in)i(\000)f(and)g(the)h(degree)e(of)h(eac)n(h)g Fn(b)c Fl(2)h Fn(B)34 b Fo(is)29 b(at)g(least)g Fn(n)p Fo(.)-85 4351 y(This)e(implies)h(\(via)f(Hall's)h(condition\))g(that)f (there)h(is)f(a)g(complete)h(matc)n(hing)f(of)h Fn(B)j Fo(in)n(to)d Fn(A)p Fo(.)552 b Fg(2)-85 4504 y Fo(Consider)29 b(Tic)h(tac)f(T)-7 b(o)r(e)30 b(when)g(case)g Fn(d)d Fo(=)f(2.)44 b(If)31 b Fn(n)e Fo(is)h(ev)n(en)g(then)g(ev)n(ery)f(arra) n(y)f(elemen)n(t)i(is)g(in)g(at)g(most)g(3)f(lines)-85 4604 y(\(one)g(ro)n(w,)g(one)h(column)f(and)h(at)g(most)f(one)g (diagonal\))g(and)g(if)i Fn(n)e Fo(is)h(o)r(dd)g(then)g(ev)n(ery)e (arra)n(y)g(elemen)n(t)i(is)f(in)h(at)-85 4703 y(most)24 b(4)h(lines)f(\(one)h(ro)n(w,)f(one)g(column)h(and)f(at)h(most)g(t)n(w) n(o)e(diagonals\).)35 b(Th)n(us)24 b(there)h(is)f(a)h(dra)n(w)e (forcing)h(pairing)-85 4803 y(if)h Fn(n)e Fl(\025)f Fo(6,)j Fn(n)f Fo(ev)n(en)h(and)f(if)h Fn(n)e Fl(\025)f Fo(9,)j Fn(n)g Fo(o)r(dd.)36 b(\(The)24 b(cases)g Fn(n)f Fo(=)f(4)p Fn(;)14 b Fo(7)24 b(ha)n(v)n(e)f(b)r(een)i(settled)g(as)f(dra)n(ws.)34 b Fn(n)23 b Fo(=)g(7)h(required)-85 4903 y(the)k(use)f(of)h(a)f (computer)g(to)h(examine)f(all)g(p)r(ossible)g(strategies.)-85 5056 y(In)h(general)e(w)n(e)h(ha)n(v)n(e)-85 5207 y Fp(Lemma)i(7.)41 b Fh(If)30 b Fn(n)23 b Fl(\025)g Fo(3)659 5176 y Fj(d)715 5207 y Fl(\000)18 b Fo(1)29 b Fh(and)i Fn(n)e Fh(is)h(o)l(dd)h(or)f(if) h Fn(n)22 b Fl(\025)h Fo(2)1742 5176 y Fj(d)1799 5207 y Fl(\000)18 b Fo(1)29 b Fh(and)h Fn(n)f Fh(is)h(even,)h(then)e(ther)l (e)h(is)g(a)g(dr)l(aw)h(for)l(cing)-85 5306 y(p)l(airing)g(of)f Fo(\()p Fn(n;)14 b(d)p Fo(\))31 b Fh(Tic)f(tac)g(T)-6 b(o)l(e.)1665 5555 y Fo(10)p eop %%Page: 11 11 11 10 bop -85 223 a Fp(Pro)s(of)191 b Fo(W)-7 b(e)26 b(only)g(ha)n(v)n(e)f(to)i(estimate)f(the)h(n)n(um)n(b)r(er)f(of)g (lines)g(through)g(a)g(\014xed)g(p)r(oin)n(t)h Fp(c)d Fo(=)e(\()p Fn(c)3023 235 y Fk(1)3061 223 y Fn(;)14 b(c)3134 235 y Fk(2)3171 223 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(c)3405 235 y Fj(d)3444 223 y Fo(\).)-85 323 y(If)28 b Fn(n)g Fo(is)g(o)r(dd)h(then)f(to)g(c)n(ho)r(ose)f(a)h(line)h Fn(L)e Fo(through)h Fp(c)g Fo(w)n(e)g(sp)r(ecify)-7 b(,)29 b(for)f(eac)n(h)f(index)h Fn(i)g Fo(whether)g Fn(L)g Fo(is)g(\(i\))h(constan)n(t)-85 422 y(on)g Fn(i)p Fo(,)h(\(ii\))g (increasing)e(on)i Fn(i)f Fo(or)g(\(iii\))h(decreasing)e(on)h Fn(i)p Fo(.)43 b(This)29 b(giv)n(es)g(3)2142 392 y Fj(d)2209 422 y Fo(c)n(hoices.)42 b(Subtract)30 b(1)f(to)g(a)n(v)n(oid)f(the)i (all)-85 522 y(constan)n(t)d(case)f(and)i(divide)g(b)n(y)f(2)g(b)r (ecause)g(eac)n(h)g(line)h(gets)f(coun)n(ted)g(t)n(wice)h(this)g(w)n(a) n(y)-7 b(.)-85 675 y(When)42 b Fn(n)f Fo(is)g(ev)n(en,)j(w)n(e)d (observ)n(e)f(that)h(once)g(w)n(e)g(ha)n(v)n(e)f(c)n(hosen)h(in)g(whic) n(h)g(p)r(ositions)g Fn(L)g Fo(is)g(constan)n(t,)j Fn(L)d Fo(is)-85 775 y(determined.)46 b(Supp)r(ose)30 b Fn(c)754 787 y Fk(1)819 775 y Fo(=)e Fn(x)j Fo(and)f(1)h(is)f(not)h(a)f(\014xed) g(p)r(osition.)46 b(Then)31 b(ev)n(ery)e(other)h(non-\014xed)g(p)r (osition)g(is)-85 874 y Fn(x)h Fo(or)f Fn(n)20 b Fl(\000)g Fn(x)h Fo(+)f(1.)46 b(Asuning)30 b(w.l.o.g.)46 b(that)31 b Fn(x)d Fl(\024)g Fn(n=)p Fo(2)i(w)n(e)g(see)g(that)h Fn(x)e(<)f(n)20 b Fl(\000)g Fn(x)29 b Fo(=)f(1)i(and)g(the)h(p)r (ositions)g(with)-85 974 y Fn(x)g Fo(increase)e(together)h(at)g(the)h (same)f(time)i(as)d(the)i(p)r(ositions)g(with)g Fn(n)20 b Fl(\000)g Fn(x)h Fo(+)f(1)30 b(decrease)f(together.)45 b(Th)n(us)31 b(the)-85 1074 y(n)n(um)n(b)r(er)c(of)h(lines)f(through)g Fp(c)h Fo(in)g(this)g(case)f(is)g(b)r(ounded)h(b)n(y)1857 1011 y Ff(P)1945 1032 y Fj(d)p Fm(\000)p Fk(1)1945 1099 y Fj(i)p Fk(=0)2083 1006 y Ff(\000)2121 1037 y Fj(d)2126 1102 y(i)2155 1006 y Ff(\001)2216 1074 y Fo(=)23 b(2)2346 1044 y Fj(d)2403 1074 y Fl(\000)18 b Fo(1.)886 b Fg(2)-85 1360 y Fa(3.2)112 b(Quasi-probabilistic)35 b(metho)s(d)-85 1567 y Fo(W)-7 b(e)28 b(no)n(w)f(pro)n(v)n(e)f(a)h(theorem)g(of)g(Erd}) -42 b(os)27 b(and)g(Selfridge.)-85 1733 y Fp(Theorem)j(9.)41 b Fh(If)36 b Fl(j)p Fn(A)614 1745 y Fj(i)642 1733 y Fl(j)e(\025)f Fn(n)j Fh(for)g Fn(i)e Fl(2)g Fo([)p Fn(N)9 b Fo(])36 b Fh(and)g Fn(N)42 b(<)34 b Fo(2)1748 1702 y Fj(n)p Fm(\000)p Fk(1)1877 1733 y Fh(,)k(then)e(Player)h(2)f(c)l(an)f(get)h(a)g(dr)l(aw) h(in)e(the)h(game)-85 1832 y(de\014ne)l(d)30 b(by)g Fl(F)8 b Fh(.)-85 2052 y Fp(Pro)s(of)191 b Fo(A)n(t)38 b(an)n(y)g(p)r(oin)n(t) h(in)g(the)f(game,)j(let)e Fn(C)1569 2064 y Fj(j)1643 2052 y Fo(denote)f(the)h(set)f(of)h(elemen)n(ts)f(in)h Fn(A)g Fo(whic)n(h)f(ha)n(v)n(e)g(b)r(een)-85 2152 y(coloured)26 b(with)i(Pla)n(y)n(er)e Fn(j)5 b Fo('s)27 b(colour,)f Fn(j)i Fo(=)23 b(1)p Fn(;)14 b Fo(2)27 b(and)g Fn(U)32 b Fo(=)22 b Fn(A)d Fl(n)f Fn(C)1923 2164 y Fk(1)1979 2152 y Fl([)h Fn(C)2112 2164 y Fk(2)2149 2152 y Fo(.)37 b(Let)1284 2351 y(\010)23 b(=)1559 2272 y Ff(X)1455 2454 y Fj(i)p Fk(:)p Fj(A)1547 2462 y Fb(i)1573 2454 y Fm(\\)p Fj(C)1666 2462 y Fc(2)1698 2454 y Fk(=)p Fm(;)1797 2351 y Fo(2)1839 2316 y Fm(\000j)p Fj(A)1961 2324 y Fb(i)1986 2316 y Fm(\\)p Fj(U)6 b Fm(j)2106 2351 y Fn(:)-85 2619 y Fo(Supp)r(ose)35 b(that)g(the)g(pla)n(y)n(ers)e(c)n(hoices)h(are)g Fn(x)1352 2631 y Fk(1)1389 2619 y Fn(;)14 b(y)1467 2631 y Fk(1)1504 2619 y Fn(;)g(x)1588 2631 y Fk(2)1626 2619 y Fn(;)g(y)1704 2631 y Fk(2)1741 2619 y Fn(;)g(:)g(:)g(:)27 b(;)p Fo(.)59 b(Then)35 b(w)n(e)f(observ)n(e)f(that)i(immediately)g (after)-85 2719 y(Pla)n(y)n(er)25 b(1's)i(\014rst)g(mo)n(v)n(e,)g(\010) c Fn(<)g(N)9 b Fo(2)995 2689 y Fm(\000)p Fk(\()p Fj(n)p Fm(\000)p Fk(1\))1251 2719 y Fn(<)23 b Fo(1.)-85 2872 y(W)-7 b(e)36 b(will)g(sho)n(w)e(that)i(Pla)n(y)n(er)e(2)h(can)g(k)n (eep)g(\010)i Fn(<)f Fo(1)f(through)g(out.)61 b(Then)35 b(at)h(the)g(end,)i(when)e Fn(U)45 b Fo(=)36 b Fl(;)p Fo(,)h(\010)f(=)-85 2910 y Ff(P)2 2997 y Fj(i)p Fk(:)p Fj(A)94 3005 y Fb(i)121 2997 y Fm(\\)p Fj(C)214 3005 y Fc(2)246 2997 y Fk(=)p Fm(;)349 2972 y Fo(1)22 b Fn(<)h Fo(1)k(implies)h(that)g Fn(A)1094 2984 y Fj(i)1140 2972 y Fl(\\)19 b Fn(C)1273 2984 y Fk(2)1333 2972 y Fl(6)p Fo(=)k Fl(;)k Fo(for)g(all)h Fn(i)22 b Fl(2)i Fo([)p Fn(N)9 b Fo(].)-85 3125 y(So,)30 b(no)n(w)f(let)g(\010)412 3137 y Fj(j)477 3125 y Fo(b)r(e)h(the)g(v)-5 b(alue)29 b(of)h(\010)g(after)f(the)h(c)n(hoice)f(of)g Fn(x)1875 3137 y Fk(1)1913 3125 y Fn(;)14 b(y)1991 3137 y Fk(1)2028 3125 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(x)2273 3137 y Fj(j)2308 3125 y Fo(.)43 b(then)30 b(if)h Fn(U;)14 b(C)2797 3137 y Fk(1)2834 3125 y Fn(;)g(C)2930 3137 y Fk(2)2997 3125 y Fo(are)28 b(de\014ned)i(at)-85 3225 y(precisely)c(this)i(time,)594 3419 y(\010)654 3431 y Fj(j)s Fk(+1)791 3419 y Fl(\000)18 b Fo(\010)934 3431 y Fj(j)1052 3419 y Fo(=)83 b Fl(\000)1382 3341 y Ff(X)1279 3523 y Fj(i)p Fk(:)p Fj(A)1371 3531 y Fb(i)1397 3523 y Fm(\\)p Fj(C)1490 3531 y Fc(2)1521 3523 y Fk(=)p Fm(;)1349 3579 y Fj(y)1383 3587 y Fb(j)1414 3579 y Fm(2)p Fj(A)1509 3587 y Fb(i)1620 3419 y Fo(2)1662 3385 y Fm(\000j)p Fj(A)1784 3393 y Fb(i)1809 3385 y Fm(\\)p Fj(U)6 b Fm(j)1948 3419 y Fo(+)2204 3341 y Ff(X)2100 3523 y Fj(i)p Fk(:)p Fj(A)2192 3531 y Fb(i)2218 3523 y Fm(\\)p Fj(C)2311 3531 y Fc(2)2343 3523 y Fk(=)p Fm(;)2031 3583 y Fj(y)2065 3591 y Fb(j)2103 3583 y Fj(=)-41 b Fm(2)o Fj(A)2190 3591 y Fb(i)2217 3583 y Fj(;x)2275 3591 y Fb(j)r Fc(+1)2376 3583 y Fm(2)p Fj(A)2471 3591 y Fb(i)2511 3419 y Fo(2)2553 3385 y Fm(\000j)p Fj(A)2675 3393 y Fb(i)2700 3385 y Fm(\\)p Fj(U)6 b Fm(j)1052 3728 y Fl(\024)83 b(\000)1382 3649 y Ff(X)1279 3831 y Fj(i)p Fk(:)p Fj(A)1371 3839 y Fb(i)1397 3831 y Fm(\\)p Fj(C)1490 3839 y Fc(2)1521 3831 y Fk(=)p Fm(;)1349 3888 y Fj(y)1383 3896 y Fb(j)1414 3888 y Fm(2)p Fj(A)1509 3896 y Fb(i)1620 3728 y Fo(2)1662 3694 y Fm(\000j)p Fj(A)1784 3702 y Fb(i)1809 3694 y Fm(\\)p Fj(U)6 b Fm(j)1948 3728 y Fo(+)2135 3649 y Ff(X)2031 3831 y Fj(i)p Fk(:)p Fj(A)2123 3839 y Fb(i)2150 3831 y Fm(\\)p Fj(C)2243 3839 y Fc(2)2274 3831 y Fk(=)p Fm(;)2065 3888 y Fj(x)2103 3896 y Fb(j)r Fc(+1)2204 3888 y Fm(2)p Fj(A)2299 3896 y Fb(i)2373 3728 y Fo(2)2415 3694 y Fm(\000j)p Fj(A)2537 3702 y Fb(i)2562 3694 y Fm(\\)p Fj(U)g Fm(j)-85 4091 y Fo(W)-7 b(e)28 b(deduce)f(that)h(\010)574 4103 y Fj(j)s Fk(+1)712 4091 y Fl(\000)18 b Fo(\010)855 4103 y Fj(j)913 4091 y Fl(\024)k Fo(0)28 b(if)g(Pla)n(y)n(er)d(2)i(c)n(ho)r (oses)f Fn(y)1809 4103 y Fj(j)1872 4091 y Fo(to)h(maximise)g(o)n(v)n (er)f Fn(y)s Fo(,)2717 4012 y Ff(X)2613 4194 y Fj(i)p Fk(:)p Fj(A)2705 4202 y Fb(i)2731 4194 y Fm(\\)p Fj(C)2824 4202 y Fc(2)2856 4194 y Fk(=)p Fm(;)2698 4250 y Fj(y)r Fm(2)p Fj(A)2829 4258 y Fb(i)2955 4091 y Fo(2)2997 4056 y Fm(\000j)p Fj(A)3119 4064 y Fb(i)3144 4056 y Fm(\\)p Fj(U)6 b Fm(j)3264 4091 y Fo(.)-85 4389 y(In)28 b(this)f(w)n(a)n(y)-7 b(,)27 b(Pla)n(y)n(er)e(2)i(k)n(eeps)g(\010)c Fn(<)g Fo(1)k(and)h(obtains)f(a)g(dra)n(w.)1560 b Fg(2)-85 4543 y Fo(In)28 b(the)f(case)g(of)h(\()p Fn(n;)14 b(d)p Fo(\))28 b(Tic)g(T)-7 b(ac)27 b(T)-7 b(o)r(e,)27 b(w)n(e)g(see)h(that)g(Pla)n(y) n(er)d(2)i(can)g(force)g(a)g(dra)n(w)g(if)h(\(see)f(Lemma)h(5\))1323 4725 y(\()p Fn(n)18 b Fo(+)g(2\))1580 4695 y Fj(d)1637 4725 y Fl(\000)g Fn(n)1770 4695 y Fj(d)p 1323 4762 487 4 v 1545 4838 a Fo(2)1842 4781 y Fn(<)k Fo(2)1971 4747 y Fj(n)p Fm(\000)p Fk(1)-85 4987 y Fo(whic)n(h)27 b(is)h(implied,)g (for)f Fn(n)h Fo(large,)e(b)n(y)1377 5087 y Fn(n)d Fl(\025)f Fo(\(1)c(+)g Fn(\017)p Fo(\))p Fn(d)c Fo(log)1943 5107 y Fk(2)1994 5087 y Fn(d)-85 5236 y Fo(where)27 b Fn(\017)c(>)f Fo(0)27 b(is)h(a)f(small)g(p)r(ositiv)n(e)g(constsn)n(t.)1665 5555 y(11)p eop %%Page: 12 12 12 11 bop -85 223 a Fp(Shannon)32 b(Switc)m(hing)g(Game)26 b Fo(Start)h(with)h(a)g(connected)f(m)n(ulti-graph)g Fn(G)c Fo(=)g(\()p Fn(V)5 b(;)14 b(E)5 b Fo(\).)-85 323 y(Tw)n(o)27 b(pla)n(y)n(ers:)35 b(Pla)n(y)n(er)25 b(A)j(go)r(es)f (\014rst)g(and)h(deletes)f(edges)g(and)h(pla)n(y)n(er)e(B)h (forti\014es)g(edges)g(making)g(them)h(in)n(vul-)-85 422 y(nerable)f(to)g(deletion)h(b)n(y)f(B.)h(Pla)n(y)n(er)d(B)i(wins)h (i\013)g(the)g(forti\014ed)g(edges)e(con)n(tain)h(a)h(spanning)f(tree)g (of)g Fn(G)p Fo(.)-85 573 y Fp(Theorem)j(10.)41 b Fh(Player)31 b(B)f(wins)g(i\013)g Fn(G)g Fh(c)l(ontains)g(two)g(e)l(dge)g(disjoint)h (sp)l(anning)f(tr)l(e)l(es.)-85 777 y Fp(Pro)s(of)191 b Fo(\(a\))32 b(Here)g(w)n(e)g(assume)g(that)h Fn(G)g Fo(has)e(t)n(w)n(o)h(edge)g(disjoin)n(t)h(spanning)e(trees)h Fn(T)2796 789 y Fk(1)2833 777 y Fn(;)14 b(T)2919 789 y Fk(2)2988 777 y Fo(W)-7 b(e)33 b(pro)n(v)n(e)e(this)-85 877 y(b)n(y)i(induction)h(on)g Fl(j)p Fn(V)19 b Fl(j)p Fo(.)56 b(If)34 b Fl(j)p Fn(V)19 b Fl(j)33 b Fo(=)g(2)h(then)g Fn(G)g Fo(m)n(ust)g(con)n(tain)f(at)h(least)f(t)n(w)n(o)g(parallel)g (edges)g(joining)h(the)g(t)n(w)n(o)-85 976 y(v)n(ertices)29 b(and)g(so)g(B)h(can)g(win.)44 b(Supp)r(ose)30 b(next)g(that)g Fl(j)p Fn(V)19 b Fl(j)27 b Fn(>)f Fo(2.)43 b(Supp)r(ose)30 b(that)g(A)h(deletes)e(an)h(edge)f Fn(e)e Fo(=)f(\()p Fn(x;)14 b(y)s Fo(\))-85 1076 y(of)26 b Fn(T)57 1088 y Fk(2)120 1076 y Fo(red.)37 b(This)26 b(breaks)f Fn(T)793 1088 y Fk(2)857 1076 y Fo(in)n(to)h(t)n(w)n(o)f(sub-trees)h Fn(T)1591 1046 y Fm(0)1579 1097 y Fk(2)1616 1076 y Fn(;)14 b(T)1714 1046 y Fm(0)o(0)1702 1097 y Fk(2)1755 1076 y Fo(.)37 b(B)26 b(will)h(c)n(ho)r(ose)e(an)h(edge)g Fn(f)32 b Fo(=)22 b(\()p Fn(u;)14 b(v)s Fo(\))24 b Fl(2)f Fn(T)3123 1088 y Fk(1)3186 1076 y Fo(with)k(one)-85 1176 y(end)f(in)g Fn(V)19 b Fo(\()p Fn(T)325 1145 y Fm(0)313 1196 y Fk(2)350 1176 y Fo(\))27 b(and)f(the)g(other)g(end)g(in)g Fn(V)19 b Fo(\()p Fn(T)1336 1145 y Fm(00)1324 1196 y Fk(2)1378 1176 y Fo(\).)37 b(No)n(w)25 b(con)n(tract)g(the)h(edge)g Fn(f)9 b Fo(.)36 b(In)26 b(the)h(new)f(graph)f Fn(G)3131 1145 y Fm(\003)3169 1176 y Fo(,)i(b)r(oth)f Fn(T)3462 1188 y Fk(1)-85 1275 y Fo(and)k Fn(T)128 1287 y Fk(2)194 1275 y Fo(b)r(ecome)g(spanning)g(trees)f Fn(T)1110 1245 y Fm(\003)1098 1296 y Fk(1)1177 1275 y Fo(and)h Fn(T)1402 1245 y Fm(\003)1390 1296 y Fk(2)1470 1275 y Fo(and)f(they)i(are)e(edge) g(disjoin)n(t.)44 b(It)31 b(follo)n(ws)e(b)n(y)g(induction)i(that)-85 1375 y(B)e(can)g(win)h(the)g(game)f(on)h Fn(G)863 1345 y Fm(\003)931 1375 y Fo(and)f(then)h(wins)g(the)g(game)f(on)g Fn(G)h Fo(b)n(y)f(uncon)n(tracting)g(the)h(edge)f Fn(f)9 b Fo(.)43 b(Of)29 b(course)-85 1474 y Fn(f)36 b Fo(is)27 b(c)n(hosen)g(\014rst)g(of)h(all)f(still!)-85 1628 y(If)f(A)h(c)n(ho)r (oses)e(an)h(edge)g Fn(x)h Fo(in)f(neither)h(of)f(the)h(trees)e(then)i (B)f(can)g(c)n(ho)r(ose)f(an)h(arbitrary)f(edge)g Fn(f)35 b Fo(of)27 b Fn(T)3123 1640 y Fk(1)3159 1628 y Fo(.)37 b(No)n(w)26 b(let)-85 1727 y Fn(e)i Fo(b)r(e)g(an)n(y)g(edge)f(of)i (the)f(unique)h(cycle)e(con)n(tained)h(in)g Fn(T)1680 1739 y Fk(2)1736 1727 y Fo(+)18 b Fn(e)p Fo(.)39 b(B)28 b(can)g(con)n(tin)n(ue)f(pla)n(ying)h(on)g Fn(G)19 b Fl(\000)f Fn(x)29 b Fo(as)e(though)-85 1827 y Fn(e)g Fo(w)n(as)g(the)h(deleted)g(edge.)36 b(W)-7 b(e)28 b(can)f(con)n(tract) g Fn(f)36 b Fo(as)27 b(b)r(efore)g(and)h(apply)f(the)h(ab)r(o)n(v)n(e)e (inductiv)n(e)i(argumen)n(t.)-85 1980 y(\(b\))g(F)-7 b(or)27 b(this)h(part)f(w)n(e)g(use)h(a)f(Theorem)g(due)h(to)f (Nash-Williams:)-85 2131 y Fp(Theorem)j(11.)41 b Fh(L)l(et)33 b Fn(k)j Fh(b)l(e)e(a)g(p)l(ositive)h(inte)l(ger.)50 b(Then)35 b Fn(G)f Fh(c)l(ontains)f Fn(k)k Fh(e)l(dge)d(disjoint)h(sp)l (anning)f(tr)l(e)l(es)f(i\013)h(for)-85 2230 y(every)c(p)l(artition)h Fl(P)e Fo(=)23 b(\()p Fn(V)730 2242 y Fk(1)768 2230 y Fn(;)14 b(V)853 2242 y Fk(2)891 2230 y Fn(;)g(:)g(:)g(:)27 b(;)14 b(V)1137 2242 y Fj(`)1169 2230 y Fo(\))30 b Fh(of)h Fn(V)49 b Fh(we)30 b(have)889 2410 y Fn(e)p Fo(\()p Fl(P)7 b Fo(\))22 b(=)h Fl(j)p Fn(E)5 b Fo(\()p Fl(P)i Fo(\))p Fl(j)23 b Fo(=)1595 2331 y Ff(X)1519 2510 y Fk(1)p Fm(\024)p Fj(i