Андрей Михайлович Райгородский - Задачи о раскрасках

BKJIJOqaJI Halli rMrreprpacp) M

eHTOM c =

14

J4mi(~n

B IIOCJie'AHeM BbIKJIMKe, IIOMMMO 06b1qHblX paBeHeTB, eeTb O'AHO aeMMITTO-

n!~(~r.

HeKOTOpOM c

n

( v'2mi(~)")2
e
= ~. rnn. r2n.

TMqeeKoe. KaK e HMM 6opOTbe.H? Hy, TOqHo MO:>KHO eKa3aTb, qTo e~eeTByeT

'AYKQM.H, e IIOMOI.U;blO KOTOpOM JierKO 'AOKa3bIBaeTC.H HepaBeHeTBO

2.

"'~ .

4>.opMyJI, B KOTOpbIX O'AHO-

BpeMeHHO yqaeTByIDT o6e MMpOBbie KOHeTaHTbl

,D;oKa3aTeJibCTBO TeopeMbl

2

2(n!)
n . (2n)!

c

'

II~aeM BO)l(,ZJ;eJieHHOe HepaBeHeTBO m::;; C
1

JC.

TeopeMa 'AOKa3aHa.

15

vn ·2n

e K034>4>MD;M-

D

6. t(aJihHenwee yicyqweHue HH)KHeu on;eHKH m(n)
c IIOMOI.QhlO paH,ll;OMU3UpOBaHHOro aJiropUTMa
rrepeKpacKu
B 3TOM pa3,a;eJie MbI 11erroJib3yeM 11HOH BepoHTHOeTHbIH rro,a;xo,a;, He)KeJil1 ,a;o e11x rrop, 11 ,a;oKa)KeM eJie,a;yrorn;yro TeopeMy, rroJiyqeHHyro H. EeKoM 11
,[VK. CrreHeepoM.
TeopeMa 3. IIpu Bcex oocmamotJ.1iO 6oJZbU1UX n BbtnOJZ1ie1iO ttepaBettcmBO

m(n)

>~

[.!.2 3vJn.
i:Ilri" 2n-l].

KoHe'IHO, MO)KHO 6bIDO HaIIHeaTb B cpopMyJI11pOBKe 1/4 H 2n, HO TaK
6y,a;eT y,a;o6Hee 'AJ151,lJ;OKa3aTeJiberna, K KOTopoMJ Ha eeif pa3 MbI 6e3 BrnKHx
npe,a;11CJIOBl1H rrpHeTJIIl1M.
,ll;oKa3aTeJibCTBO TeopeMhI 3. IlyeTb H = (V, E)- n-o,a;Hopo,a;HbIH r11neprpacp e m = [x · 2n- 1 ] pe6paMH, r,a;e

era eTPYKTYPY H IIOBbieHTb TeM caMbIM BepoHTHOeTb Toro, 'ITO Ha BbIXO,a;e Bee pe6pa OKa)l{JTC51 Heo,a;Hou;BeTHbIMH. Pa3JMeeTrn, KaqeeTBO IIIara 2
3aBl1Cl1T OT BbI6opa p' 11 CKOpo Mb! JBH,a;HM, KaK tty)KHO 3TOT Bbr6op oeyrn;eeTBJIHTb OIITl1MaJibHO.
IlycTb §: - eo6bITl1e, coeTOHrn;ee B TOM, 'ITO paeKpaeKa He y,a;aJiaCb,
T. e. eyrn;eeTByroT O,lJ;HOll;BeTHbie pe6pa. KaK KOHKpeTHOe pe6po f MO)KeT
OKa3aTbCH 0,lJ;HOll;BeTHbIM? ECTb Bcero 6 Bap11aHTOB:
1) A 1,1: pe6po f KpaeHoe rroCJie IIIara 111 Kpaettoe rrocJie IUara 2;
2) A 1,2 : pe6po f KpaeHoe rroCJie IIIara 111 CHHee rroCJie IIIara 2;

f
f
S) Cf,l: pe6po f
6) C1,2 : pe6po f
3) A 1,3 : pe6po
4) A 1.4: pe6po

CHHee rroCJie IUara 111 c11Hee rroCJie IIIara 2;
c11Hee rroCJie IIIara 111 KpacHoe rroCJie IIIara 2;
Heo,a;Hou;BeTHoe rroCJie IIIara 1 11 Kpaettoe noCJie IIIara 2;
Heo,a;Hou;BeTHoe rroCJie IUara 1 11 e11Hee rroeJie IIIara 2.

QqeBH,a;HO,

x=~·~.

§:

v,

