In this exercise we learn how routing may cause congestion at the nodes. Consider an mx (2n+1) grid with m rows and 2n+1 columns and a total of m(2n + 1) nodes. Label by (i,j) the node in the i-th row and j-th column of the grid. Also consider the middle column M of nodes (1,n+1),..., (m, n+1). m rows n columns M n columns n+1 The nodes establish simultaneous communications sessions as follows. Each of the m nodes at the leftmost column creates an arbitrary dedicated path traversing the grid to each node in the rightmost column. In particular, each node in the leftmost column creates m paths. 1. [2 pts] Show that in total at least (m) paths have to pass through nodes of the middle column M. 2. [4 pts] Show that there is node in the column M so that at least (m) paths have to pass through it. 3. [4 pts] Now assume that all but l nodes among the nodes of the vertical column M are faulty and cannot route packets; so all packets have to be routed through non-faulty nodes in M; the senders know of these non-faulty nodes and can forward packets so as to avoid faulty nodes. Show that there is a node in the column M so that at least (m/l) paths have to pass through it.? Hint: Use the pigeonhole principle. The symbol (f(n)) means "at least cf(n)", where c> 0 is a constant independent of n.