I am stuck at problem 3.
I noticed that borders must contain at least one x
Then I noticed that if there are less than n infected students there are always one not infected row after arbitrary number of steps
I tried to prove that by induction by drawing an (n+1)(n+1) grid and take a n*n piece at top left corner and use induction but I failed.
I tried saying if there are n x inside n*n grid border will be missing so not all (n+1)(n+1) will be infected but if one or more students are infected I cant prove it even using induction hypothesis. I tried strengthening my hypothesis saying if n*n grid contains k initial x and k < n, then there be atleast (n-k) free rows or columns but I couldnt continue from that with induction proof.
Can any one give me a hint about how to find invariant and solution. If you can make hint indirect or better give me a general purpose tip when finding invariants that can aid me here.
Thanks in advance for help and I hope I made my question less cryptic
I know the one-word clue, but I don't think you want it yet.
The version I had found (see my previous link) referred to something slightly different from an invariant; it wasn't a number that remains the same, but one that never increases. Presumably "invariant" here refers to a fact about that number.
Your suggested induction won't work, because you can't assume the initial cells are within any particular part of the grid. The induction, as stated in the hint, will be
on the number of steps. You want to show that something will remain true from one step to the next (that's the induction), which can't be true if everyone is infected.
I don't think there is any general procedure for finding invariants; all I know to do is to use lateral thinking, that is, let your mind wander as you consider the problem from various perspectives. Invention is not easy or automatic.
All I can say, short of the clue that would make it obvious, is that you should
think geometrically about the marked cells -- fill them in, as I mentioned I did, and think about the resulting figure. What geometrical measurements can you make on it, and what is true about the final stage if everyone is infected, but not when only some are?
Also, what do you find to be true about the final state, besides having an empty row? What shape does it have? This won't directly tell you what to do, but may possibly contribute an idea.