IlOKa)KeM, 'ITO eyrn;ecrnyeT paCKpaeKa B 2 u;BeTa MHO)KeCTBa
rrpH KOTOpOH Bee pe6pa Heo,a;Hou;BeTHbI. PaCKpacey 6y,a;eM eTp011Tb e IIOMOIIJ;bIO
CJie,a;yrorn;ero patt,a;OMl13HpOBaHHOro aJiropHTMa.
Illar 1. Kpae11M BeplllHHbI He3aBHeHMO ,a;pyr OT ,a;pyra, e BepoHTttoeTbIO
1
2 Bbl611pa51 ,lJ;JI51 Ka)K,lJ;Ol1v BeplllHHbI O,lJ;l1H 113 ,a;Byx u;BeTOB - KpaCHbIHv HJll1

= LJ (Af,l UAJ,2 UAJ,3 UAJ,4 U Cf,l U Cf,2),
fEE

P(A1,1 ) =P(Af,3),

P(Af.2) =P(A1, 4 ),

P(Cf,l) =P(C1,2 ).

Il03TOMY

P(§:) ~ 2

L (P(A1,1) + P(A1,2) + P(Cf,1)).
fEE

c11H11if. IlycTb D - CJiyqaifHoe MHO)Keerno BepIII11H, np11Ha,a;Jie)Karn;11x o,a;Hou;BeTHbIM pe6paM (06'be,a;11HeHHe Bcex pe6ep, KOTOpbre OKa3aJil1Cb O,lJ;HOu;BeTHbIM11). 3TO MO)KeT 6bITb, HarrpHMep, 11 nyeToe MHO)KeeTBO.
Illar 2. IlyCTb p E [O, l] (Mb! ,lJ;JIH Ka)K,lJ;Oro n BbI6epeM KOHKpeTHOe p
no3,a;Hee). PaeeMaTpHBaeM TOJibKO BepIII11HbI 113 MHO)Kecrna D. Y Ka)K,lJ;OH
113 Hl1X Mb! He3aBl1eHMO OT Bcex oeTaJibHbIX BepIII11H MHO)KeCTBa D MeH51eM u;BeT Ha npOTHBOIIOJIO)KHbIH c BepOHTHOCTbIO p H He MeH51eM u;BeT c
BepOHTHOCTbIO 1 - p. l1HbIMH CJIOBaMH, y Hae KaK 6br eeTb MOHeTa co CMern;eHHbIM, Boo6rn;e roBOpH, u;eHTpOM T51)KeCTl1. Ilp11 CJiyqaHHOM 6pocaHl111
MOHeTa Jl0)1{11TC51 peIIIKOH KBepxy e BepOHTHOCTbIO p 11 OpJIOM - c BepOHTHOeTbIO 1- p. Mbr 6pocaeM MOHezy IDI pa3 11, ecJI11 B oqepe,a;ttoM 6pocaH1111
MOHeTa na,a;aeT peIUKOH KBepxy, MeH51eM u;BeT COOTBeTernyrorn;eif BepIII11HbI
113 D; 11Ha'le He MeH51eM.
IlOH5ITHO, 'ITO Illar 1 - 3TO o6bI'IHa51 CJiyqaHHM paeKpacKa, e IIOMOIIJ;bIO
KOTOpOH Mb! ,lJ;OKa3bIBaJil1 HepaBeHeTBO m(n) ~ 2n- l + 1. TaKl1M o6pa30M,
Illar 2 - 3TO IIOIIbITKa 11enpaBHTb OIUH6KH IUara 1 3a eqeT Toro, 'ITO Illar 1
He'IJECTBl1TeJieH K BH,a;Y 11exo,a;Horo r11rreprpacpa, a Illar 2 IIbITaeTCH yqeCTb

KaK MOrJIO CJl)"-IHTbC51, 'ITO pe6po f 6bmo HeO,a;Hou;BeTHbIM IIOCJie IUara 1, HO CTaJIO KpaCHblM IIOCJie IIIara 2? KoHe'IHO, eHHl1e BepIII11HbI pe6pa f'
HMeBIU11ern B HeM IIOCJie IIIara 1, ,lJ;OJl)l{HbI 6bIDl1 rrepeKpael1TbCH. Ho rroqeMy? KaK OHl1 IIOIIaJIH B MHO)KeCTBO D, eeJil1 f HeO,a;Hou;BeTHOe 11 B cpopM11poBaHl111 D He yqaeTBOBaJio? 3Ha'll1T, 6bIDO ern;e XOTH 6bI O,lJ;HO pe6po 0
2
BbLnOJZHeHO HepaBeHCffiBO

disc(H)

~

J2n ln(2m).

a2

PCli;-1 + ... +i;-nl >a)

~2e-2n.

