Matematická olympiáda – kategorie P

Zadání úloh ústředního kola 42. ročníku

P-III-1

Body X₁=(x₁,y₁), ..., X_m=(x_m,y_m) (m>=3) jsou (v tomto pořadí, proti směru hodinových ručiček) vrcholy konvexního m-úhelníka M v rovině.

Mnohoúhelník M leží vevnitř kruhu K se středem S=(x_s,y_s) a poloměrem r (to znamená, že každé X_i je vniřním bodem K).

Říkáme, že bod u ležící na obvodu (hranici) M je viditelný z bodu v, jestliže úsečka uv neobsahuje vnitřní body M. (Všimněte si, že podle této definice jsou všechny body strany X_iX_i+1 viditelné z každého bodu přímky X_iX_i+1; na druhé straně, obvod M je neviditelný pro vnitřní body M!)

Napište a zdůvodnětě co nejrychlejší program, který:

1. Vypočítá a vypíše takové údaje, ze kterých bude pro libovolný bod v ležící na obvodu kruhu K zřejmé, které body ležící na obvodu M jsou z bodu v viditelné.
2. Určí minimální počet bodů ležících na obvodu K tak, aby každý bod na obvodu M byl viditelný alespoň z jednoho z nich.

Poznámka

V programu můžete použít vzorce z analytické geometrie (např. pro vzdálenost 2 bodů anebo pro průsečík dvou přímek, přímky a kružnice apod.) jako funkce; tyto funkce nemusíte programovat.

P-III-2

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.

Úloha

Zjistěte, jakou činnost vykonává následující lineární algoritmus:
Vstup: a, b, c, d
f₁:=a+b
f₂:=c+d
f₃:=a*c
f₄:=b*d
f₅:=f₁*f₂
f₆:=f₅-f₃
f₇:=f₃-f₄
f₈:=f₆-f₄
Výstup: f₇, f₈
a rozhodněte, zda existuje lineární algoritmus počítající f₇ a f₈ s lepší multiplikativní složitostí.

P-III-3

Jsou dány mince v hodnotě q₁, ..., q_n korun, kde 1<=q1<q2<...<qn jsou přirozená čísla a q_i+1/q_i je liché přirozené číslo pro 1<=i<n.

Plátce i příjemce mají k dispozici neomezený počet mincí každé hodnoty. Plátce má zaplatit příjemci obnos X korun. Platba je optimální, jestliže se při ní vymění nejmenší možný počet mincí; tj. pro každé 1<=i<=n dá plátce x_i(>=0) mincí hodnoty q_i, příjemce dá y_i(>=0) mincí hodnoty q_i tak, že suma (x_i-y_i)q_i = X a přitom suma (x_i+y_i) je minimální.

Například při mincích s hodnotou 1, 3 a 9 korun (n=3) se dá 17 korun vyplatit tak, že plátce dá 1 devítikorunu, 2 trojkoruny a 2 jednokoruny, vymění se 5 mincí. Při optimální platbě ovšem dá plátce 2 devítikoruny a příjemce vrátí 1 jednokorunu, vymění se 3 mince.

Napište a zdůvodněte program, který pro vstupní kladné celé číslo X určí optimální způsob platby X korun.

P-III-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.

V řešení můžete bez důkazu využít následující vlastnosti (z minulých kol):

• existuje číslo vytvářející samo sebe (X->X)
• (McCullochův zákon) pro každé číslo A existuje takové číslo X, že X vytváří AX, tj. X->AX
• (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).
• (Fergussonův zákon) Pro libovolná A, B existují čísla X, Y tak, že X->AY a zároveň Y->BX.

Číslo X0 je nesmrtelné, jestliže následující proces není konečný (tj. nevyskytne se v něm nepřijatelné číslo):
Zadám stroji číslo X0.
Jestliže se objeví výsledek X1, zadám stroji číslo X1
Jestliže se objeví výsledek X2, zadám stroji číslo X2
atd.

McCullochův algoritmus zjišťování nesmrtelnosti čísel: Základem algoritmu je číslo H takové, že X je nesmrtelné, pravě když HX není nesmrtelné.

VSTUP: číslo X ALGORITMUS: 1) Y:=X; U:=HX 2) stroji S1 zadáme Y; stroji S2 zadáme U 3) Jestliže stroj S1 dá odpověď Z, pak Y:=Z; jinak STOP - číslo X není nesmrtelné 4) Jestliže stroj S2 dá odpověď V, pak U:=V; jinak STOP - číslo X je nesmrtelné 5) skok na 2

Úlohy

1. Najděte 4 nesmrtelná čísla.
2. Najděte 1993 nesmrtelných čísel.
3. Je McCullochův algoritmus správný?