Excercise Probabilistic counting
1) Smart Cards provide an interesting application for the probabilistic
counting technique. Write-only memories are technologically easier
to implement than ordinary read-write memories. Write-only bits are
initialized to 0 at the factory. They can be read at will, and they
can be flipped to 1, but they cannot be reset to 0. Prove that it
is impossible to count more than n events in an n-bit write-only register
by any deterministic technique. Show however that it is possible
to count up to 2^n - 1 events by probabilistic methods. In other
words, probabilistic counting and write-only register cover the same ground
as deterministic counting and an ordinary register of the same length.
2) A room contains 25 strangers; would you be willing to bet at
even odds that at least two of them share the same birthday?