4. (30 points) Professor Trelawney has acquired origin and dubious reliability. Trelawney needs your help to identify which crystal balls n enchanted crystal balls, of dubious inaccurate. She has constructed a strange contraption that are accurate and which fits over two crystal balls at a time to perform a test. When the contraption is activated each crystal ball glows one of two colors depending accurate or not. An accurate crystal ball always glows correctly according to whether the other crystal ball is accurate or glows the opposite color of what the other crystal ball is (i.e. If the other crystal ball is accurate, it will glow red. If the other crystal ball is inaccurate it will glow green) You quickly notice that there are two possible test outcomes: are whether the other crystal ball is on not, but the glow of inaccurate crystal ball an crystal ball i glows red crystal ballj glows red at least one is inaccurate both green are accurate, or both inaccurate green (a) Prove that if n/2 necessarily determine which crystal balls this kind of pairwise test. crystal balls are inaccurate, Professor Trelawney cannot are tainted using any strategy based or more on (c) Now, under the same assumptions as part (4b), prove that all of the accurate crys- tal balls can be identified with O(n) pairwise tests. Give and solve the recurrence that describes the number of tests