А.Б. Угольников - Лекции по дискретной математике (1083729), страница 3
Текст из файла (страница 3)
m1 +m2 + .. + mn = k, ïðè ýòîì èìååòñÿ ðîâíî ïî îäíîìó ñëàãàåìîìó äëÿ êàæäîãî âîçìîæíîãî íàáîðà(m1 , ..., mn ) ñ öåëûìè íåîòðèöàòåëüíûìè mi . Êàæäîìó òàêîìó ñëàãàåìîìó ñîîòâåòñòâóåò âûáîðêàk èç n ýëåìåíòîâ ñ ïîâòîðåíèÿìè: mi êîëè÷åñòâî i-ãî ýëåìåíòà â âûáîðêå. Îòñþäà ïîëó÷àåì:Êîýôôèöèåíò ïðèx∞Xïîëó÷àåòñÿ ïðèâåäåíèåì ïîäîáíûõ ñëàãàåìûõ âèäàbnk ,ak = CãäåbnkC èíòåðåñóþùåå íàñ êîëè÷åñòâî âûáîðîê èçnýëåìåíòîâ ïîkñ ïîâòîðåíèÿìè.Êàê ïîêàçûâàëîñü ðàíåå(1 + x + x2 + ...)...(1 + x + x2 + ...) = (1 − x)−n|{z}n íåêîòîðîé îêðåñòíîñòè íóëÿ−n(1−x) àíàëèòè÷åñêàÿ ôóíêöèÿ, ïîýòîìó å¼ ìîæíî åäèíñòâåííûìîáðàçîì ïðåäñòàâèòü â âèäå ñõîäÿùåãîñÿ ê íåé ðÿäà Òåéëîðà:(1 − x)−n =∞X(−1)kk=0=∞Xk=0−n(−n − 1)...(−n − k + 1) kx =k!∞(n + k − 1)! k X kx =Cn+k−1 xk(n − 1)!k!k=0Ïðîèçâåäåíèå (1) òîæå ñõîäÿùèéñÿ â íåêîòîðîé îêðåñòíîñòè íóëÿ ê ôóíêöèè(1 − x)−nðÿä Òåéëîðà.
Îòêóäà çàêëþ÷àåì, ÷òîkbnk = ak = Cn+k−1CÊîíå÷íûå ïîëÿÈç êóðñà àëãåáðû èçâåñòíà ñëåäóþùàÿÒåîðåìà. Äëÿ âñÿêîãî ïðîñòîãî p è íàòóðàëüíîãî n ñóùåñòâóåò åäèíñòâåííîå ñ òî÷íîñòüþäî èçîìîðôèçìà ïîëå èç pn ýëåìåíòîâ.nßñíî, ÷òî äëÿ n = 1 ýòî Zp .  ýòîì ïóíêòå ìû ïîñòðîèì êîíå÷íîå ïîëå ïîðÿäêà päëÿnïðîèçâîëüíîãî n. Òàêèå ïîëÿ íàçûâàþòñÿ ïîëÿìè Ãàëóà è îáîçíà÷àþòñÿ GF (p ).Ðàññìîòðèì Zp [x] êîëüöî ìíîãî÷ëåíîâ îäíîé ïåðåìåííîé íàä ïîëåì Zp .
Ïî äîêàçàííîìó âîäíîé èç ïðîøëûõ ëåêöèé ñóùåñòâóåò πn (x) ∈ Zp [x] íåïðèâîäèìûé ìíîãî÷ëåí ñòåïåíè n. Ðàñ.ñìîòðèì ôàêòîð-êîëüöîZp [x] (πn (x))è ïîêàæåì, ÷òî îíî ÿâëÿåòñÿ èñêîìûì ïîëåì. Âî ïåðâûõ,πn (x), ò.å. òîëüêî èç ìíîãî÷ëåíîâ. ñòåïåíèíå âûøå n − 1. Âî âòîðûõ, âñÿêèé òàêîé ìíîãî÷ëåí ëåæèò â í¼ì. Òàêèì îáðàçîì,Zp [x] (πn (x)) = pn . Äàëåå ïîêàæåì, ÷òî ýòî êîëüöî îáëàñòü öåëîñòíîñòè, ò.å. â í¼ì íåò äå.ëèòåëåé íóëÿ: äåéñòâèòåëüíî, åñëè P (x)Q(x) = 0 â Zp [x] (πn (x)), ò.å. πn (x)P (x)Q(x), òî, â ñèëóíåïðèâîäèìîñòè πn (x), ëèáî πn (x)P (x), ëèáî πn (x)Q(x), ÷åãî ïðè íåíóëåâûõ P (x) è Q(x) áûòüíå ìîæåò, ò.ê.
èõ ñòåïåíü ñòðîãî ìåíüøå ñòåïåíè πn (x). Èç êóðñà àëãåáðû õîðîøî èçâåñòíî, ÷òîî÷åâèäíî, îíî ñîñòîèò òîëüêî èç îñòàòêîâ îò äåëåíèÿ íà ìíîãî÷ëåíêîíå÷íàÿ îáëàñòü öåëîñòíîñòè ÿâëÿåòñÿ ïîëåì.15Òåîðèÿ ÐàìñåÿÈçëîæåíèå ñåðü¼çíîãî ðåçóëüòàòà, äîêàçàííîãî Ðàìñååì, íà÷í¼ì ñ ïðîñòîé øêîëüíîé çàäà÷è:äëÿ êàêîãî ìèíèìàëüíîãîNâ ïîëíîìN- âåðøèííîì ãðàôå, ð¼áðà êîòîðîãî ðàñêðàøåíû â 2 öâå-òà, ìîæíî ãàðàíòèðîâàòü ñóùåñòâîâàíèå îäíîöâåòíîãî òðåóãîëüíèêà? Îêàçûâàåòñÿ, îòâåò:N =6ñóùåñòâîâàíèå òðåóãîëüíèêà äëÿ 6-òè âåðøèííîãî ãðàôà ëåãêî äîêàçûâàåòñÿ ðàññìîòðåíèåì ïðîèçâîëüíîé âåðøèíû, èç êîòîðîé ïî ïðèíöèïó Äèðèõëå âûõîäèò ïî êðàéíåé ìåðå 3 ðåáðà îäíîãî öâåòà,à çàòåì ðàçáîðîì âîçìîæíûõ âàðèàíòîâ öâåòîâ ð¼áåð ìåæäó ýòèìè òðåìÿ âåðøèíàìè.
Ïðèìåð 5-òèâåðøèííîãî ãðàôà áåç îäíîöâåòíîãî òðåóãîëüíèêà ëåãêî ñòðîèòñÿ.X = {x1 , ..., xn }r:Tr (X) = {A ⊆ X |A| = r}Ïåðåéä¼ì ê îáùåé ïîñòàíîâêå çàäà÷è. Ïóñòüñòâî,r ∈ N. êîíå÷íîån-ýëåìåíòíîåìíîæå-Îïðåäåëèì êëàññ ïîäìíîæåñòâ ìîùíîñòèα è β îáðàçóþò ðàçáèåíèå Tr (X), åñëèα ∩ β = ∅.Òåîðåìà. (Ðàìñåé) Äëÿ ëþáûõ p, q > r ∈ N ñóùåñòâóåò N (p, q, r), òàêîå ÷òî äëÿ ëþáîãî n > Näëÿ ëþáîãî (α, β)-ðàçáèåíèÿ ñèñòåìû ïîäìíîæåñòâ Tr (X) âûïîëíåíî ñëåäóþùåå:ëèáî ñóùåñòâóåò ïîäìíîæåñòâî A ⊆ X òàêîå, ÷òî |A| = p è Tr (A) ⊆ αëèáî ñóùåñòâóåò ïîäìíîæåñòâî B ⊆ X òàêîå, ÷òî |B| = q è Tr (B) ⊆ βÏî îïðåäåëåíèþ ãîâîðèì, ÷òî äâå ñèñòåìû ïîäìíîæåñòâα ∪ β = Tr (X)èÄîêàçàòåëüñòâî.
Äîêàçàòåëüñòâî ïðîâåä¼ì ïî èíäóêöèè.Øàã 1. Äëÿ r = 1 Tr (X) ìíîæåñòâî îäíîýëåìåíòíûõ ïîäìíîæåñòâ X ,ò.å., ôàêòè÷åñêè, ñàìî(α, β) ðàçáèåíèå ìíîæåñòâà X . Àíàëîãè÷íî Tr (A) ' A, Tr (B) ' B . Òðåáóåòñÿ ïðåäúÿâèòü òàêîå N , ÷òî äëÿ ëþáîãî n > N ëèáî â α áóäåò p ýëåìåíòîâ, ëèáî â β q . ßñíî, ÷òî N = p+q −1X,òîãäàïîäõîäèò.Øàã 2.q = r. Ïóñòü β íå ïóñòî. Òîãäà âîçüì¼ì â êà÷åñòâå B ëþáîé ýëåìåíòq = r-ýëåìåíòíîå ïîäìíîæåñòâî â X .
Åñëè β ïóñòî, òîãäà α âñå r-ýëåìåíòíûåïîäìíîæåñòâà X . Åñëè n > p âîçüì¼ì â êà÷åñòâå A ëþáîå p-ýëåìåíòíîå ïîäìíîæåñòâî X . Àíàëîãè÷íî ðàçáèðàåòñÿ ñëó÷àé p = r (N â ýòîì ñëó÷àå ðàâíî q ).èçβÐàçáåð¼ì ñëó÷àé ýòî è áóäåòØàã 3.Ïðåäûäóùèå äâà øàãà áóäåì ðàññìàòðèâàòü êàê áàçó äëÿ èíäóêöèè. Èíäóêöèîííûéïåðåõîä áóäåì îñóùåñòâëÿòü ïî ñëåäóþùåé ñõåìå: ñ÷èòàåì óòâåðæäåíèå äîêàçàííûì äëÿ òðîåê(p − 1, q, r), (p, q − 1, r) è äëÿ âñåõ òðîåê âèäà (p0 , q 0 , r − 1), ãäå p0 , q 0 = r − 1, r, r + 1, ....
Èíäóêöèîííûìïåðåõîäîì ìû ïîêàæåì ñïðàâåäëèâîñòü óòâåðæäåíèÿ äëÿ òðîéêè (p, q, r), ïðè÷¼ì ïîêàæåì, ÷òî âêà÷åñòâå N (p, q, r) ìîæíî âçÿòü N (p1 , q1 , r − 1) + 1, ãäå p1 = N (p − 1, q, r), q1 = N (p, q − 1, r).00Èòàê, ïóñòü |X| = N (p1 , q1 , r−1)+1, (α, β) ðàçáèåíèå Tr (X). Ðàññìîòðèì X = X \ {x1 }, |X | =0000N (p1 , q1 , r −1). Ïóñòü (α , β ) ðàçáèåíèå Tr−1 (X ), ïîðîæä¼ííîå (α, β), ò.å.
D ∈ α ⇔ D ∪{x1 } ∈ α,D ∈ β 0 ⇔ D ∪{x1 } ∈ β . Ïî èíäóêöèîííîìó ïðåäïîëîæåíèþ âûïîëíåíî îäíî èç ñëåäóþùèõ óñëîâèé:00000à) ñóùåñòâóåò A ⊆ X , ò.÷. |A | = p1 , Tr−1 (A ) ⊆ α ;00000á) ñóùåñòâóåò B ⊆ X , ò.÷. |B | = q1 , Tr−1 (B ) ⊆ β .0Ðàçáåð¼ì, ê ïðèìåðó, ñëó÷àé à), ñëó÷àé á) ðàçáèðàåòñÿ àíàëîãè÷íî. |A | = p1 = N (p − 1, q, r).0Ðàññìîòðèì (α̂, β̂) ðàçáèåíèå Tr (A ), ò.÷.
α̂ ⊆ α, β̂ ⊆ β. Îïÿòü ïî ïðåäïîëîæåíèþ èíäóêöèèâîçìîæíà îäíà èç ñèòóàöèé: ⊆ A0 , ò.÷. |Â| = p − 1, Tr (Â) ⊆ α̂ ⊆ α;0à2) ñóùåñòâóåò B̂ ⊆ A , ò.÷. |B̂| = q, Tr (B̂) ⊆ β̂ ⊆ β. ñëó÷àå à2) ñðàçó êëàä¼ì B = B̂ èñêîìîå ìíîæåñòâî. ñëó÷àå à1) ïîëîæèì A =  ∪ {x1 }. Ïîêàæåì, ÷òî A óäîâëåòâîðÿåò óñëîâèþ òåîðåìû. Äåéñòâèòåëüíî, |A| = p è îñòà¼òñÿ ïðîâåðèòü, ÷òî Tr (A) ⊆ α. Äëÿ ïðîèçâîëüíîãî D ∈ Tr (A) ëèáîx1 6∈ D, ëèáî x1 ∈ D.
 ïåðâîì ñëó÷àå èìååì: D ∈ Tr (Â) ⇒ D ∈ α̂ ⇒ D ∈ α. Âî âòîðîì ðàññìîòðèìD0 = D\{x1 }. D0 ∈ Tr−1 (Â) ⊆ Tr−1 (A) ⊆ α0 , îòêóäà, ïî ïîñòðîåíèþ ìíîæåñòâà α0 , èìååì D ∈ α.à1) ñóùåñòâóåòÄîêàçàòåëüñòâî îêîí÷åíî.Ïðèìåð, ðàçîáðàííûé â íà÷àëå ïóíêòà, ïîêàçûâàåò, ÷òî âî ââåä¼ííûõ îáîçíà÷åíèÿõ òî÷íàÿíèæíÿÿ îöåíêà íàN (3, 3, 2) åñòü 6. Åñëè ðóêîâîäñòâîâàòüñÿ ïðåäëîæåííûì â òåîðåìå ðåêóðåíòíûì16ñîîòíîøåíèåì íàN (p, q, r),ïîëó÷èìN (3, 3, 2) = N (N (2, 3, 2), N (3, 2, 2), 1) + 1 = 2N (3, 2, 2) = 2 · 3 = 6. äàííîì ñëó÷àå ïî ïðåäëîæåííîìó ïðàâèëó íàõîäèòñÿ ìèíèìàëüíîå âîçìîæíîåN.Îäíàêî, êàêìû óâèäèì íèæå, ýòî íå âñåãäà òàê, è ðåêóðåíòíûå ñîîòíîøåíèÿ äàþò ñèëüíî çàâûøåííûå çíà÷åíèÿN.Íèæå ïîäN (p, q, r)áóäåì îáîçíà÷àòü ìèíèìàëüíîå ïîäõîäÿùåå17N.Ëåêöèÿ 5.Ðàññìîòðèì íåñêîëüêî ñëåäñòâèé èç òåîðåìû Ðàìñåÿ.Ñëåäñòâèå.N (p, q, r) 6 N (N (p − 1, q, r), N (p, q − 1, r), r − 1) + 1.Ñëåäñòâèå. r = 2.N (p, q, 2) 6 N (p − 1, q, 2) + N (p, q − 1, 2).Ñëåäñòâèå.N (p, q, 2) 6 max(p, q)2p+q .Äîêàçàòåëüñòâî.N (p, q, 2) 6 max(p − 1, q)2p+q−1 + max(p, q − 1)2p+q−1 6 max(p, q)2p+q .Ââåäåì îáîçíà÷åíèåN (p) = N (p, p, 2).Ñëåäñòâèå.
