     
P 46 (2018/2019) 2 7
Trikrat pakiramo
I L
Ste se že kdaj prepirali, kako zložiti prtljago v
prtljažnik? Tokrat bomo poskusili rešiti nekaj na-
log povezanih s pakiranjem.
Pakiranje kvadrov v kvader
Prevoznik Andrej prevaža tovor. Tovornjak ima pro-
stor za tovor, ki meri 630 cm v dolžino, 170 cm v ši-
rino in 200 cm v višino. Tokrat prevaža škatle enake
oblike, ki merijo 55 cm v dolžino, 45 cm v širino in
35 cm v višino. Kako naj Andrej naloži škatle v to-
vornjak tako, da bo šlo vanj čimveč škatel, pri čemer
se omejimo samo na taka nalaganja, kjer so škatle
zložene druga ob/na drugi tako, da vse enakoimen-
ske dimenzije škatel gledajo v isto smer? Pri tem
imajo prostor za tovor in škatle obliko kvadra.
Obstaja šest načinov takega pakiranja: prvo škatlo
z merami d, s in v lahko namreč postavimo v vogal
tovornega prostora z merami D, S in V tako, da je
mera d vzporedna meri D, mera s vzporedna meri
S, in mera v vzporedna meri V . Nadaljnje možnosti
dobimo, če prvo škatlo obrnemo in s tem njene mere
glede na ta vrstni red permutiramo. Možnosti so:
s, v , d v , d, s v , s, d
d, s, v d, v , s s, d, v
TABELA 1.
Šest načinov postavitve prve škatle
Kateri način je najboljši? Pri prvem načinu gre dol-
žina škatle d kar ⌊D : d⌋-krat1 v dolžino prostora D,
širina škatle s gre ⌊S : s⌋-krat v širino prostora S in
višina škatle v gre ⌊V : v⌋-krat v višino prostora V .
Zmnožek teh treh dobljenih (navzdol zaokroženih)
količnikov pa nam pove, koliko škatel gre na ta način
v tovornjak. Pri vrtenju prve škatle in menjavi mer
1⌊x⌋ =max{n ∈ Z : n ≤ x}
dobimo še druge take količnike in druge zmnožke.
Za dani primer sestavimo sedaj tabelico 2: v gor-
njo vrstico naštejmo mere tovornega prostora, v levi
stolpec pa mere prvo postavljene škatle. Na križišču
stolpca in vrstice pa naj bo količnik ustrezne mere
prostora in ustrezne mere škatle.
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
35 18 4 5
45 14 3 4
55 11 3 3
630 170 200
TABELA 2.
Tabelica kolǐcnikov mer
Količnike iz te tabelice jemljemo v zmnožek po vr-
sticah in stolpcih tako, da količniki niso iz iste vr-
stice niti iz istega stolpca. Tako dobimo šest zmnož-
kov v tabeli 3.
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
168 216 162
14 · 4 · 3 18 · 3 · 4 18 · 3 · 3
s, v , d v , d, s v , s, d
165 176 210
11 · 3 · 5 11 · 4 · 4 14 · 3 · 5
d, s, v d, v , s s, d, v
TABELA 3.
Šest načinov, šest zmnožkov
V danem primeru je torej najboljši peti način z
216 naloženimi škatlami. Dodajmo še to: pri vseh
teh načinih ostane še nekaj praznega prostora, ki je
morda še uporaben za doložitev kake škatle. Kako
izkoristiti morebitni tak ostanek, tu ne bomo premi-
šljali.
Pakiranje krogov v pravokotnik
Tokrat ima prevoznik Andrej tovor plinskih jeklenk
oblike krožnega valja. Naložil je že 40 jeklenk v
osem vrst po pet v vrsto in tako zapolnil razpolo-
žljivi prostor (slika 1 - tloris). Ima še eno jeklenko, ki
bi jo rad dodal na tovornjak.
     
