Úloha 5.u1: Platové dilema (2 b)

Zadáno v čísle 22.5.

Řešeno v čísle 22.7.

Zadání

Představte si skupinku státních zástupců, kteří by rádi zjistili, jaký je jejich průměrný plat, ale přitom žádný z nich nechce výši toho svého prozradit. Poradíte jim, jak jejich průměrný plat zjistit, aniž by se některý z nich dozvěděl výši platu někoho dalšího? Právníci nemají k dispozici žádný materiál, mohou využívat jen své hlavy.

Řešení

Pojďme se zamyslet nad řešeními podle počtu právníků. Pro jediného právníka je úloha zjevně vyřešena. Pro dva právníky úloha nemá řešení, jelikož z průměru a znalosti svého platu si může každý právník dopočítat výši platu toho druhého.

Podívejme se tedy na možná řešení pro tři a více právníků. Úplně správná řešení neumožňují, aby některý z právníků získal horní či dolní odhad na výši platu někoho z ostatních právníků.

Asi nejjednodušší řešení obsahovalo posílání náhodného čísla od jednoho právníka přes všechny ostatní. První právník si vymyslí přirozené číslo řádově vyšší, než je jeho vlastní plat, nebo náhodné celé číslo.1 Toto číslo si zapamatuje a nikomu jinému jej nesdělí. Poté k němu přičte vlastní plat a výsledek pošle dalšímu právníkovi. Další právníci pak již pouze přičtou svůj plat k přičítanému číslu a pošlou jej dále. Od výsledného čísla pak první právník odečte původní náhodné číslo a výsledek vydělí počtem právníků (což je veřejná informace). V případě zvolení nedostatečně velkého čísla by každý právník získal poměrně dobrý horní odhad na aritmetický průměr platů právníků před sebou. Speciálně by druhý právník v pořadí získal dobrý horní odhad na plat prvního právníka. Toto řešení bylo nastíněno ve vzorovém řešení podobné úlohy ve 21. ročníku, kdo tedy pozorně četl vzorové řešení, měl výhodu.

V dalším řešení si počet právníků označme jako $n$. Každý právník vytvoří sadu $n-1$ celých čísel, která v součtu dávají jeho plat. Poté každé z těchto čísel řekne jinému kolegovi. Každý právník pak sečte všechna čísla, která obdržel, a výsledek sdělí všem ostatním. Sečtením zveřejněných výsledků a vydělením svým počtem získají právníci požadovaný průměrný plat. Tato metoda měla více možných variant, ať už to byl jiný počet předávaných čísel či že součet čísel nedával plat přímo, ale jeho $k$-násobek, který je pro všechny stejný.

Všimněme si, že na rozdíl od předchozího řešení je tato metoda odolná vůči spiknutí několika právníků s cílem zjistit plat jiného. U předchozího řešení k získání platu jednoho právníka stačí, aby se spikli jeho sousedé. Zde je však potřeba, aby se proti danému jedinci spikli všichni ostatní právníci (v alternativní variantě řešení všichni, kdo dostali od daného právníka nějaké číslo).

Naopak ani jedna z uvedených metod není imunní vůči podvodníkovi, který použije jiné číslo, než je jeho vlastní plat. Takový podvodník pak jako jediný dokáže dopočítat opravdovou výši průměrného platu. Je však nutno poznamenat, že si podvodník v takovém případě nemůže být jistý, zda je opravdu jediný, kdo podváděl.

Anet


1) Pokud by se u platů předpokládaly velmi vysoké rozdíly, je výběr čísla zvláště důležitý.