Дискретная математика

1 1.1 Ââåäåíèå Î ïðåäìåòå è ñîäåðæàíèè êóðñà Ñëîâî "äèñêðåòíûé" ÿâëÿåòñÿ ïðîòèâîïîëîæíûì ïî çíà÷åíèþ ñëîâó "íåïðeðûâíûé", à íåïðåðûâíûìè ìîãóò áûòü òîëüêî áåñêîíå÷íûå îáðàçîâàíèÿ. Äèñêðåòíàÿ ìàòåìàòèêà èìååò äåëî ñ êîíå÷íûìè îáúåêòàìè: êîíå÷íûìè ìíîæåñòâàìè è èõ ïðåîáðàçîâàíèÿìè (ôóíêöèÿìè, îïðåäåëåííûìè íà êîíå÷íûõ ìíîæåñòâàõ è ïðèíèìàþùèìè êîíå÷íûå ìíîæåñòâà çíà÷åíèé). Ýëåìåíòû êîíå÷íûõ ìíîæåñòâ ìîæíî îáîçíà÷àòü öåëûìè ÷èñëàìè, ïîýòîìó ìîæíî ñêàçàòü, ÷òî äèñêðåòíàÿ ìàòåìàòèêà îïåðèðóåò öåëûìè ÷èñëàìè, ðåçóëüòàòû âñåõ âû÷èñëåíèé  öåëûå ÷èñëà. Èñòîðè÷åñêè íåîòðèöàòåëüíûå öåëûå ÷èñëà ïîÿâèëèñü ðàíüøå âñåõ îñòàëüíûõ, îíè âûðàæàþò êîëè÷åñòâî ýëåìåíòîâ ìíîæåñòâà. Òàê ïðèøëè ê ïîíÿòèþ íàòóðàëüíîãî ÷èñëà äðåâíèå ëþäè, òàê ó÷àò ìàëåíüêèõ äåòåé, ïîêàçûâàÿ è ñðàâíèâàÿ ìíîæåñòâà ñíà÷àëà îäèíàêîâûõ ïðåäìåòîâ (ïàëî÷åê, êóáèêîâ, øàðèêîâ), à çàòåì è ðàçíîðîäíûõ. Ïîçæå ïîíÿòèå ÷èñëà ðàñøèðÿåòñÿ â ñâÿçè ñ ïðàêòè÷åñêèìè äåéñòâèÿìè  ñ÷åòîì, àðèôìåòè÷åñêèìè îïåðàöèÿìè è îáðàòíûìè ê íèì. ×èñëî 0 íå èçìåíÿåò èñõîäíîå ïðè ñëîæåíèè, îòðèöàòåëüíûå ÷èñëà ïîÿâëÿþòñÿ ïðè âûïîëíåíèè âû÷èòàíèÿ, äåéñòâèÿ, îáðàòíîãî ñëîæåíèþ. Ðàöèîíàëüíûå ÷èñëà  ðåçóëüòàò äåëåíèÿ, äåéñòâèÿ, îáðàòíîãî óìíîæåíèþ. Èððàöèîíàëüíûå è êîìïëåêñíûå ÷èñëà  ðåçóëüòàò èçâëå÷åíèÿ êîðíåé, äåéñòâèé, îáðàòíûõ âîçâåäåíèþ â ñòåïåíü. Äàæå øêîëüíèêè ìîãóò óáåäèòüñÿ, ÷òî çàäà÷è ñ öåëî÷èñëåííûì ïî ñìûñëó ðåçóëüòàòîì äîâîëüíî ñèëüíî îòëè÷àþòñÿ îò àíàëîãè÷íûõ çàäà÷ áåç òàêîãî îãðàíè÷åíèÿ: óðàâíåíèÿ, íåðàâåíñòâà è èõ ñèñòåìû ìîãóò íå èìåòü ðåøåíèÿ è, íàïðîòèâ, ðåøåíèå âñåãî ëèøü îäíîãî óðàâíåíèÿ ñ íåñêîëüêèìè íåèçâåñòíûìè ìîæåò áûòü åäèíñòâåííûì.  äèñêðåòíîé ìàòåìàòèêå, â ñèëó êîíå÷íîñòè ðàññìàòðèâàåìûõ ìíîæåñòâ, íåâîçìîæåí ïðåäåëüíûé ïåðåõîä è, ñëåäîâàòåëüíî, íåïðèìåíèìû îñíîâàííûå íà ïîíÿòèè ïðåäåëà ìåòîäû äèôôåðåíöèàëüíîãî è èíòåãðàëüíîãî èñ÷èñëåíèÿ. Íåîáõîäèìû èíûå ïîäõîäû, îáóñëîâëåííûå ñïåöèôèêîé äèñêðåòíûõ çàäà÷, è ñèñòåìàòèçàöèÿ èõ â îñîáîì ðàçäåëå ìàòåìàòèêè.  ÕÕ âåêå äèñêðåòíàÿ ìàòåìàòèêà ïîëó÷èëà äîïîëíèòåëüíûé ñòèìóë ê ðàçâèòèþ â ñâÿçè ñ ïîÿâëåíèåì è øèðîêèì ïðèìåíåíèåì öèôðîâîé òåõíèêè. Ëþáîå òàêîå óñòðîéñòâî êîíå÷íî, è â íåì öèôðàìè ìîæíî ïðåäñòàâèòü ëèøü êîíå÷íîå ìíîæåñòâî ÷èñåë, êàê áû âåëèêî îíî íè áûëî. Ýòèì ñõîæè è ïðîñòåéøèé äðåâíèé âû÷èñëèòåëüíûé èíñòðóìåíò àáàê (ñ÷åòû), è ñîâðåìåííûé ñóïåðêîìïüþòåð. Îäíàêî íå ñëåäóåò ïðîòèâîïîñòàâëÿòü äèñêðåòíóþ è íåïðåðûâíóþ ìàòåìàòèêó. Îíè, êàê áóäåò âèäíî, íàõîäÿòñÿ â òåñíîé âçàèìîñâÿçè, ìåòîäû îäíîé ïðèìåíÿþòñÿ êàê èíñòðóìåíò â äðóãîé, èõ òðóäíî ðàçäåëèòü. Îâëàäåíèå è äèñêðåòíûìè, è íåïðåðûâíûì ìåòîäàìè íåîáõîäèìî äëÿ âûðàáîòêè ìàòåìàòè÷åñêîé êóëüòóðû 1 è óñïåøíîãî ïðèìåíåíèÿ ìàòåìàòèêè â ëþáîé ñôåðå äåÿòåëüíîñòè. Èçëàãàåìûé çäåñü êóðñ ñîñòîèò èç òðåõ ÷àñòåé. Ïåðâàÿ ÷àñòü  ýòî ìåòîäû êîìáèíàòîðíûõ âû÷èñëåíèé, ïîäñ÷åòà ðàçëè÷íûõ êîíå÷íûõ îáúåêòîâ. Âòîðàÿ ÷àñòü  ìîäåëè è ìåòîäû òåîðèè ãðàôîâ, ñîâðåìåííîãî ðàçäåëà ìàòåìàòèêè, ïîçâîëÿþùåãî àíàëèçèðîâàòü âñåâîçìîæíûå îòíîøåíèÿ ìåæäó ïàðîé ýëåìåíòîâ êîíå÷íîãî ìíîæåñòâà. Òåîðèÿ ãðàôîâ îáëàäàåò áîëüøîé ñòåïåíüþ óíèâåðñàëüíîñòè, êðàñîòîé è íàãëÿäíîñòüþ, ïîçâîëÿþùåé ñ÷èòàòü åå àíàëîãîì ãåîìåòðèè ïðè êîíå÷íîì ìíîæåñòâå òî÷åê. Òðåòüÿ, çàêëþ÷èòåëüíàÿ ÷àñòü  öåëî÷èñëåííàÿ àðèôìåòèêà, îíà îáëàäàåò, êàê óæå ãîâîðèëîñü, óäèâèòåëüíûìè (íà ïåðâûé âçãëÿä) îñîáåííîñòÿìè, ïîçâîëÿþùèìè â ðÿäå ñëó÷àåâ çíà÷èòåëüíî ñîêðàòèòü îáúåì âû÷èñëåíèé è èçáåæàòü îøèáîê. Ðåçóëüòàòû ïåðâîé ÷àñòè ñóùåñòâåííî èñïîëüçóþòñÿ â ïîñëåäóþùèõ. 1.2 Ðåêîìåíäóåìàÿ ëèòåðàòóðà 1. Íàáåáèí À. À. Äèñêðåòíàÿ ìàòåìàòèêà  Ì.: Íàó÷íûé ìèð, 2010. 2. Èâàíîâ Á. Í. Äèñêðåòíàÿ ìàòåìàòèêà. Àëãîðèòìû è ïðîãðàììû  Ì.: Ëàá. áàç. çíàíèé, 2002. 3. Íàáåáèí À. À. Ñáîðíèê çàäàíèé ïî äèñêðåòíîé ìàòåìàòèêå  Ì.: Íàó÷íûé ìèð, 2009. Íè îäíà èç êíèã íå ÿâëÿåòñÿ îáÿçàòåëüíîé. Äëÿ îâëàäåíèÿ êóðñîì è óñïåøíîãî âûïîëíåíèÿ çàäàíèé äîñòàòî÷íî ïóáëèêóåìîãî çäåñü ìàòåðèàëà. Íî ïîëåçíî çíàòü, ÷òî òàêèå êíèãè åñòü, êàê è ìíîæåñòâî äðóãèõ, â çàãëàâèè êîòîðûõ ïðèñóòñòâóþò ñëîâà "äèñêðåòíàÿ ìàòåìàòèêà". 1.3 Ïðèìåíÿåìûå îáîçíà÷åíèÿ N = {1, 2, . . .}  ìíîæåñòâî íàòóðàëüíûõ ÷èñåë. Z = {0, ±1, ±2, . . .}  ìíîæåñòâî öåëûõ ÷èñåë. Z+ = {0, 1, 2, . . .}  ìíîæåñòâî íåîòðèöàòåëüíûõ öåëûõ ÷èñåë. R = (−∞; +∞)  ìíîæåñòâî âåùåñòâåííûõ ÷èñåë. C = {z = x + iy, x, y ∈ R}  ìíîæåñòâî êîìïëåêñíûõ ÷èñåë, ãäå i  ìíèìàÿ åäèíèöà, i2 = −1. bxc  öåëàÿ ÷àñòü âåùåñòâåííîão x, íàèáîëüøåå öåëîå, íå ïðåâîñõîäÿùåå x. dxe äëÿ âåùåñòâåííîãî ÷èñëà x  íàèìåíüøåå öåëîå M òàêîå, ÷òî M ≥ x.  îçíà÷àåò êîíåö äîêàçàòåëüñòâà, "òðåáóåìîå ïîëó÷åíî", "òåîðåìà äîêàçàíà". 2 2 Âû÷èñëåíèå êîíå÷íûõ ñóìì  çàäà÷àõ äèñêðåòíîé ìàòåìàòèêè ïðèõîäèòñÿ äîâîëüíî ÷àñòî âûïîëíÿòü íåêîòîðûå ñòàíäàðòíûå âû÷èñëåíèÿ. Ðàññìîòðèì ìåòîäû âû÷èñëåíèÿ ñóìì, çàâèñÿùèõ îò íåñêîëüêèõ ïàðàìåòðîâ, îäíèì èç ïàðàìåòðîâ âñåãäà ÿâëÿåòñÿ ÷èñëî ñëàãàåìûõ. Ýòèìè íåñëîæíûìè òåõíè÷åñêèìè ïðèåìàìè íåîáõîäèìî îâëàäåòü äëÿ óñïåøíîãî ðåøåíèÿ áîëåå ñëîæíûõ è ñîäåðæàòåëüíûõ çàäà÷. Îòìåòèì, ÷òî ïðèíöèïèàëüíûì îòëè÷èåì ýòèõ âû÷èñëåíèé îò ñóììèðîâàíèÿ ðÿäîâ ìåòîäàìè âûñøåé ìàòåìàòèêè (òî÷íåå, ìàòåìàòè÷åñêîãî àíàëèçà) ÿâëÿåòñÿ êîíå÷íîñòü ÷èñëà ñëàãàåìûõ è íåâîçìîæíîñòü ïðåäåëüíîãî ïåðåõîäà.  ìàòåìàòè÷åñêîì àíàëèçå òàêèå ñèòóàöèè ÷àñòî ïðèâîäÿò ê ïðèáëèæåííîìó ðåçóëüòàòó (ïîãðåøíîñòü êîòîðîãî ìîæíî, òåì íå ìåíåå, îöåíèòü). Ìû æå áóäåì èñêàòü òî÷íûå çíà÷åíèÿ ñóìì íàòóðàëüíûõ ÷èñåë. Íàïîìíèì, ÷òî ðåçóëüòàòîì âñåãäà äîëæíî áûòü öåëîå ÷èñëî. Ðàññìîòðèì äîâîëüíî îáùåå ñåìåéñòâî ñóìì Sn (k) = n X j k = 1k + 2k + · · · + nk , (1) j=1 çàâèñÿùèõ îò äâóõ öåëî÷èñëåííûõ ïàðàìåòðîâ n ≥ 1 è k ≥ 0. 1.1 Ïðè k = 0 áåç òðóäà íàõîäèì Sn (0) = n X j = j=1 n X 1 = n, j=1 Sn (0) = n. (1.1) 1.2. Ïðè k = 1 çàïèøåì ñóììó Sn (1) â ïðÿìîì è îáðàòíîì ïîðÿäêå: Sn (1) = 1 + 2 + 3 + · · · + (n − 2) + (n − 1) + n, Sn (1) = n + (n − 1) + (n − 2) + · · · + 3 + 2 + 1. Ñëîæèâ ýòè ðàâåíñòâà, ïîëó÷èì 2Sn (1) = (1 + n) + (2 + n − 1) + (3 + n − 2) + · · · + (n − 2 + 3) + (n − 1 + 2) + (n + 1).  ïðàâîé ÷àñòè òåïåðü ñóììà n îäèíàêîâûõ ñëàãàåìûõ (n + 1), îòêóäà Sn (1) = n(n + 1) . 2 (1.2) Âåëèêèé íåìåöêèé ìàòåìàòèê Êàðë Ôðèäðèõ Ãàóññ (17771855) ïðèäóìàë òàêîé ñïîñîá âû÷èñëåíèÿ ýòîé ñóììû â 7-ëåòíåì âîçðàñòå. 3 Ðàññìîòðèì èíîé ñïîñîá. Îí èñïîëüçóåò ñóììó Sn+1 (2). Ñ îäíîé ñòîðîíû, Sn+1 (2) = Sn (2) + (n + 1)2 = Sn (2) + n2 + 2n + 1. Ñ äðóãîé ñòîðîíû, Sn+1 (2) = n X 2 (j + 1) = j=0 n X (j 2 + 2j + 1) = Sn (2) + 2Sn (1) + (n + 1). j=0 Òàêèì îáðàçîì, Sn (2) + n2 + 2n + 1 = Sn (2) + 2Sn (1) + n + 1, îòêóäà ïîñëå ýëåìåíòàðíûõ ïðåîáðàçîâàíèé 2Sn (1) = n2 + n. Ïîëó÷àåì òîò æå ðåçóëüòàò (1.2). Ïðè ëþáîì íàòóðàëüíîì n ïðîèçâåäåíèå n(n + 1) ÷åòíî, ïîýòîìó Sn (1) öåëîå. Âòîðîé ñïîñîá ìîæíî ìîäèôèöèðîâàòü äëÿ âû÷èñëåíèÿ, êàê ìû ïîêàæåì, è áîëåå ñëîæíûõ ñóìì. 1.3 (ñóììà ïåðâûõ n ÷ëåíîâ àðèôìåòè÷åñêîé ïðîãðåññèè a1 , a2 = a1 +d, a3 = a1 + 2d, . . . ñ ðàçíîñòüþ d) An (d) = n X j=1 aj = n X (a1 + (j − 1)d). j=1 Ïðåîáðàçóÿ ñóììó è èñïîëüçóÿ (1.2), ïîëó÷àåì An (d) = na1 + d(1 + 2 + · · · + n − 1) = na1 + d(n − 1)n/2. Ýëåìåíòàðíûìè ïðåîáðàçîâàíèÿìè ïðèõîäèì ê èçâåñòíûì ñî øêîëû ôîðìóëàì An (d) = n(2a1 + (n − 1)d) n(a1 + an ) = . 2 2 (1.3) 1.4. Âû÷èñëèì Sn (2) ñïîñîáîì, àíàëîãè÷íûì âòîðîìó ìåòîäó âû÷èñëåíèÿ ñóììû Sn (1). Èìååì Sn+1 (3) = Sn (3) + (n + 1)3 = Sn (3) + n3 + 3n2 + 3n + 1. Ñ äðóãîé ñòîðîíû, Sn+1 (3) = n X 3 (j + 1) = j=0 n X (j 3 + 3j 2 + 3j + 1) = Sn (3) + 3Sn (2) + 3Sn (1) + (n + 1). j=0 Òàêèì îáðàçîì, Sn (3) + n3 + 3n2 + 3n + 1 = Sn (3) + 3Sn (2) + 3Sn (1) + n + 1. 4 Ñ ó÷åòîì (1.2) ïîëó÷àåì n3 + 3n2 + 3n = 3Sn (2) + 3n(n + 1)/2 + n, . n(n + 1)(2n + 1) . (1.4) 6 Óáåäèìñÿ, ÷òî âûðàæåíèå èç ïðàâîé ÷àñòè (1.4) öåëîå. Èç äâóõ ïîñëåäîâàòåëüíûõ ÷èñåë ðîâíî îäíî ÷åòíî, ïîýòîìó ÷èñëèòåëü äðîáè äåëèòñÿ íà 2. Ïðîâåðèòü, ÷òî îí äåëèòñÿ è íà 3 (ñëåäîâàòåëüíî, íà 6 = 2 · 3) ìîæíî, ðàññìîòðåâ âîçìîæíûå îñòàòêè îò äåëåíèÿ íà 3 ÷èñëà n (ñëó÷àè n = 3m, 3m + 1, 3m + 2, ãäå m ∈ Z ). Ñäåëàéòå ýòî ñàìîñòîÿòåëüíî. 1.5. Àíàëîãè÷íî âû÷èñëèì Sn (3). Èç âûðàæåíèé Sn (2) = Sn+1 (4) = Sn (4) + (n + 1)4 = Sn (4) + n4 + 4n3 + 6n2 + 4n + 1, Sn+1 (4) = n X 4 (j + 1) = j=0 n X (j 4 + 4j 3 + 6j 2 + 4j + 1) = j=0 = Sn (4) + 4Sn (3) + 6Sn (2) + 4Sn (1) + (n + 1) ñëåäóåò ðàâåíñòâî Sn (4) + n4 + 4n3 + 6n2 + 4n + 1 = Sn (4) + 4Sn (3) + 6Sn (2) + 4Sn (1) + n + 1. Ïîäñòàâëÿÿ â íåãî (1.1), (1.2), (1.4), ïîëó÷èì n4 + 4n3 + 6n2 + 4n = 4Sn (3) + n(n + 1)(2n + 1) + 2n(n + 1) + n, îòêóäà 4Sn (3) = n4 + 2n3 + n2 è, íàêîíåö, n2 (n + 1)2 Sn (3) = . 4 (1.5) 1.6. Òàêèì æå ïóòåì ïîñëåäîâàòåëüíî âû÷èñëÿþòñÿ ñóììû Sn (4), Sn (5), . . ..  ÷àñòíîñòè, Sn (4) = n X j=1 j4 = n(6n4 + 15n3 + 10n2 − 1) . 30 Âûâåäèòå ýòó ôîðìóëó ñàìîñòîÿòåëüíî. 1.7. Çíàÿ Sn (0), Sn (1), Sn (2), . . . , Sn (m) è èñïîëüçóÿ ñâîéñòâî ëèíåéíîñòè ñóìì, ìîæíî âû÷èñëèòü ñóììó ìíîãî÷ëåíîâ còåïåíè m, çàâèñÿùèõ îò j : n X (am j m + am−1 j m−1 + · · · + a1 j + a0 ) = j=1 5 = am Sn (m) + am−1 Sn (m − 1) + · · · a1 Sn (1) + a0 Sn (0). 1.8. Ê òàêèì ïîëèíîìàì îòíîñÿòñÿ è ÷àñòî âñòðå÷àåìûå ñóììû âèäà SSn (k) = n X j(j + 1) · · · (j + k − 1). j=1 Äëÿ k = 2, 3 èìååì: SSn (2) = 1 · 2 + 2 · 3 + · · · + n(n + 1) = = 1 · (1 + 1) + 2(2 + 1) + · · · + n(n + 1) = = (12 + 22 + · · · + n2 ) + (1 + 2 + · · · + n) = Sn (2) + Sn (1) = = n(n + 1)(2n + 1) n(n + 1) + , 6 2 SSn (3) = 1 · 2 · 3 + 2 · 3 · 4 + · · · + n(n + 1)(n + 2) = n n X X = j(j + 1)(j + 2) = (j 3 + 3j 2 + 2j) = S3 (n) + 3Sn (2) + 2Sn (1). j=1 2. j=1 Ñóììà ïåðâûõ ÷ëåíîâ ãåîìåòðè÷åñêîé ïðîãðåññèè ñî çíàìåíàòe- ëåì q Gn (q) = 1 + q + q 2 + · · · + q n âû÷èñëÿåòñÿ ïî ñëåäóþùèì ôîðìóëàì: Gn (1) = n + 1, Gn (−1) = 0 ïðè ÷åòíûõ n, Gn (−1) = 1 ïðè íå÷åòíûõ n, q n+1 − 1 Gn (q) = ïðè |q| = 6 1. q−1 Ïðèìåð. Âîò ñîäåðæàòåëüíàÿ çàäà÷à, â êîòîðîé èñïîëüçóåòñÿ ñóììà Gn (q). Êàêîâî êîëè÷åñòâî äåñÿòè÷íûõ öåëûõ ÷èñåë îò 0 äî 10n , íå ñîäåðæàùèõ íàõîäÿùèõñÿ ðÿäîì îäèíàêîâûõ öèôð? Îáîçíà÷èì èñêîìóþ âåëè÷èíó êàê xn . Ëåãêî íàéòè x1 = 10, x2 = 100 − 9 = 91. Ïóñòü íàéäåíî ÷èñëî xn . Òîãäà xn+1 = xn + ∆n+1 , ãäå ∆n+1  êîëè÷åñòâî ÷èñåë, ñîäåðæàùèõ ðîâíî n + 1 öèôð d1 , d2 , . . . , dn+1 , ïðè ýòîì d1 6= 0, ò. å. d1 ìîæåò ïðèíèìàòü ëþáîå èç 9 çíà÷åíèé 1, . . . , 9. Òîãäà è äëÿ êàæäîãî j = 2, . . . , n + 1 öèôðà dj ìîæåò ïðèíèìàòü ëþáîå èç 9 çíà÷åíèé, ïðèíàäëåæàùèõ ìíîæåñòâó {0, 1, . . . , 9} \ {dj−1 }. Âñå n + 1 öèôð ìîãóò ïðèíèìàòü, òàêèì îáðàçîì, 9n+1 6 çíà÷åíèé (ýòî ÷àñòíûé ñëó÷àé îáùåãî ïðàâèëà ïðîèçâåäåíèÿ, ÷àñòî èñïîëüçóåìîãî â ðàçëè÷íûõ çàäà÷àõ äèñêðåòíîé ìàòåìàòèêè). Ñëåäîâàòåëüíî, ∆n+1 = 9n+1 , xn+1 = xn + 9n+1 , 9n+1 − 1 xn = 10 + 9 + 9 + · · · + 9 = Gn (9) = . 8 2 3 n Ìàòåðèàë ýòîãî ðàçäåëà âçÿò âî ìíîãîì èç êíèãè Ãðýõåì Ð., Êðóò Ä., Ïàòàøíèê Î. Êîíêðåòíàÿ ìàòåìàòèêà. Îñíîâàíèå èíôîðìàòèêè.  Ì.: Ìèð, 1998, ãë. 2. (R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics. A Foundation for Computer Science. The 2-nd Ed., AddisonWesley, 1994.) Äàëåå ÒÅÑÒ 1. 7