Hole and the Board - 3

A carpet of size 10 by 10 meters should be placed in a room of size 12 by 9 meters. In the center of the room, there is an aquarium of size 8 by 1 meters (see the figure below). The carpet should be cut into no more than two pieces (i.e. one cut in total).

Center of a circle

Using only a compass, can you find the center of a circle?
NOTE: You can't use anything other than compass. Not even a ruler or a scale. This implies, you can't make a straight also.

Search for Celebrity

Consider a party of n people. Consider a matrix A (nXn) with each entry being either 0 or 1. 
A(ij) = 1 if the ith person knows jth person in party
A(ij) = 0 if the ith person doesn't know jth person in party
Also note that A(ij) is not always equal to A(ji)


A celebrity is the one who doesn't know anybody but everybody knows him. 
Can you find the celebrity in O(n).

Disclaimer: This was again asked in GSach Interview which I was unable to answer. I guess you can try using directed graphs for solving this but not sure.

Array of natural number

Consider an array 'A' of 1st n natural numbers randomly permuted. Consider an array B formed from array A as given below
B(k) = number of elements from A(1) to A(k-1) which are smaller than A(k)
Obviously B(1) = 0;
i) Given A can you find B in O(n)
ii) Given B can you find A in O(n)


Disclaimer: The question was asked to me during GSachs interview and of course I was unable to answer. I am still unable to figure out the solution

Guess the hat

Consider infinite people with each wearing a red or a black hat such that they can't see their hat but can see other's hat. Now, everybody has to tell the color of his hat simultaneously.
a) Derive a strategy such that infinite people can say correct answer
b) Derive a strategy that only finite people will say wrong answer