Matematická olympiáda – kategorie P

Zadání úloh oblastního kola 42. ročníku

P-II-1

Města A a B jsou spojena rovným úsekem cesty. Na této cestě leží města A₁, ..., A_n, B₁, ..., B_n (ne nutně v tomto pořadí, ale vždy je město A_i blíže k A než město B_i (1<=i<=n)). Nákladní auto jezdí mezi A a B a má n objednávek; i. tá (1<=i<=n) objednávka je převézt náklad z A_i do B_i; přitom auto může vézt vždy nejvýše jeden náklad a po naložení v A_i ho může vyložit jedině v B_i.

Jízdou nákladního auta rozumíme cestu auta z města A do města B (s případným splněním některých objednávek) a zpět; během jízdy lze změnit směr jen v městě B.

Napište a zdůvodněte program, který pro zadané vzdálenosti měst A_i a B_i od A sestaví plán nákladního auta (tj. určí počet jízd a splněné objednávky pro každou jízdu) tak, aby splnilo všechny objednávky minimálním počtem jízd.

P-II-2

Body X₁=(x₁,y₁), ..., X_n=(x_n,y_n) (n>=3) tvoří (v tomto pořadí) vrcholy konvexního n-úhelníka M v rovině.

Napište a zdůvodněte program, který určí délku strany čtverce S s následujícími vlastnostmi:

S pokrývá M
alespoň jedna strana M leží na straně S
S má nejmenší možný obsah

Poznámka

V programu můžete použít vzorce z analytické geometrie (např. pro vzdálenost 2 bodů, vzdálenost bodu od přímky, apod.) jako funkce. Tyto funkce nemusíte programovat.

P-II-3

Multiplikativní složitost

Lineární algoritmus je algoritmus následujícího tvaru:
Vstup: x₁, x₂, ..., x_n (vstupní proměnné)
f₁:=g₁ op h₁
f₂:=g₂ op h₂
....
f_k:=g_k op h_k
Výstup: y₁, y₂, ..., y_m (výstupní proměnné)
přičemž pro každé i=1, ..., k je g_i, h_i prvkem {x₁, ..., x_n} U {f₁, ..., f_i-1} a op je jedna z operací +, -, * (sčítání, odčítání, násobení).

Složitost lineárního algoritmu je počet operací op, multiplikativní složitost lineárního algoritmu je počet operací *.

Například následující lineární algoritmus:

Vstup: a, b, c, d
f₁ := a * b
f₂ := c * d
f₃ := f₁ - f₂
Výstup: f₃
počítá hodnotu výrazu ab-cd a má multiplikativní složitost 2.

Úlohy

Zjistěte, jakou činnost vykonává následující lineární algoritmus:
Vstup: a₁₁, a₁₂, a₂₁, a₂₂, b₁₁, b₁₂, b₂₁, b₂₂
f₁:=a₁₁+a₂₂
f₂:=b₁₁+b₂₂
f₃:=a₂₁+a₂₂
f₄:=b₁₂-b₂₂
f₅:=b₂₁-b₁₁
f₆:=a₁₁+a₁₂
f₇:=a₂₁-a₁₁
f₈:=b₁₁+b₁₂
f₉:=a₁₂-a₂₂
f₁₀:=b₂₁+b₂₂
f₁₁:=f₁*f₂
f₁₂:=f₃*b₁₁
f₁₃:=a₁₁*f₄
f₁₄:=a₂₂*f₅
f₁₅:=f₆*b₂₂
f₁₆:=f₇*f₈
f₁₇:=f₉*f₁₀
f₁₈:=f₁₁+f₁₄
f₁₉:=f₁₅-f₁₇
f₂₀:=f₁₁+f₁₃
f₂₁:=f₁₂-f₁₆
f₂₂:=f₁₈-f₁₉
f₂₃:=f₁₂+f₁₄
f₂₄:=f₁₃+f₁₅
f₂₅:=f₂₀-f₂₁
Výstup: f₂₂, f₂₃, f₂₄, f₂₅
Najděte lineární algoritmus s co nejmenší multiplikativní složitostí, který pro vstup x₁, ..., x_n, y₁, ..., y_n, u₁, ..., u_n, v₁, ..., v_n vypočítá:
x₁u₁+x₂u₂+...+x_nu_n
x₁v₁+x₂v₂+...+x_nv_n
y₁u₁+y₂u₂+...+y_nu_n
y₁v₁+y₂v₂+...+y_nv_n

P-II-4

McCullochův stroj

McCullochův stroj slouží ke zpracování čísel. Má vstup a výstup; jestiže na vstup dáme číslo, tj. konečnou neprázdnou posloupnost cifer 1, 2, ..., 9, po konečném čase se na výstupu může (ale nemusí) objevit (obecně jiné) číslo - odpověď stroje na vstupní číslo. V prvním případě (jestliže se odpověď objeví), vstupní číslo se nazývá přijatelným. Odpověď stroje je vstupním číslem jednoznačně určená:

jestliže je vstupní číslo přijatelné, odpověď se objeví vždy a je vždy stejná.
jestliže vstupní číslo není přijatelné, nikdy se neobjeví odpověď a stroj se po konečném čase zastaví (tj. můžeme zjistit, že vstupní číslo není přijatelné).

Zavedeme si tato značení:

Jak již bylo řečeno, čísla jsou pro nás kladná celá čísla, jejichž desítkový zápis neobsahuje nulu.
Jestliže X, Y jsou čísla, pak XY označuje jejich spojení: číslo, které dostaneme napsáním zápisů čísel X, Y za sebou (v tomto pořadí). Např. pro X=53 a Y=728 je XY=53728 a XYX=5372853. Číslo XX..X (k-krát) zapíšeme jako X^k.
Zdvojením čísla X je číslo XX, tj. např. zdvojením čísla X=12345 je XX=1234512345.
Říkáme, že číslo X vytváří číslo Y, jestliže X je přijatelné a po zadání X na vstup stroje je odpovědí Y. Tento vztah budeme zkráceně zapisovat X->Y.

McCullochův stroj se řídí následujícími pravidly:

Pravidlo P1: Pro libovolné číslo X, 2X2 je přijatelné a vytváří X (2X2->X).
Pravidlo P2: Pro libovolná čísla X, Y, jestliže X vytváří Y, pak 7X vytváří Y2. Zkráceně: z X->Y plyne 7X->Y2.
Pravidlo P3: Pro libovolná čísla X, Y, jestliže X vytváří Y, pak 5X vytváří zdvojení čísla Y, tedy z X->Y plyne 5X->YY.
Pravidlo P0: Číslo X je přijatelné pravě tehdy, když to vyplývá z pravidel P1, P2, P3.

Například 2532->53 podle P1, 72532->532 podle P2, 572532->532532 podle P3, ale 4253 není přijatelné podle P0.

Operační číslo je číslo složené z cifer 5, 7. Každé operační číslo M určuje operaci M() v následujícím smyslu: z X->Y plyne MX->M(X). Např. 5 určuje operaci zdvojení (5(Y)=YY), neboť z X->Y plyne 5X->YY. 75 určuje operaci připsání 2 ke zdvojení (75(Y)=YY2), neboť z X->Y plyne 75X->YY2.

Úlohy

(Craigův zákon) Pro každé operační číslo M a pro každé číslo A existuje číslo X vytvářející M(AX), tj. X->M(AX). Dokažte!
Najděte čísla X<>Y taková, že X->Y a zároveň Y->X!
(Fergussonův zákon) Pro libovolná A, B existují čísla X, Y tak, že X->AY a zároveň Y->BX. Dokažte!