2. Given a 2^n x 2^n chessboard and an infinite number of L shaped tiles (of size 2x2) which may be rotated and placed, is it possible to tile the entire chessboard leaving just a single gap?
3. Find the minimum number of comparisons required to find the minimum and maximum element in the array of 20 elements.
4. Jack and his wife went to a party where four other married couples were present. When Jack asks everyone (including his wife) how many hands they shook. He gets all different answers. No person shakes hands with their partners.
How many hands did Jack's wife shake?
Here are few more questions asked by google:
Q2. Use induction. In fact the gap can be anywhere on the board. Obv true for n=1. For n=2, divide 4x4 into 4 2x2 squares, the gap belongs to one of these squares. Cover that square use L. For remaining three, you can put L at the inner corner of the big L formed by the 3 2x2 squares. And cover the rest. And so on for any n. It is difficult to explain without diagrams.
ReplyDeleteSolving the second question by induction -
ReplyDeleteAssume that for n-1 I can tile the chess board such that the only right-bottom corner is left out. (Hence essentially I can tile the chessboard with any corner left out(by rotations), I call them RB(if RightBottom corner if left out), LT(if left top corner is left out) and so on).
Now to solve for n take an instance of the form
RB LB
RT RB
notice that in the above configuration the gap left out in the middle is an L shape exactly which can be filled. The gap left here again is RB, and the induction goes on. Base Case 2x2 is ob.
why are the times on this blog wrong?
ReplyDeleteAnswer 4:
ReplyDelete4
9 people other that jack,
max handshakes possible = 8 therefore all numbers from 0 to 8 covered => 0 and 8 handshake are couples similarly 7 and 1 are couples.... so on.
@Abhilash: Correct Solution!
ReplyDelete@Aditya and NB: Correct Solution!