2
It sounds like the thing you're trying to prove is this: If $X$ is a terminal $B$-coalgebra, then the greatest $B$-bisimulation on $X$ is the internal equality.
First of all, the definition of internal equality as the kernel pair of $\text{id}_X$ is a bit silly. The following square is a pullback:
$$\require{AMScd}
\begin{CD}
X @>\text{id}_X>> X\\
...
1
If you let $b=\frac54$, then $$\frac nb=\frac{n}{5/4}=\frac{n}{5/4}\times \frac{4/5}{4/5}=\frac{4n}{5}$$
which matches your original expression.
1
A strategy inspired by merge sort works well.
First, split the hats into $\sqrt n$ piles of size $\sqrt n$, and sort each pile by repeatedly finding the smallest unsorted hat in that pile. This takes $O(n)$ queries.
Second, merge the piles. To do this, take the smallest hat from each pile and find the minimum of those. That's the smallest hat of all; set it ...
Only top voted, non community-wiki answers of a minimum length are eligible
