Feladat: 11.23.
*
Egy számot 3-univerzális számnak nevezünk, ha belőle jegyeket letörölve megkapható minden különböző számjegyekből álló
abc háromjegyű szám. Például az 134356 számból letörléssel megkapható a 456 szám, de nem kapható meg a 465 szám.
Hány számjegyű a legrövidebb 3-univerzális szám? (Arany Dániel-verseny, 1986H.)
Megoldás: 11.23
Legyen
U egy 3-univerzális szám és az első jegyétől indulva keressük meg azt a számjegyet, amelyik utoljára fordul elő először. Legyen ez az
a szám. Előtte legalább kilenc számjegy áll, hiszen minden számjegynek kell szerepelnie egy 3-univerzális számban. Ez után a szám után is még kell szerepelnie minden tőle különböző számnak legalább egyszer, mert ha például egy
b számjegy nem szerepel, akkor az
ab kezdetű háromjegyű számokat nem tudjuk megkapni belőle letörléssel. Megint keressük meg azt, amelyik utoljára fordul elő először az első
a után. Legyen ez a
b számjegy. Ekkor az első
a és e között a
b között még legalább nyolc számjegy van. Eddig összesen -
a-t és
b-t is beleszámolva - 19 számjegyből áll a szám. Viszont ez után a
b után is minden további,
a-tól és
b-től különböző számjegynek elő kell fordulnia, különben nem tudnánk minden
ab-vel kezdődő számot letörléssel megkapni. Vagyis eddig összesen legalább 27 számjegynek kell szerepelnie egy 3-univerzális számban. Csakhogy vagy van még egy
a a számjegyek között, vagy ha nincs, akkor
a előtt több, mint kilenc számjegynek kell szerepelnie. Ha ugyanis csak egy
a van, és előtte minden számjegy csak egyszer szerepel, akkor legyen az első két számjegy
u és
v. Ekkor az
uva számot megkaphatjuk letörléssel, de az
vua számot nem, hiszen
a előtt csak egyetlen
u van és az megelőzi
v-t. Tehát egy 3-univerzális számban legalább 28 számjegy van.
Megmutatjuk, hogy van 28 számjegyű 3-univerzális szám van is: ilyen például a
0123456789876543210123456789 szám. Egy tetszőleges
abc számot akarunk ,,kiolvasni" belőle.
a-t az első
0123456789 sorozatból választhatjuk. Ha
a≠9, akkor
b-t választhatjuk a
9876543210 jegysorozatból. Ha
a=9, akkor is! Ugyanígy
c-t választhatjuk az utolsó
0123456789 sorozatból (akkor is, ha
b=9).