Todiste siitä, ettei suurinta alkukappaletta ole

Tällä viikolla jatkamme matemaattisten todistusten parissa. Tänään käsittelemme yleistä todistusta, jossa todistamme, ettei suurinta alkulukua ole olemassa. Kuten tavallista, tavoitteenani on selittää todistukset mahdollisimman yksinkertaisella kielellä ja välttää vaikeita matemaattisia merkintöjä. Ennen kuin kuitenkin pääsemme siihen, esittelen tavanomaisen viikoittaisen logiikkapulman.

Logiikkapulma

Olet 106-kerroksisessa rakennuksessa. Kerrokset on numeroitu 0–105 (kuten suurimmassa osassa maailmaa kerroksia on numeroitu Yhdysvaltojen ulkopuolella). Haluat testata, mistä ylimmästä kerroksesta voit turvallisesti pudottaa munan maahan suureen höyhenlaatikkoon. Tiedät, että katolta pudotettu muna rikkoutuu ja kerroksesta 0 pudotettu muna selviää hengissä. Sinulla on kaksi munaa kokeiltavana. Mikä on vähiten pudotuksia, joita tarvitset pahimmassa tapauksessa?

Vastaus ja ratkaisu näkyvät sarakkeen lopussa.

Todiste siitä, ettei suurinta alkukappaletta ole

Todistan ristiriidan avulla, ettei suurinta alkulukua ole olemassa. Toisin sanoen, todistan päinvastaisen väitteen – että suurin alkuluku on olemassa.

Kutsutaan suurinta alkulukua p _n: ksi, eli se on n:s alkuluku. Merkitään kaikki alkuluvut järjestyksessä seuraavasti:

_p1 = 2, _p2 = 3, _p3 = 5, _p4 = 7, … _pn =?

Tarkastellaan lukua N seuraavasti:

N = _p1 × _p2 × _p3 × _p4 × … × _pn +1.

Jos N on alkuluku, mikään pienempi alkuluku ei saisi jakautua siihen tasan. Jos kuitenkin jaamme minkä tahansa alkuluvun p _:hen asti siihen, saamme jakojäännöksen 1.Tuon voi selittää vain kahdella mahdollisella tavalla:

1. N itse on alkuluku, minkä täytyy olla suurempi kuin p _/n .
2. On olemassa jokin p _n: ää suurempi alkuluku, joka jakautuu tasan N:ään.

Joka tapauksessa olemme osoittaneet, että on olemassa suurempi alkuluku kuin p _n .

Tarkastellaan esimerkiksi pientä alkulukua. Katsotaanpa, mitä tapahtuu, jos oletamme, että 31 on suurin alkuluku. Tässä tapauksessa:

N = 2 × 3 × 5 × 7 × 11 × 13 × 17 × 19 × 23 × 29 × 31 + 1 = 1 805 044 411 171

Alkulukulaskurilla löydämme 1 805 044 411 171 = 1 061 729 x 1 700 099. Olemme siis löytäneet kaksi suurempaa alkulukua kuin 31: 1 061 729 ja 1 700 099.

Toisen esimerkin saamiseksi oletetaan, että 7 on suurin alkuluku. Tällöin N = 2 × 3 × 5 × 7 + 1 = 211. Suorittamalla alkulukutekijöihinjakotestin luvulle 211, huomaamme, että 211 on alkuluku. Näin ollen löysimme suuremman alkuluvun kuin 7.

Riippumatta siitä, minkä alkuluvun oletamme olevan suurin, tämä menetelmä löytää suuremman.

Vastaus logiikkapulmaan

14

Näin löydät korkeimman turvallisen kerroksen enintään 14 pudotuksella.

