| I remember the pattern, I do! Back in the year 1992, when I was 9 years old, I participated in the first tour of Russian programming olympiad. The first challenge was this one: "On the infinite coordinate grid (positive integers only), start with the number 0 in the cell with coordinates (0,0). Then, in each cell in the neighbourhood, write the largest integer that hadn't yet appeared in the same row or column. Repeat indefinitely. Find the formula for obtaining the value inside any arbitrary cell in the grid." I have filled a 16x16 grid using this definition manually (of course, the programming olympiad had nothing to do with computers — similar to whiteboard coding during the job interviews these days), and obtained similar pattern. As this task was by far the most interesting in the problem set, I have spent the entire allotted time trying to figure out the formula, without success — so I got 0 points and went out of the competition. And now, 24 years later, I see the solution (not the AND; the pattern looks slightly different, perhaps XOR?) But I should have tried bitwise operations back then. Damn it! |
(Note by the way, that the initial condition about (0,0) can be omitted -- at that point, there are no numbers in that row or column, so the smallest one available is 0!)
Topics you might want to look up: https://en.wikipedia.org/wiki/Combinatorial_game_theory https://en.wikipedia.org/wiki/Nim https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem https://en.wikipedia.org/wiki/Mex_(mathematics) https://en.wikipedia.org/wiki/Nimber