$1.$ Suppose the Davies$-$Meyer Construction $($module $7\mathrm{.}3$ slide $2)$ is used to construct a hash function for fixed length

messages using a block cipher PI$.$ Suppose that a search space of $2^112$ is considered large enough to make a brute

force attack infeasible. What should be the minimum block size of PI to protect against brute force birthday

attacks to search for a collision.