MATEMATIKA
—^ razlikovanje med več ključi potrebovali več različnih oznak, a se je izkazalo drugače - če ima profesor na okroglem nosilcu šest ali več ključev, bo za učinkovito razlikovanje med njimi potreboval le dve različni oznaki.
Razlikovalno število grafa
Zgoraj predstavljeni problem so raziskovalči pred približno dvajsetimi leti posplošili tako, da nosileč za ključe ni bil več nujno okrogel in da so definirali razlikovalno število poljubnega grafa G, D(G) kot najmanjše število d, za katerega obstaja razlikovalna označitev grafa G z d različnimi oznakami. Končept razlikovalnega števila je bil vpeljan v članku M. O. Albertson in K. L. Collins, Symmetry breaking in graphs, Elečtron. J. Combin. 3(1996), R18. Danes smo torej določili razlikovalno število čiklov in ugotovili, da je D(C3) = D(C4) = D(C5) = 3 ter D(Cn) = 2 za n > 6. O znanih razlikovalnih številih drugih grafov pa več kdaj drugič.
_ XXX
Naloga
Marko Razpet
-> Izračunaj
■	62 - 5 , 562 - 452, 5562 - 4452, 55562 - 44452. Nato rezultate posploši na razliko kvadratov oblike
55... 5 62 - 44... 4,52 .
n	n
Rešitev
Uporabimo enakost a2 - b2 = (a - b)(a + b) in dobimo:
■	62 - 52 = (6 - 5)(6 + 5) = 1 ■ 11 = 11,
■	562 - 452 = (56 - 45)(56 + 45) = 11 ■ 101 = 1111,
■	5562 - 4452 = (556 - 445)(556 + 445) =
111■1001 =111111,
■	55562 - 44452 = (5556 - 4445)(5556 + 4445) =
1111 ■10001 = 11111111.
Predvidevamo, da velja enakost
55... 5; 62 - 44... 4 52 = 11... 1.
n	n	2n+2
(1)
Ce hocemo (1) zares izpeljati, ne le uganiti, se moramo spomniti, kaj desetiški mestni zapis števil sploh pomeni. 1949 je npr. le krajši zapis števila 1 ■ 103 + 9 ■ 102 + 4 ■ 10 + 9. Brez težav pa lahko krajše izrazimo vsoto Sn = 1 + q + q2 + ... + qn, kjer je q poljubno število, ki ni enako 1, n pa poljubno naravno število. Ker je qSn = q + q2 + q3 + ... + qn + qn+1 = Sn - 1 + qn+1, dobimo Sn iz enacbe qSn = Sn + (qn+1 - 1):
■ Sn = 1 + q + q2 + ... + qn = V posebnem primeru q = 10 je
qn+1 - 1
q -1
1 + 10 + 102 + ... + 10n = 1 (10n+1 - 1).
9
(2)
Enakost (1) lahko sedaj z uporabo mestnega zapisa in (2) preverimo tako:
55... 5 62 - 44... 4 52 =
nn
= (55... ^ 6 - 44... 4ß 5)(55... ^ 6 + 44... 4 5) =
n	n	n	n
= ,11... 1.-1,00... 0,1 =
n+1	n
= (10n + ... + 10 + 1)(10n+1 + 1) =
1 (10n+1 - 1)(10n+1 + 1) = 1 ((10n+1)2 - 1) = 99
1
9
9 (102n+2 -1) =
1 + 10 + ... + 102n+1 = 11... 1
2n+2
XXX
8
PRESEK 44 (2016/2017) 3	5