Arhivi avtorja: AndrejJ
Desmos
Goldbachova domneva in nemogoči problem
Ivan Vidav: Teorija števil in elementarna geometrija
Članek z naslovom O nerešljivem problemu je izšel v časopisu Obzornik za matematiko in fiziko 29, 1982, str. 101-102.
Naravno število je praštevilo, če je večje od 1 in je deljivo le z 1 in s samim seboj. Najmanjše praštevilo je 2 in je edino sodo, vsa druga so liha: 3, 5, 7, 11, 13, … Vemo, da se dá vsako naravno število, ki je > 1 in ni praštevilo, razstaviti v produkt samih praštevil. Ali se dá zapisati tudi kot vsota praštevil? Prav gotovo, če se ne oziramo na število sumandov. Sodo število je na primer vsota samih dvojk. Zgled:
100 = 2 + 2 + 2 + … + 2.
Tu je na desni kar 50 sumandov. Število 100 pa lahko izrazimo tudi takole:
100 = 3 + 97 = 11 + 89 = 17 + 83 = 29 + 71 = 41 + 59 = 47 + 53 .
Vsi sumandi na desni so praštevila. Torej se dá 100 zapisati kot vsota dveh praštevil, in sicer kar na šest načinov. Poglejmo, kako je pri najmanjših sodih številih:
4 = 2+2, 6 = 3+3, 8 = 3+5, 10 = 3+7 = 5+5.
Kaj hitro se prepričamo tudi o nadaljnjih ne prevelikih sodih številih 12, 14, 16, 18, … , da se izražajo kot vsote dveh praštevil. Zato se nam upravičeno vsiljuje tale
DOMNEVA. Vsako sodo število >= 4 se da zapisati vsaj na en način kot vsota dveh praštevil.
Prvi je to domnevo izrazil C. Goldbach leta 1742 v nekem pismu L. Eulerju. Zato se imenuje Goldbachova domneva. Doslej je še nihče ni dokazal, prav tako ni nihče našel kakega protiprimera. Z računalniki so potrdili veljavnost domneve za velikansko množico sodih števil. Toda dokler nimamo strogega dokaza, ne moremo z gotovostjo trditi, da je Goldbachova domneva pravilna. Morda soda števila, ki jih ni mogoče razstaviti v vsoto dveh praštevil, obstajajo, vendar so zelo velika in se tudi najmanjše med njimi izraža v desetiškem sestavu s številko, ki ima nekaj sto števk. Če bi bilo to res, Goldbachova domneva ne bi bila pravilna, toda tega ne bi mogli nikoli odkriti s testiranjem, niti z uporabo najhitrejših računalnikov ne.
PRIPOMBA. Če se da število n vsaj na en način zapisati kot vsota dveh praštevil, bomo na kratko rekli, da je vsota dveh praštevil, če pa to ni mogoče, potem n ni vsota dveh praštevil. Naj bosta a in b naravni števili. Izjava, da je a+b vsota dveh praštevil, torej ne pomeni, da sta a in b praštevili, temveč da obstajata taki praštevili p1 in p2, da je a+b = p1+p2. Npr. število 8+6 je vsota dveh praštevil, ker je 8 + 6 = 14 = 3+11.
Kdaj je liho število vsota dveh praštevil? Ker so razen 2 vsa praštevila liha, vsota dveh lihih števil pa je soda, je liho število n vsota dveh praštevil natanko tedaj, kadar ima obliko n = p + 2, kjer je p liho praštevilo. Torej je liho število n vsota dveh praštevil, če je razlika n – 2 praštevilo, sicer pa ni. Tako je npr. 9 vsota dveh praštevil, ker je razlika 9 – 2 = 7 praštevilo, 11 ni, ker je razlika 11 – 2 = 9 = 3∙3 sestavljeno število.
Kaj lahko na splošno povemo o izražanju lihih števil, namreč tudi tistih, ki niso vsote dveh praštevil?
DOMNEVA L. Vsako liho število >= 7 se da zapisati kot vsota treh praštevil.
Denimo, da je Goldbachova domneva pravilna. Naj bo n poljubno liho število >= 7. Potem je razlika n – 3 soda in >= 4, torej je vsota dveh praštevil, npr. n – 3 = p1-p2, kjer sta p1 in p2 praštevili. Od tod dobimo n = 3 + p1 + p2. Tako smo zapisali n kot vsoto treh praštevil 3, p1 in p2. Vidimo, da iz pravilnosti Goldbachove domneve izhaja pravilnost domneve L. V obratni smeri pa ne gre; ne znamo dokazati, da je Goldbachova domneva pravilna, če je pravilna domneva L.
Domnevo L bi skoraj smeli imenovati izrek. Leta 1937 je namreč ruskemu matematiku I. M. Vinogradovu uspelo dokazati, da je vsako liho število, ki je dovolj veliko, namreč večje od N0=, vsota treh praštevil. Število N0 se v desetiškem sestavu izraža s številko, ki ima skoraj sedem milijonov števk, se pravi, da je nepredstavljivo veliko. Kljub temu je do N0 samo končno mnogo lihih števil. Treba bi bilo vsako od njih testirati, ali je vsota treh praštevil. Če je, bi bila domneva L dokazana. Žal je N0 tako velik, da tega testiranja verjetno ne bo mogoče nikoli opraviti niti z najhitrejšimi računalniki.
PRIPOMBA. Pred nekaj leti sta Chen in Wang zmanjšala omenjeno mejo N0 na število, ki ima, zapisano v desetiškem sistemu, samo okoli triinštirideset tisoč števk. Testiranje lihih števil do te meje je seveda praktično prav tako neizvedljivo.
Oglejmo si zdaj neko zanimivo nalogo, ki je rešljiva samo na en način, če je Goldbachova domneva pravilna. Glasi se takole:
Peter je izbral dve naravni števili, večji od 1. Vsoto teh števil je povedal prijatelju Tonetu, produkt pa Mirku. Tone si ogleda vsoto in telefonira Mirku:
“Ne vidim možnosti, kako bi ti lahko ugotovil vsoto.”
Čez nekaj časa odgovori Mirko:
“Imaš prav. Ne morem določiti vsote.”
Kmalu nato pa se spet oglasi Tone:
“Vem, kolikšen je produkt.”
Kateri števili je izbral Peter?
Nalogo v tej obliki je postavil Barry Wolk z univerze v Manitobi, objavil pa jo je Martin Gardner v časopisu Scientific American junija 1980. Imenoval jo je nemogoči problem, in sicer zato, ker na videz ni dan noben podatek, ki bi omogočil rešiti nalogo.
Imenujmo izbrani naravni števili x in y, vsota x+y naj bo V, produkt xy pa P. Ker sta x in y večja od 1, je P produkt najmanj dveh praštevil. Mirko, ki je poznal P, je P razstavil na prafaktorje. Vsoto bi takoj našel, če bi bil P produkt samo dveh praštevil. Recimo, da bi bilo P = 15 = 3 ∙ 5. V tem primeru bi Peter izbral števili 3 in 5, vsota pa bi bila 8. Mirko ni mogel določiti vsote zato, ker je P produkt najmanj treh prafaktorjev. Kako je Tone to vedel? Ogledal si je vsoto V in videl, da se V ne da zapisati kot vsota dveh praštevil in potemtakem P ne more biti produkt samo dveh prafaktorjev. Njegovo telefonsko sporočilo Mirku je zato vsebovalo informacijo, da V ni vsota dveh praštevil. Mirko je zdaj skušal razstaviti P na dva faktorja tako, da vsota faktorjev ni vsota dveh praštevil. Če bi se dal P razstaviti v tem smislu samo na en način, bi Mirko dobil faktorja x in y, s tem pa vsoto V = x + y. Denimo, da bi bilo P = 18. Število 18 lahko razstavimo na dva načina v produkt dveh faktorjev, ki sta oba večja od 1, namreč 18 = 3 ∙ 6 in 18 = 2 ∙ 9. Vsota faktorjev je v prvem primeru 3 + 6 = 9. Ker je 9 = 2 + 7 vsota dveh praštevil, izbrani števili nista 3 in 6. V drugem primeru je vsota faktorjev 2+ 9 = 11, ki ni vsota dveh praštevil. Če bi bil torej produkt 18, bi Mirko ugotovil, da je Peter izbral števili 2 in 9 in da je vsota V = 11. Toda Tonetu je telefoniral, da vsote ne more najti. Zakaj ne? Videl je namreč, da se da P razstaviti vsaj na dva načina v produkt dveh faktorjev tako, da vsota faktorjev ni vsota dveh praštevil. Ko je Tone dobil sporočilo od Mirka, je zapisal V na vse mogoče načine kot vsoto dveh sumandov
V=2+(V-2)=3+(V-3)=…
in si ogledal pripadajoče produkte 2(V-2), 3(V-3), 4(V-4) itd. Ugotovil je, da je mogoče samo enega izmed njih razstaviti še na en način v produkt dveh faktorjev tako, da vsota faktorjev ni vsota dveh praštevil. Tisti produkt je bil pravi. Zato je lahko telefoniral Mirku, da je našel produkt.
Tone je poznal vsoto V izbranih števil, Mirko produkt P, mi pa ne poznamo niti V niti P. Kako bomo razvozlali uganko? Naštejmo, kaj vemo o naravnih številih x in y, ki jih je Peter izbral, o vsoti V in produktu P :
(i) x in y sta večja od 1.
(ii) V = x + y ni vsota dveh praštevil.
(iii) Število P = xy se da vsaj še na en način razstaviti v produkt x’y’ tako, da vsota faktorjev x’ + y’ ni vsota dveh praštevil.
(iv) Število V lahko zapišemo na en sam način kot vsoto x+ y, kjer imata sumanda x in y lastnosti, navedeni v (i) in (iii).
Dokažimo zdaj, da sta x, y, z njima pa vsota V in produkt P, z lastnostmi (i) do (iv), natanko določena, če je Goldbachova domneva pravilna.
Po (i) je vsota V = x + y najmanj
enaka 4. Če drži Goldbachova domneva, je vsako sodo število > 4 vsota dveh
praštevil. Pogoj (ii) potemtakem pove, da je V liho število. Tudi razlika V – 2
je liha, ni pa enaka kakšnemu praštevilu p, saj bi sicer bil V = p + 2 vsota
praštevil p in 2. Zato je V – 2 sestavljeno število. Razstavimo ga v produkt
ab, kjer sta faktorja a in b liha in večja od 1. Tedaj imamo V = ab + 2. Ker
sta a in b liha, sta razliki a – 1 in b – 1 sodi in zato lahko pišemo a – l =
2m,
b – 1 = 2n, kjer sta m in n naravni števili > 1. Potem je a = 2m + 1, b = 2n
+ 1 in
V = 4mn + 2(m + n) + 3
Število V bomo zdaj na dva načina zapisali kot vsoto dveh sumandov. Najprej postavimo
x = 4mn + 2 , y = 2(m + n) + 1 .
Potem je x + y = V. Pripadajoči produkt
P = xy = (4mn + 2)(2m + 2n + 1) lahko razstavimo na dva faktorja x’ in y’ tudi takole:
x’ = 2 , y’ = (2mn + 1)(2m + 2n + l) .
Očitno sta faktorja x’ in y’ različna od faktorjev x in y v prejšnjem razcepu. Vsota novih faktorjev
x’ + y’ = (2mn + 1)(2m + 2n + l) + 2
je liho število in ni vsota dveh praštevil, ker (2mn + 1)(2m + 2n + 1) očitno ni praštevilo. Torej smo zapisali V kot vsoto x + y, pri tem pa se da pripadajoči produkt P = xy vsaj na dva načina razstaviti v produkt dveh faktorjev tako, da vsota faktorjev ni vsota dveh praštevil.
Drugič razcepimo V na tale sumanda:
X = 4mn – 4m + 2 , Y = 6m + 2n + 1 .
Ta razcep je različen od prejšnjega, ker ni niti X = x, niti X = y (X je namreč sod, y lih). Oglejmo si produkt
XY = (4mn — 4m + 2)(6m + 2n + 1) .
Če postavimo
X’ = 2, = (2mn — 2m + 1)(6m + 2n + 1) ,
je X’Y’ = XY. Privzemimo najprej, da je n > 1, torej
4mn – 4m = 4m(n – 1) > 0.
Potem je X = 4m(n – 1) + 2 > 2 in zato X > X’ = 2 ter Y’ > Y. Vsota
X’ + Y’ = (2mn — 2m + 1)(6m + 2n + 1) + 2
je liho število. Ker je zaradi n > 1 faktor 2mn — 2m + 1 večji od 1, X’ +Y’ ni vsota dveh praštevil.
Če je torej n > 1, se da V zapisati vsaj na dva načina kot vsota dveh sumandov, tako da sumanda ustrezata pogojema (i) in (iii). Zato v tem primeru V nima lastnosti (iv). Isto lahko trdimo tedaj, kadar je m > 1. Izraz (1) za V, se pravi V = 4mn + 2(m + n) + 3, se namreč nič ne spremeni, če v njem zamenjamo m in n. Tako smo ugotovili, da število V ne zadošča pogoju (iv), če je katero izmed števil m in n večje od 1.
Preostane edina možnost, da je m = n = 1. Tedaj je V = 11. Pišemo lahko
V = 11 = 2 + 9 = 3 + 8 = 4 7 = 5 + 6 .
Pripadajoči produkti so 2 ∙ 9 = 18, 3 ∙ 8 = 24, 4 ∙ 7 = 28 in 5 ∙ 6 = 30. Ugotovili smo že, da se da 18 razstaviti samo na en način v produkt dveh faktorjev tako, da vsota faktorjev ni vsota dveh praštevil. Bralec naj se sam prepriča, da velja isto za števili 24 in 28. Pač pa lahko razstavimo 30 na dva načina v produkt dveh faktorjev tako, da vsota faktorjev ni vsota dveh praštevil. En razcep je 5∙6 z vsoto faktorjev 5 + 6 = 11, drugi 2 15 z vsoto 2 + 15 = 17. Niti 11 niti 17 ni vsota dveh praštevil. Vidimo, da se da 11 samo na en način zapisati kot vsota x + y tako, da sumanda x in y zadoščata pogoju (iii), namreč 11 = 5 + 6. Torej ima V = 11 tudi lastnost (iv).
Iz povedanega je razvidno, da edino števili 5 in 6 z vsoto V = 11 in produktom P = 30 zadoščata pogojem (i) do (iv). Odgovor na zastavljeno vprašanje se potemtakem glasi:
Peter je izbral števili 5 in 6.
Pri reševanju naloge smo privzeli, da je Goldbachova domneva pravilna. To nam je omogočilo dokazati, da je vsota V liho število. Če se ne zanesemo na pravilnost domneve, potrebujemo dodatni podatek, da je namreč V lih. Drugi pogoj moramo torej postaviti takole:
(ii*) V = x + y je liho število in ni vsota dveh praštevil.
Potem poteka dokazovanje kakor prej. Edino števili 5 in 6 z vsoto V = 11 in produktom P = 30 zadoščata pogojem (i), (ii*), (iii) in (iv).
Vsako naravno število n je produkt samih praštevil. Obstajajo me¬tode, s katerimi je dejansko mogoče razstaviti n v produkt praštevil s končno mnogo koraki. Tako pravi teorija, ki pa je po navadi ne zanima, koliko dela je treba opraviti pri razstavljanju. V praksi je obseg dela seveda še kako pomemben. Kar precej časa potrebujemo, da razstavimo na prafaktorje nekoliko večje število, tudi če si pomagamo z računalniki. Pri velikih številih pa je računanja toliko, da ga ne zmore v razumnem času niti najhitrejši računalnik.
Iz formulacije naloge je razvidno, da je Mirko razmeroma hitro razstavil P na prafaktorje in da je prav tako Tone kmalu pregledal vse produkte 2(V — 2), 3(V — 3), … in našel med njimi pravega. Zato Peter prav gotovo ni izbral zelo velikih števil x in y. Torej smemo domnevati, da je vsota V = x + y manjša od meje, do katere so testirali vsa soda števila in ugotovili, da je vsako izmed njih vsota dveh praštevil. Potemtakem ne potrebujemo dodatnega podatka, da je V lih in smemo ostati kar pri prvotnem pogoju (ii).
Mnogoženski mat
V daljni Perziji je imel Šah zelo obsežen harem. Zgodbe pravijo, da je v nekem trenutku lastnoročno zadrgnil vrat črnemu nasprotniku, kot kaže pozicija.
Pozicija v zapisu FEN:
k7/2KQQQQQ/1Q1QQQQQ/1QQQQQQQ/
1QQQQQQQ/1QQQQQQQ/1QQQQQQQ/
1QQQQQQQ b – – 0 0
Pozicijo seveda lahko udobno urejate s spletnim orodjem Lichess.
Žal je pri zapisu natančnega položaja (očitno) prišlo do napak. Zadnja poteza belega je bila Kc6-c7#. Kaj pa je bilo pred tem? In še pred tem?
Vaša naloga je restavrirati položaj, morda s kako priležnico manj (vendar tako, da jih ostane čim več!), tako da bo dosegljiv s pravilnimi potezami.
Najkrajša dokazna partija (1)
SPG 5.5
Na sliki imamo zanimivo matno pozicijo, črnega kralja je precej hitro matiral beli kralj, z odkritim šahom. Kako priti do te pozicije?
Nalogo je sestavil Christoph Fieberg leta 2002.
Do te pozicije seveda lahko pridemo na mnogo načinov, toda naloga predpisuje SPG v 5.5 oz. najkrajša dokazna partija v (natančno) 5,5 potezah. Od kod polovičke poteze? Poteza je pravzaprav sestavljena iz dveh polpotez, belega in črnega. 5,5 potez torej pomeni, da je zadnjo polpotezo odigral beli. Če je zadnji odigral črni, to poudarimo in rečemo, da je pozicija nastala (recimo) v 4,0 poteze.
Kako je šla zgoraj omenjena partija?
Potek
Bistvo dokazne partije je, da se izteče v predpisanem številu potez, da je partija unikatna in s tem, da vrstnega reda potez ni mogoče zamenjati.
Naloga
Poskusite sami razrešiti naslednjo nalogo: SPG 4.0, torej, pozicija je nastala po četrti potezi črnega, kako je šla partija?