P 46 (2018/2019) 28
SLIKA 1.
8 · 5 = 40
Vendar kako? Po nekaj minutah se domisli. V prvi
vrsti pusti pet jeklenk. Iz druge vrste eno umakne in
ostale štiri porine nekoliko gor in levo v vmesni pro-
stor. Podobno naredi še z vrstami od tretje do osme
ter začuda pridobi prostor za deveto vrsto in skupaj
41 jeklenk (slika 2)!
SLIKA 2.
8⊙ 5 = 41
Tak način pridobivanja prostora poglejmo podro-
bno. Andrej je sprva postavil 40 jeklenk na štiriko-
tniški način: vsaka notranja jeklenka se dotika štirih
sosednjih. Zatem je poskusil povečati število sosed
notranjih jeklenk in izkoristiti obstoječe vrzeli. Lihe
vrste so ohranile po pet jeklenk, sodim je bila po ena
odvzeta, soda vrsta pa je bila pomaknjena v medpro-
store prejšnje vrste. To je šestkotniški način. Večina
notranjih jeklenk ima po šest sosed, vrzeli med tremi
sosednjimi jeklenkami pa so se nekoliko zmanjšale:
prej je tipična vrzel merila (4− π)r 2 .= 0,858r 2 (na
sliki 1 jih je 28), potem pa le še (
√
3 − π : 2)r 2 .=
0,161r 2 (na sliki 2 jih je 56).
Uvedimo sedaj novo operacijo ⊙ takole: zmno-
žek v ·s je število krogov v štirikotniškem načinu na-
laganja krogov v v vrst po s v vrsto, zmnožek v⊙s pa
naj bo število krogov v šestkotniškem načinu pri ena-
kem prostoru kot pri prvem načinu. Zaradi lažje ana-
lize privzemimo še, da prvi način zapolni pravokotni
prostor v celoti do vseh stranic pravokotnika.
Koliko pa je v ⊙ s? Najprej opazimo, da imajo
v vsaki vrsti središča krogov enako koordinato: v
prvi vrsti je to kar polmer kroga, v drugi vrsti je to
polmer kroga in še premer kroga, pomnožen s
√
3 : 2,
v tretji vrsti je to polmer kroga in še dva premera
kroga, pomnožena s
√
3 : 2 itd. Denimo, da imamo
v šestkotniškem načinu skupno v′ vrstic, v1 vrstic
po s krogov in v2 vrstic po s − 1 krogov. Krogi naj
imajo enotski premer. Potem mora veljati:
v ⊙ s = v1s + v2(s − 1), v1 + v2 = v′,
1
2
+
√
3
2
(v′ − 1)+ 1
2
≤ v.
Ta sistem enačb in neenačb ima rešitev
v′ = ⌊1+ 2√
3
(v − 1)⌋,
v1 = ⌊
v′ + 1
2
⌋, v2 = ⌊
v′
2
⌋.
Definirajmo še: v ⊙ 1 = 1⊙ v = v .
Videli smo že, da je 8 ⊙ 5 = 41. Bralec lahko pre-
veri, da je 5 ⊙ 8 = 38 (operacija ⊙ torej ni komu-
tativna). Zanima pa nas, kdaj je dobro jeklenke na-
lagati šestkotniško, kdaj pa ne. V tabeli 4 imamo
prikazano razliko v ⊙ s − v · s. Negativna števila ka-
žejo prednost pri štirikotniškem načinu nalaganja,
pozitivna kažejo prednost pri šestkotniškem načinu
nalaganja. Tabela je usklajena s slikama 1 in 2, ko-
ordinatni vrstici sta zato izjemoma spodaj in levo.
Iz tabele razberemo, da pri majhnih merah pro-
stora bolje deluje prvi način, pri večjih merah pa bo-
lje šestkotniški način. Primer 8⊙5 je prvi, kjer pride
do prevlade šestkotniškega načina. Še to: pokazali
smo primer, kjer je šestkotniški način boljši, ni pa
rečeno, da je najboljši tudi v splošnem.
Pakiranje krogov vzdolž premice
Tokrat morajo gozdarji za d enako debelih okroglih
debel pripraviti na tleh skladovnico. V njej bo v prvi
vrsti k debel, v vsaki nadaljnji pa eno manj oziroma
kolikor jih pač ostane v zadnji vrsti. Vsako deblo
je bodisi na tleh bodisi med dvema spodnjima de-
bloma. Skladovnica naj sprejme vseh d debel, ven-
dar naj bo čim ožja, lahko pa je visoka. Primer skla-
dovnice z d = 8 debli in k = 4 debli v prvi vrsti je
na sliki 3.
     
