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

BepO.HTHOCThlO

1
2'

u

H c TaKOH )Ke Be-

pOHTHOCThlO OH H,D;eT BO BTOpoii Ka6HHeT; Bb16op Ka6HHeTa IIIKOJihHHKH

oc~eCTBJUllOT

30

He3aBHCHMO ,n;pyr OT ,n;pyra. 11HhIMH CJIOBaMH, Mhl KaK 6bI

pa3 6pocaeM CHMMeTpMqHYJO MOHeTKy, H eCJIM MOHeTKa B

HHH na,n;aeT peIIIKOH KBepxy, TO
HHaqe -

MMeIOT HerrycToe rrepeeeqeHHe. 3aBe,n;oMo B 3TOM rre-

i-ii

BO BTopo:H. BBe,n;eM o6o3HaqeHMe

COCTO.Hrn;ero B TOM, qTo TI.HTepKa
KaKoBa BepoRTHOCTh

P(Ai )

i-M

6poca-

IIIKOJibHHK H,D;eT B nepBblH Ka6HHeT,

Mi

Ai,

i = 1, ... , 15,

,n;JIH co6hITHR,

u;eJIHKOM norraJia B O,ll;HH Ka6HHeT.

3Toro co6hITHR7 TiocKOJihKY Bh16op npoH3BO-

,ll;HTC.H IIIKOJibHHKaMH He3aBHCHMO, Bepo.HTHOCTH rrepeMHO)l(alOTC.H, H Mbl

MeH.bWe

eeMHa,n;u;aTblO TaKOH HOMep He rrpoxo,n;HT...
JierKO BH,D;eTb, qTo ,ll;JUI

126

TI.HTepoK OTBeT ]')Ke nOJIO)l(HTeJibHbIM He

RBJUieTCH. CTpaHHoe qlfeJio, ,n;a? Hy, eeiiqae pa36epeMC.H! Mb1 )Ke BOJibHbI
B BbI6ope HCXO,ll;HOro KOJIHqeeTBa IIIKOJibHHKOB. ,l(aBaiiTe B03bMeM
TepKH, KaKHe TOJibKO MO)l(HO eoeTaBHTb H3
paT

126 = C~.

aeaRmU

ace

TIR-

qeJioBeK. 11X B aKKY-

Tionpo6yeM Terrepb paeea,n;HTb ,n;eBHTepbIX IIIKOJibHHKOB no

,ll;BYM Ka6HHeTaM. 11 BOT He TYT-TO 6bIJIO! TipH JII06o:H paeea,n;Ke B KaKOHTO Ka6HHeT nona,n;eT He Mettee TIRTM IIIKOJibHHKOB. Ho y Hae

Ka:Heaa.R.

TIR-

TepKa eeiiqac «B ,n;eJie». 3HaqHT, Bee IIJIOXO H Mbl HMeeM npHMep CHryaI.J;HH, Kor,n;a OTBeT Ha nepBOHaqaJibHhIH BOIIpoe ]')Ke He .HBJIHeTe.H YTBep,n;HTeJibHbIM.
11TaK, ,ll;JIH JII06bIX

10m

no.rryqaeM

cmpozo

CYMMbl BepO.HTHOCTeH H Halli MeTO,ll; eHoBa cpa6aTbrnaeT. Y)l(e e

126

16

n.HTepoK OTBeT YTBep,n;HTeJihHhIH, HO

C)'l4ecmay-

TI.HTepoK, ,ll;JUI KOTOpbIX OTBeT OTpHu;aTeJibHhIH. Bee 3TO npHBO,ll;HT

K o6rn;e:H noeTaHOBKe 3a,n;aqM, 0 KOTOpo:H Mhl H rrorOBOpHM B CJie,n;YJOrn;eM
pa3,n;eJie .

4

5

He nyraThCH, TaK KaK Mbl ero ynoTpe6JIHTb He 6y,n;eM). Ho (011HTb )Ke, .ZJ;JIH
Tex, KTO B TeMe) Cl1MilJll111;11aJibHbIH KOMITJieKC Tipe)l(,ZJ;e Bcero rropa rrepeHTl1 OT IIIKOJibHl1KOB K a6cTpaKTHblM o6'beKTaM.

A

11MeHHO, BBe.n;eM 110HRTl1e 2unep2pa2.

cpa3y IlOHRTh, qTo B TepM11HaX 3TOH BeJI11q11Hbl pe3yJibTaThl

X11TpOCITJieTeHl1IO 3,ZJ;aKHX «Cap,n;eJieK» (CM. p11c. 1). B CBOl1X JieKD;IDIX H qacTO
yn0Tpe6JIH10 CJIOBO «cap,n;eJibKa»

Jll1Illb ,ZJ;Ba cnoco6a on11caHIDI

o,n;Horo 11 Toro )Ke HBJieHIDI.