TeopeMa 5 BO MHOrMX CMryau;M.HX ,z:i;aeT BeCbMa xopOIIIYJO ou;eHey. ,l(eiiCTBMTeJibHO, eCJIM m He CJIMIIIKOM BeJIMKO (HanpMMep, He 60Jibllle KaKoro~
HM6y,n;b MHoroqneHa OT n), a pe6pa r11:neprpacpa ,z:i;ocrnToqHo 6oJibIIIMe (HarrpMMep, nop.H,ZI;Ka n)' TO noJiyqaeTC.H, qTo He npOCTO MO)KHO Bcer,z:i;a c,z:i;eJiaTb BCe pe6pa HeO,ZJ;HOI.J;BeTHbIMM, HO MO)KHO ern;e M C,ZJ;eJiaTb TaK, qT06bI
pa3HMu;a Me)l{',,D;y KOJIMqecTBaMM BepIIIHH pa3HOro I.J;BeTa B Ka)K,D;OM pe6pe
He npeBocxo,n;MJia KopHH M3 ero pa3Mepa, YMHO)KeHHoro Ha Jiorap11:cpM ero
pa3Mepa. TaKMM o6pa30M, onTMMaJibHOe yKJIOHeHMe 6ecKoHeqHo MaJio no
cpaBHeHMIO c q11:CJIOM BepIIIHH B Ka)K,ll;OM pe6pe.

.HTHOCThIO M,D;eT B Toqey -1. ,l(aJibIIIe OH CHOBa BhI6MpaeT HanpaBJieHMe
,ZJ;BM)KeHM.H ~aHHO. TaK BOT, TeopeMa roBOpHT 0 TOM, qTO Kpaii:He MaJia
BepO.HTHOCTb, c KOTopoH: nb.HHMu;a ~eT cpaBHMTeJibHO ,n;aJieKO OT po,n;Horo

24

25

aKTMqecKM B TeopeMe 8 peqh M,ZJ;eT 0 COBepIIIeHHO KJiacc11:qecKOM o6'heKTe TeopMM Bepo.HTHOCTeH - 0 CJiyqaiiHOM 6Jly)K,ll;aHMM Ha np.HMOH. B IIIyToqHoH MHTepnpeTaI.J;MM, KOTOPYJO .H 06p1qHo paccKa3bIBaIO Ha JieKu;M.Hx,
B ToqKe 0 Ha np.HMOH HaXO,ZJ;MTC.H Ka6aK. l13 Hero BbIXO,ZJ;MT nh.HHMu;a, KO~
1 nepeMern;aeTCH B ToqKy 1 M c TaKOM~ )Ke BepoTOpbrn
c BepO.HTHOCTbIO 2

Ka6aKa. HanpHMep, npn n = 106 , a= 104 Bepo.HTHOCTb He 6oJibIIIe 2e- 50 ,
T. e., c,n;enaB MlfJIJIHOH maroB, nb.HHm.J;a y,n;aJIHTC.H OT «CH.HIOII.I;ero u;eHTpa» Ha
paCCTO.HHHe, paBHOe Bcero JIHIIIb ,n;ec.HTH TbIC.HqaM maroB, c Bepo.HTHOCTblO,
He npeBOCXO,ZJ;.Hm;eM: qy,n;OBHIIJ;HO MaJIOH BeJilfqlfHbl 2e- 50 •
.l);oKaJaTeJibCTBO TeopeMbI 8. BBlf,ZJ;Y CHMMeTpHH ,n;ocTaToqHo y6e,n;nThC.H B TOM, qTO

P ( ~ 1 + ... + ~ n > a) ~ e-

a2

3To H 3aBepIIIHT ,n;oKa3aTeJibCTBO TeopeMbl 5. Ho 3TO paBHOClfJibHO TOMy,
qTo c BepO.HTHOCTblO, MeHbIIIeH e,n;HHHD;bl, HaH.n;eTC.H f EE, ,ZJ;JI.H KOToporo
Ix (f) I >a. ,ZJ;JI.H Ka)l{,ZJ;oro oT,n;eJihHoro pe6pa f HMeeM
PClxCf)I > a) .=P(j
(no TeopeMe 8)
2

2n ln(2m)
21!1 ~2e __2_n_

_ ...£.__

2n •

~ 2e

TioJIO)l(HM A = £!.. I1MeeM

n

P(3 f : Ix Cf) I> a)~

P(eA.C.;1 +... +.;n) > eA.a)

~ e-A.a. EeA.C.;1 + ...+.;n)

n
n

= e-A.a.

EeA..;i

=

(no opMyJie ( 4))
(

1 (

2.

A
A)
Eo TI+
Eo----;(!
oo

k

oo

k ) )

(-

n

-A.a

=e .

(

k~o
oo

A2k
(2k)!

)

n

~

(3a cqeT Toro, qTQ (2k) ! ~ 2k · k !)
~ -A.a

" e

zk )n

oo

.(

Eo 2kA.. k !

(no oPMYJie --">