1. Pudota ensimmäinen muna 14. kerroksesta. Jos se rikkoutuu, testaa kerroksia 1–13 yksi kerrallaan. Jos se rikkoutuu, pudotusten enimmäismäärä on 14 (1 ensimmäisen munan kanssa ja 13 toisen kanssa). Muussa tapauksessa siirry vaiheeseen 2.
2. Mene ylös 13 kerrosta ja pudota ensimmäinen muna 27. kerroksesta. Jos se rikkoutuu, testaa kerroksia 15–26 yksi kerrallaan. Jos se rikkoutuu, pudotusten enimmäismäärä on 14 (2 ensimmäisen munan kanssa ja enintään 12 toisen kanssa). Muussa tapauksessa siirry vaiheeseen 3.
3. Mene ylös 12 kerrosta ja pudota ensimmäinen muna 39. kerroksesta. Jos se rikkoutuu, testaa kerroksia 28–38 yksi kerrallaan. Jos se rikkoutuu, pudotusten enimmäismäärä on 14 (3 ensimmäisen munan kanssa ja enintään 11 toisen kanssa). Muussa tapauksessa siirry vaiheeseen 4.
4. Mene ylös 11 kerrosta ja pudota ensimmäinen muna 50. kerroksesta. Jos se rikkoutuu, testaa kerroksia 40–49 yksi kerrallaan. Jos se rikkoutuu, pudotusten enimmäismäärä on 14 (4 ensimmäisen munan kanssa ja enintään 10 toisen kanssa). Muussa tapauksessa siirry vaiheeseen 5.
5. Mene 10 kerrosta ylös ja pudota ensimmäinen muna 60. kerroksesta. Jos se rikkoutuu, testaa kerrokset 51–59 yksi kerrallaan.Tarvittavien pudotusten enimmäismäärä rikkoutuessa = 14 (5 ensimmäisen munan kanssa ja enintään 9 toisen kanssa). Muussa tapauksessa siirry vaiheeseen 6.
6. Mene ylös 9 kerrosta ja pudota ensimmäinen muna 69. kerroksesta. Jos se rikkoutuu, testaa kerroksia 61–68 yksi kerrallaan. Jos se rikkoutuu, pudotusten enimmäismäärä on 14 (6 ensimmäisen munan kanssa ja enintään 8 toisen kanssa). Muussa tapauksessa siirry vaiheeseen 7.
7. Mene ylös 8 kerrosta ja pudota ensimmäinen muna 77. kerroksesta. Jos se rikkoutuu, testaa kerroksia 70–76 yksi kerrallaan. Jos se rikkoutuu, pudotusten enimmäismäärä on 14 (7 ensimmäisen munan kanssa ja enintään 7 toisen kanssa). Muussa tapauksessa siirry vaiheeseen 8.
8. Mene ylös 7 kerrosta ja pudota ensimmäinen muna 84. kerroksesta. Jos se rikkoutuu, testaa kerroksia 78–83 yksi kerrallaan. Jos se rikkoutuu, pudotusten enimmäismäärä on 14 (8 ensimmäisen munan kanssa ja enintään 6 toisen kanssa). Muussa tapauksessa siirry vaiheeseen 9.
9. Mene ylös 6 kerrosta ja pudota ensimmäinen muna 90. kerroksesta. Jos se rikkoutuu, testaa kerroksia 85–89 yksi kerrallaan. Jos se rikkoutuu, pudotusten enimmäismäärä on 14 (9 ensimmäisen munan kanssa ja enintään 5 toisen kanssa). Muussa tapauksessa siirry vaiheeseen 10.
10. Mene viisi kerrosta ylös ja pudota ensimmäinen muna kerroksesta 95. Jos se rikkoutuu, testaa kerroksia 91–94 yksi kerrallaan. Jos se rikkoutuu, pudotusten enimmäismäärä on 14 (10 ensimmäisen munan kanssa ja enintään 4 toisen kanssa). Muussa tapauksessa siirry vaiheeseen 11.
11. Mene neljä kerrosta ylös ja pudota ensimmäinen muna 99. kerroksesta. Jos se rikkoutuu, testaa kerroksia 96–98 yksi kerrallaan. Jos se rikkoutuu, pudotusten enimmäismäärä on 14 (11 ensimmäisen munan kanssa ja enintään 3 toisen kanssa). Muussa tapauksessa siirry vaiheeseen 12.
12. Mene kolme kerrosta ylös ja pudota ensimmäinen muna 102. kerroksesta. Jos se rikkoutuu, testaa kerroksia 100 ja 101 yksi kerrallaan. Jos se rikkoutuu, pudotusten enimmäismäärä on 14 (12 ensimmäisen munan kanssa ja enintään 2 toisen kanssa). Muussa tapauksessa siirry vaiheeseen 13.
13. Mene kaksi kerrosta ylös ja pudota ensimmäinen muna kerroksesta 104. Jos se rikkoutuu, testaa kerrosta 103. Jos se rikkoutuu, pudotusten enimmäismäärä on 14 (13 ensimmäisen munan kanssa ja 1 toisen kanssa). Muussa tapauksessa siirry vaiheeseen 14.
14. Mene yksi kerros ylös ja pudota ensimmäinen muna kerroksesta 105. Jos se rikkoutuu, ylin turvallinen kerros on 104. Jos se selviää, ylin turvallinen kerros on 105.

N-kerroksisen rakennuksen yleinen strategia on löytää optimaalinen kerros ensimmäiselle pudotukselle. Jos ensimmäinen testi läpäisee, siitä noustaan sama määrä kerroksia miinus yksi. Jos toinen testi läpäisee, noustaan taas yksi kerros vähemmän kuin viimeksi. Toista tätä ja noustaan yksi kerros vähemmän kuin edellisessä pudotuksessa. Jos ensimmäisellä pudotusmunalla tehty testi epäonnistuu, testataan toisella pudotusmunalla systemaattisesti jokainen kerros kahden viimeisen testin välillä alkaen alimmasta kerroksesta.

Huomaa, että kerrosten lukumäärä kasvaa n, n-1, n-2, ... 1. Kaikkien näiden hyppyjen summa on n(n+1)/2. Ratkaisu on löytää pienin mahdollinen n:n kokonaislukuarvo, jossa sarjan summa on yhtä suuri tai suurempi kuin rakennuksen kerrosten lukumäärä.

Tarkastellaan esimerkiksi 500-kerroksista rakennusta (lukuun ottamatta turvallista pohjakerrosta) ja ratkaistaan:

n(n+1)/2 = 500

n(n+1) = 1000

^n² + n-1000 = 0

6; font-family: 'Open Sans', sans-serif; color: #313131 !important; ">Käyttäen Pythagoraan kaavaa:

n = (-1 +/- √4001 )/2 = ~ 31,13

Kerroksilla on kuitenkin kokonaislukuarvoja. Joten pyöristämme ylöspäin lukuun n=32. Näin ollen 500-kerroksisen rakennuksen tapauksessa (tai 501, jos lasketaan mukaan turvallinen pohjakerros) teemme ensimmäisen testin kerroksesta 32.