17 ~ m(5)~126 .

o6o3HaqeHIDI pe6pa r11neprpacpa, HO

(1)

KapT11HOK He p11cyio. MHe caMOMY Jierqe rrpe.n;cTaBJIHTb ce6e 11MeHHO 3,ZJ;a-

Y JI106oro

KYJO KaCTplOJibKY (MHO)KeCTBO BepIII11H)

c HaMeIIIaHHbIMl1 B Hett cap,n;eJibKa-

T11qeCKoe q11CJIO paBHO .ZJ;BYM, 1103TOMY m(S) ~ 17, HO cyrn;ecrnyeT 5-0.ZJ;HO-

M11-pe6paMl1. HeKOTOpbie «11pO.ZJ;Bl1HYThie 110Jlb30BaTeJil1» BCI10Ml1HalOT Bbl-

po,n;HblH r1111eprpacp co 126 pe6paM11, y KOToporo xpoMaT11qecKoe q11CJI0

pa)KeH11e «Cl1MilJll111;11aJibHbIH KOMITJieKC» (rrpocb6a Tex, KTO He CJibIIIIaJI ero,

6oJibIIIe ,n;Byx, a 3Haq11T, m(5) ~ 126.

5-o,n;Hopo,n;Horo mrreprpacpa c IIIeCTHa.n;n;aThlO pe6paM11 xpoMa-

QqeBH,ll;HOe 0606m;eH11e HepaBeHCTB (1) rrp11BO.ZJ;l1M HH)Ke:
zn - l

+ 1 ~ m(n) ~ c;n - 1'

(2)

Mbl He CTaHeM ,ZJ;OKa3bIBaTb 3Tl1 HepaBeHCTBa, Be,ZJ;b 3TO COBCeM JierKoe
ynpa)l(HeH11e. Ho Mbl 06cy,n;11M Borrpoc 0 TOM, HaCKOJibKO 6Jil13KH .n;pyr K
.n;pyry BepxHRH 11 HH)KIDIH ou;eHKH. B caMoM ,n;eJie, xopoIIIo H3BeCTHO TO)K.n;ecrno (CM.

[3])

o
C2n-1
+ cl2n -

. 0

1

en
+ c2n-l
_
+ ... + cn-1
2n - 1 + 2n-1 + ···
2n - 1 -

z2n-1

·

TalOKe 113BeCTHO, KOHeqHo, qTo ,ZJ;Ba u;eHTpaJibHbIX CJiaraeMbIX B 3TOM TO)K.n;ecTBe HBJIHIOTCH B HeM caMbIMl1 6oJihIIIl1Ml1. Tip11 3TOM o6m;ee q11CJIO CJiaraeMbIX B JieBOH qaCTl1 TO)l(,ZJ;eCTBa paBHO
22n-1

_ _ - (l + 3£) e In 2
4

r

p

£)

Z

= ( 1 - i ) e- 1 ,

,aaJiee, 3aMetJ:aa, tJ:TO rrpH Bcex ,ZJ;OCT3TOtJ:HO 60JibIIIHX
HepaBeHCTBO

CHH3y, TaK KaK

4

n

crrpaBe,D;JIHBO

2 n
n 2 '

IIOJiyqaeM

OHa H,n;eT y Hae c MHHyCOM. PacCMOTpHM CHatJ:aJia ee 3HaMeHaTeJib:

v!
= v(v-l) · .. . ·(v-n+l) = vn.
n!(v-n)!
n!
n!

~e

p~21-n(1-i)e-1.

= ev In 2+m ln(l - p) ~ ev ln2- pm

B CHJIY CBOHCTBa JIOrapHcpMa. Terrepb OQeHHM BeJIHtJ:HHy

en=

_ n(n -1) _ 4n(n -1)(2n -1)
2
2v
6v

B

3aMeTHM, tJ:TO
2v (l - p )m

