Úloha 1.u4: Medián dvou množin (4 b)

Zadáno v čísle 24.1.

Zadání

Z hromádky kartiček očíslovaných od 1 do $2^ k$ jsem si vybral $m$ kousků, můj kamarád si poté vylosoval svých $n$ kousků. Chtěli bychom zjistit medián čísel1 na všech našich kartičkách, ale nevíme, jaká čísla si vylosoval ten druhý. Jak máme postupovat, abychom si mezi sebou museli pro zjištění mediánu předat co nejméně bitů informace? Průběh výměny informací si dohodneme předem, tj. můžeme se například dohodnout, že nejdřív já pošlu své nejmenší číslo, pak kamarád pošle svoje nejmenší číslo atd.


1) Medián z čísel $a_1$, $a_2$, …, $a_ n$ je takové $a_ i$, že skončí přesně uprostřed, pokud čísla seřadíme podle velikosti. Je-li $n$ sudé, pak jsou „prostřední“ prvky dva a medián je jejich průměr. Tedy medián z čísel 1, 4, 2, 5, 1 je 2, medián z čísel 1, 4, 2, 5 je $(4+2)/2 = 3$.