/sci/ - Science & Math

This was a shortlisted IMO question from 2010 and here's the question:
Prove that the maximal possible colors is 2nif the rows and columns of the 2nX 2ntable are numbered from 0 to (2n)-1the cells have been colored with the property “for each 0(is less than or equal to)i, j(is less than or equal to)(2^n)-1 the jth cell in the ith row and the (i+j)th cell in the jth row have the same color, and the indices of the cells in a row are considered modulo 2n.

There is a proof online on the IMO website (question N6 from 2010), but I was particularly confused on the induction hypothesis and how one would know what the next step should be. Either explaining the online proof in greater detail, providing another proof, or providing possible ideas on how to solve it, would be very appreciated.

To start you out (this may not be helpful at all), you should basically redefine things so that you have a coordinate grid, then an equation that connects Fibonacci numbers to numbers you would produce to make a sequence where each set of adjacent numbers create coordinate sets that loop around, and with different seed numbers produces the different possible coordinate sets for different colors, then one would need to find the period of sequences generated by an equation with certain seed conditions, then find a way to represent all of the possible seed conditions that generate different sets of points, and then to sum the periods of all of those sequences.

Help?