n--... oo ,
,n;mI BeJIHn
tJ:HHhI 2 v. Tio3TOMY rrpH Bcex ,n;ocTaTOtJ:Ho 60JihIIIHx n BhIIIOJIHeHo HepaaeHCTpeMHTCH K eymo rrpH

e

2 QBeTa 2v IIITYK.
2v (1 - p )m < 1 rrpH Bcex ,n;ocTaTOtJ:HO

ae,n;h acero pacKpacoK MHO:>KecTBa
IIIHX

A - «Haff,n;eTCH pacKpacKa aep-

6v 2
n2
H6o v =-.To :>Ke caMoe BepHo
2

v ln 2- pm

e

(i-!)
.... · (i- n-1).
v
v

~e

TiocKOJihKY

v ln 2- 21 - n (I- f )e- lm

~e

2

1

e < 2,

n2 ln 2 - 2I-n (1 + f - 3e2 ) n2(ln 2)2"
2

4

s

4

c orpoMHhIM 3arracoM

£

.AHaJiorHtJ:HO

3£2

4-g->

£
100·

B HTore
2

2

n ln 2 _ 21-n (I+ f _ 3e 2 ) n (ln 2)2"

CTaJIO 6bITh,

p

2 - n, YMHO:>KeHHOH Ha OTHOIIIeHHe ,n;ayx
n - 1 CK060K Ka:>K,n;Oe. H3YtJ:HM rrpOH3Be,n;e-

paBHO BeJIHtJ:HHe

rrpOH3Be,n;eHHH, COCTOHIQHX H3

1

10

e

2

4

s

4

rrpH Bcex ,n;ocTaTOtJ:Ho 6oJihIIIHX

n2 ln 2 _ (l
=e

n.

2

f _ 3e2 ) n2 ln 2
s
2

+4

TeopeMa ,n;oKa3aHa.

11

En2 ln 2

< e-200KepTBYH KOHCTPYKTHBHOCThIO, MhI peaJihHO
ynpocTMJIH ce6e )KI13Hh. ,l(o CHX rrop HeH3BeCTHhl .HBHhie KOHCTp)1Kll;HH
rHrreprpacl>oB co CTOJih MaJihIM qHCJIOM pe6ep H xpoMaTHqecKMM qHCJIOM,
60JihIIIHM ,ll;Byx. JIHIIIh COBCeM He,n;aBHO - B 2013 ro,n;y- X. fe6ay3p IIOCTpOMJia npHMep rHrreprpacl>a, y KOTOporo qHCJIO pe6ep He npeBOCXO,ll;HT

c> 0 .

2 n+cn2/3 ,

3TO rrpeKpaCHOe Bhlpa:>KeHHe, IIOCKOJihKY OCHOBHOM COMHO)KMTeJih -

2n -

COBrra,n;aeT c H3BeCTHOM HaM 3KCIIOHeHTOM B BepxHeM H HH:>KHeM ou;eHKax.
2
2n2/3
Ho 3TO ropa3,n;o rna6ee TeopeMhI 1, Be,n;h n HecpaBHHMO MeHbIIIe, qeM

5. Y;cyqmeHHe HH)KHeH: on;eHKH BeJIHqHHbI m(n)
c

noMo~LIO

B 3TOM pa3,n;eJie

ma,n;Horo aJiropHTMa

MhI y~IIIHM HH:>KHIOIO ou;eHKY m(n) npHMepHo B

P11c. 2

tin

pa3.

MaTHqecKoe qHCJio rpacpa paBHo ,n;BYM»? 0Ho 03HaqaeT, qTo MHO:>KeCTBO

TeopeMa 2. C)'L4eCmByem maKWI KOHcmm-1.ma c > 0, tJ.mo O.ll5l JZ106ozo n
BbLnOJlHeHO HepaBeHCmBO

BepIIIHH rpaKHOM H,n;ee,
KOTOpyIO rrpe,n;JIO)KMJI A. IIJI:Yxap. ,l(JI.H OIIHCaHMH M,ll;eH BBe,n;eM HeCKOJihKO

=

HOBhIX rroHHTHM. TiycTb ,n;aH rHrreprpaa (cM. pHc. 3). TaKoM: rpa

H = (V, E) em pe6paMM. MbI xoTMM ITOKa3aTb, qTo rrpM

OTKy'Aa H

>0

(He 3aBMe.Hm;eM HH OT qero, --">