N (p) 6 p 22p .Òåîðåìà. (Ýðäåøà) ∀p > 2N (p) >Äîêàçàòåëüñòâî.p1p 2 2 −1 .eÐàññìîòðèì ïîëíûé ãðàô ñn âåðøèíàìè Kn . Áóäåì êðàñèòü åãî ðåáðà â äâàöâåòà.  ýòîì ñëó÷àå óòâåðæäåíèå òåîðåìû îçíà÷àåò ñëåäóþùåå. Êàêîå íàèìåíüøåå êîëè÷åñòâîKn ,âåðøèí äîëæíî áûòü â ïîëíîì ãðàôå÷òîáû â íåì íàøåëñÿ ïîëíûé ïîäãðàôKp ,òàêîé ÷òîâñå åãî ðåáðà ïîêðàøåíû â îäèí è òîò æå öâåò. Åñëè ïðè äàííîé ðàñêðàñêå òàêîé ïîëíûé ïîäãðàôñóùåñòâóåò, íàçîâåì å¼ "õîðîøåé". Ïîñ÷èòàåì ÷èñëî ñïîñîá ðàñêðàñèòü ðåáðà ïîëíîãî ãðàôàòàê, ÷òîáû âñåãäà áûëà "õîðîøàÿ" ðàñêðàñêà.Cnp ÷èñëî ñïîñîáîâ âûáðàòüpKnâåðøèí áóäóùåãîKp .
Åãî ðåáðà ìîæíî îêðàñèòü â äâà öâåòà. Îñòàëüíûå ðåáðà ìîæíîñïîñîáàìè. Ïðè ýòîì, âñåãî ñïîñîáîâ ðàñêðàñèòü ðåáðà ïîëíîãî ãðàôà Kn â äâàîäíîöâåòíîãî ïîëíîãî ïîäãðàôàðàñêðàñèòüöâåòà22Cn .2Cn−Cp22Çíà÷èò, åñëè2222 Cnp 2Cn −Cp 6 2Cn ,(1)N (p) äîëæíî áûòü áîëüøå, ÷åì äàííîå n.p12 −1 íåðàâåíñòâî (1) âûïîëíÿåòñÿ.
Òîãäà ìû ïîëó÷èì óòâåðæäåíèåe p 2òåîðåìû. Äëÿ ýòîãî ñíà÷àëà ïî èíäóêöèè äîêàæåì ñëåäóþùåå íåðàâåíñòâîòî ñóùåñòâóåò "íå õîðîøàÿ" ðàñêðàñêà. Ñëåäîâàòåëüíî,Ïîêàæåì, ÷òî ïðèn = p peÏóñòü äëÿpâåðíî, äîêàæåì äëÿ p peÒ.å. îñòàëîñü ïîêàçàòü, ÷òîpp+1Ïîñëåäíåå íåðàâåíñòâî âåðíî, òàê êàên → ∞.(2)p + 1.(p + 1)! = (p + 1)p! > (p + 1)âîçðàñòàåò ïðè6 p!p+1 p p p e (p + 1)pp+1p= (p + 1)=ee e (p + 1)pep+1pe > 1 ⇐⇒ e >lim 1 +n→∞1 nn11+pp= e, à ïîñëåäîâàòåëüíîñòü 1 +Âåðíåìñÿ ê äîêàçàòåëüñòâó òåîðåìû.Cnp =n!np<, p > 2.(n − p)!p!p!181 nìîíîòîííînÈç (2) ñëåäóåò, ÷òîCnp pn<epp(3)Íåðàâåíñòâî (1) ðàâíîñèëüíî ñëåäóþùåìó2Cnp < 2Cp −1Ïîêàæåì òåïåðü, ÷òî ïðèn=1epp 2 2 −1(4)âûïîëíÿåòñÿ íåðàâåíñòâî p2nep 6 2Cp −1p(5)è òîãäà ïî íåðàâåíñòâó (3) áóäåò ñëåäîâàòü (4).(5) ⇐⇒ 2p22−pp1 p 2 2 −1e p26 2Cp −1 ⇐⇒ 2p22p−pep = 262p22p22−p−p2 −1⇐⇒ p >p+ 1 ⇔ p > 2.2Òåì ñàìûì òåîðåìà äîêàçàíà.Òåîðåìà.
(Ðàìñåÿ, ìíîãîöâåòíàÿ ðàñêðàñêà) ∀k > 2, ∀l1 , . . . , lk > r > 1 ñóùåñòâóåò íàèìåíüøåå N = N (l1 , . . . , lk , r) òàêîå, ÷òî ∀n > N è äëÿ ëþáîãî ðàçáèåíèÿ α1 , α2 , . . . , αk ìíîæåñòâàTr (X) ∃i : 1 6 i 6 k, ∃Ai ⊆ X òàêîå, ÷òî | Ai |= li è Tr (Ai ) ⊆ αi .Äîêàçàòåëüñòâî.Äîêàæåì äëÿÏðèìåíèì èíäóêöèþ ïîk . Áàçà k = 2.
Ïóñòü äëÿ âñåõ k 0 < kâñå äîêàçàíî.k.Nk (l1 , . . . , lk , r) 6 N = N (Nk−1 (l1 , . . . , lk−1 , r), lk , r).α1 , . . . , αk ñòðîèì ðàçáèåíèå α, β ìíîæåñòâà Tr (X) ñëåäóþùèì îáðàçîì, β = αk , α =α1 ∪ . . . ∪ αk−1 . Ïî ïðåäûäóùåé òåîðåìå Ðàìñåÿ ìîæåò áûòü äâà ñëó÷àÿ.1) ∃A ⊆ X òàêîå, ÷òî | A |= Nk−1 (l1 , . . . , lk−1 , r) è Tr (A) ⊆ α.2) ∃B ⊆ X òàêîå, ÷òî | B |= lk è Tr (B) ⊆ β.Âî âòîðîì ñëó÷àå i = k , Ak = B .  ïåðâîì ïîëüçóåìñÿ ïðåäïîëîæåíèåì èíäóêöèè. ÒåîðåìàÏî ðàçáèåíèþäîêàçàíà.Òåîðåìà.
(Øóðà) ∀k > 1 ∃R = R(k) òàêîå, ÷òî ∀n > R è äëÿ ëþáîãî îòîáðàæåíèÿ φ,φ : {1, . . . , n} −→ {c1 , . . . , cn }, íàéäåòñÿ îäíîöâåòíîå ðåøåíèå óðàâíåíèÿ x + y = z.R(k) = Nk (3, 3, 2) è n > R(k). Ïîñòðîèì îòîáðàæåíèå φ∗ : T2 −→{c1 , . . . , ck }. ñëåäóþùèì îáðàçîì. Åñëè (i, j) ∈ T2 (X), i 6= j, òî φ∗ (i, j) = = φ(|i − j|). Ïî òåîðåìåÐàìñåÿ ñóùåñòâóåò îäíîöâåòíûé òðåóãîëüíèê ∆ = {i, j, k}. Ïóñòü, äëÿ îïðåäåëåííîñòè, i < j < k.Äîêàçàòåëüñòâî.ÏóñòüÒîãäàφ∗ (i, j) = φ∗ (i, k) = φ∗ (j, k).Íî ýòî ðàâåíñòâî ðàâíîñèëüíî ñëåäóþùåìóφ(j − i) = φ(k − i) = φ(k − j).Ïîýòîìó, åñëè îáîçíà÷èòüóðàâíåíèÿx + y = z.x = j − i, y = k − j, z = k − i,òî ìû íàøëè îäíîöâåòíîå ðåøåíèåÒåîðåìà äîêàçàíà.Òåîðåìà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
