To celebrate the end of the exams, Hogwarts' instances have decided to organize the following event:
Great Wizardry Contest
The aim of this challenge is to make an object which doesn't exist.
The team who'll make the most outstanding nonexisting object will be rewarded with a nice chocolate cake.
signed : A. Dumbledore
The D-day, Harry and Hermione are facing the jury.
- We got a square... a magic square, Harry announces.
- Really? Dumbledore asks.
- Indeed, Hermione explains, it consists in a 3 cells x 3 cells square, each cell being either blue or red. Nevertheless, if I consider any row from it, I know for sure that it has an odd number of blue cells (the "R" property).
- Furthermore, Harry adds, if I consider any column from it, I know for sure that it has an odd number of red cells (the "C" property).
Perplex looks are exchanged among the jury.
- Interesting, Dumbledore observes.
- Look, Albus, Snape roars. They pretend that each row contains an odd nomber of blue cells, and that each column contains an odd number of red cells, hence an even number of blue ones. Hermione's property (R) indicates me that the square has an odd+odd+odd=odd number of blue cells, while Harry's property (C) implies that the square has an even+even+even=even number of them. Ridiculous!
- Right, our square does not exist, Harry admits.
- But we got one! Hermione exclaims.
- In this case, the jury would be absolutely thrilled to see it.
Harry's expression darkens.
- In fact, our square is top secret, we cannot show it to you. However, there are operations preserving the (R) and (C) properties : for instance a permutation of rows, or of columns, or a 90 degrees rotation followed by a global color inversion. Let's call such an operation a magic transformation (MT). It's easy for you to check that our square satisfies (C) without knowing it totally. For this purpose, I apply a secret MT to the initial square, then I reveal to you the column of your choice, and we can do the whole thing as many times as you want.
- And to check that the squares satisfies (R), Hermione continues, I can also apply different secret MT to the initial square, and unveil after each one of them the row of your choice.
- Aha, Snape smirks. Of course this task is trivial for both of you. But what the jury wants to be sure of, is that the square satisfies simultaneously
(R) and (C). That means that if you apply separately the same MT, and that afterwards you are individually asked to unveil a row (Hermione) and a column (Harry) of the transformed square, your answers should coincide at the intersection, that is, the colors should be the same.
- An excellent suggestion, Dumbledore approves. I guess nobody will oppose that we carry out this little protocol. Hermione, Harry, please decide together on a MT sequence to execute, then will begin the validation process, during which our magic powers will completely prevent you from communicating ; thus noone of you will know the requests issued to the other.
- If we get out of this, we'll have well deserved the chocolate cake, Harry whispers.
Question : Understand the situation. Can Hermione and Harry prepare a plan determining what to answer to the different possible requests in a manner such that the required coincidences are systematically satisfied? Knowing that they can't communicate during the protocol, how may they reach this goal ?
(Thanks to A. M.!)