Finding factors

We received a few different ideas about how many answers need to be revealed in order to work out all of the headings. Thank you to everybody who sent in their ideas about this problem.

Dhruv from The Glasgow Academy in Scotland explained:

The smallest amount of flaps you need to open to figure out the headers is 6.

Image

I wonder what the general rule for revealing this pattern of answers would be, on an $n$ by $n$ grid?

Ci Hui from Queensland Academies for Science Mathematics and Technology in Australia looked for the lowest number of answers it is possible to reveal in order to find the correct headers:

The smallest number of answers I need to reveal is 4 (in a 4x4 grid) 6 (6x6) 8 (8x8)

So if we have a square $n^2$ then the number of answers I need to reveal is $n$.

Step 1 Factorisation of quadratic expressions with constraints given. In those one clicked square in each row/column

Image

Location of known quadratic expression

No two items in same column/row

Put the factors in

E.g. $x^2-2x+1=(x+-1)(x+-1)$

Step 2 Repeat this for all rows/columns

Image

Step 3 Multiply each column and row to fill in the table and check.

Image

Image

I wonder how likely it is that Ci Hui's headers will all be the correct way round using this method?

Ci Hui did some further investigation with the larger grids:

6x6 with 6 knowns and no repeated factors in each column and row and yet the answer is wrong

4 mistakes. Need more known expressions! Maximum 4 more. It means that for a 6x6 grid, between 6 and 10 known expressions are needed.

This is true of the particular grid you tried, Ci Hui, but I'm not sure this necessarily tells us anything about the more general case. In some grids, revealing $n$ answers in an $n$ by $n$ grid would lead to getting every header wrong, because they would all be the wrong way round. I wonder how many more answers we would have to reveal to be sure that every header was the correct way round?

Kris from Ripon Grammar School in the UK sent in this explanation of how the grid can be solved by revealing $1.5n$ squares, rounded up if $n$ is odd:

In the four-by-four square, the maximum number of squares revealed to figure out each of the multipliers is six. There are eight multipliers so to figure them out you would need to open four quadratics because each quadratic has two multipliers but you would need to make each one would be in a different column and row to each other so you get the same multiplier twice. Now you would know all of the multipliers by working out the quadratics but you wouldn't know which order they are in, to find out this you could open any other square and by working out the quadratic you could compare it to the other ones on the same row and column and by seeing which of the multipliers would match and which one didn't match, you would know which one would be on the same column and which one wouldn't. This means you would now know four of the multipliers and by doing the same thing again but this time making sure the next square you open is not in a row or column you have already figured out; you could work out the remaining four multipliers. 

To figure out any $nxn$ grid, you would need to open $1.5n$ squares because first you would need to open one in each row and column and since each square has a column and row you would need to open n squares and then you would need to figure out which ways the multipliers went which you could figure out by opening $0.5n$ more because there would be $2n$ multipliers and each square you open would tell you where 4 of them go and $2n/4= 0.5n$. However, if the grid were an odd number you would need to round up because you cannot open half a square.

This is the most convincing argument we've received so far for a smallest number of answers that will always give the correct order for the headers. In order to visualise Kris's solution, I found it helpful to imagine splitting each grid into several smaller 2 by 2 grids.

Kris also considered how the number of answer reveals needed changes when an answer is revealed which is a perfect square:

However if you find a perfect square, where both the multipliers were the same, you wouldn't need to know the order however there are two problems, if you open it in your last two squares, it won’t make the square count lower because you using the squares to find the order so the perfect square skipping showing what order they go in won't help unlike if you opened it in one of your first four squares where you were opening them to find out the multipliers where they would additionally show you the order, the other problem is that you would need to open at least two for them to make a difference because when you are finding out which way the multipliers go, you find out for each square you open but each perfect square you open only shows where two of the multipliers go so you would need to open another square to find out which way the last two multipliers go. This also means if you find four perfect squares in the first four squares, you could solve it in only four squares.

Assuming the program chooses the squares randomly, each square has a chance of one in ten of being a perfect square because there are only ten options for each of the multipliers with it being "$x$ + an integer from negative five to five" (excluding zero as the program doesn't choose it) so for the first square to match the second, there would be ten options of the first square being and one of what it actually is making it one in ten, for it to be solved in 4 squares opened you would need to get this four times in a row making it a tenth to the power of four making it one in ten thousand but for it being solved in just five moves only two of them would need to be perfect squares which would be one in a hundred but there are six orders you could get the perfect squares (the first and second, first and third, first and fourth, second and third, third and fourth) making it a six in a hundred chance.