P 46 (2018/2019) 2 9
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
s/v 1 2 3 4 5 6 7 8 9
1 0 0 0 0 0 0 0 0 0
2 0 −1 −1 −2 −2 −3 −3 −2 −3
3 0 −1 −1 −2 −2 −3 −3 −1 −2
4 0 −1 −1 −2 −2 −3 −3 0 −1
5 0 −1 −1 −2 −2 −3 −3 1 0
6 0 −1 −1 −2 −2 −3 −3 2 1
7 0 −1 −1 −2 −2 −3 −3 3 2
8 0 −1 −1 −2 −2 −3 −3 4 3
9 0 −1 −1 −2 −2 −3 −3 5 4
TABELA 4.
v ⊙ s − v · s
SLIKA 3.
8 = 4+ 3+ 1
Naš cilj bo za dani d izračunati ustrezni k, da bo
mogoče skladovnico pravilno začeti s prvo vrsto s k
debli. Najprej opazimo tole: če se d debel postavi
v skladovnico tako, da je v zadnji vrsti eno samo de-
blo, je število debel d enako
d = k+ (k− 1)+ · · · + 2+ 1 = k(k+ 1)
2
.
V takih primerih je d enak trikotniškemu številu Tk.
Zaporedje trikotniških števil smo verjetno že srečali,
gre pa takole:
0,1,3,6,10,15,21,28,36,45, . . . .
Vidimo, da Tk debel napolni skladovnico s prvo vrsto
s k debli. Za splošni d pa iščemo tak k, da bo
Tk−1 < d ≤ Tk =
k(k+ 1)
2
.
Število kmora biti najmanjša naravna rešitev kvadra-
tne neenačbe k2 + k − 2d ≥ 0, katere diskriminanta
je D = 1 + 8d, pozitivna realna rešitev (
√
D − 1) : 2,
naravna rešitev pa navzgor zaokrožena:2
k = ⌈(
√
8d+ 1− 1) : 2⌉ = ⌈
√
2d+ 1 : 4− 1 : 2⌉.
Primer za d = 30: D = 241,
√
D = 15,524 . . .,
k = 8 in 30 = 8+ 7+ 6+ 5+ 4.
Naloge
1. Poišči čim večje število škatel za podane mere
v spodnji tabelici:
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
40
55
60
550 150 180
2. Na šahovnico je mogoče postaviti 64 krogov s
premerom, enakim robu enega polja. Koliko ta-
kih krogov dobimo s šestkotniško postavitvijo?
3. Gozdarji so posekali 50 debel. V kakšno skla-
dovnico naj jih naložijo?
Rešitve
1. Tabelica je taka:
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
40 13 3 4
55 10 2 3
60 9 2 3
550 150 180
Največje število škatel je 10 · 3 · 3 = 90.
2. Izračunamo 8⊙ 8 = 68.
3. Za d = 50 izračunamo D = 401,
√
D = 20,024
in k = 10 ter 50 = 10+ 9+ 8+ 7+ 6+ 5+ 4+ 1.
×××
2⌈x⌉ =min{n ∈ Z : n ≥ x}.