Can any one aid me with this problem

[AbdelRahmanShady]

I am trying to solve beaver flu problem of mit course of leghman leighton.
I have thought about edges needing to be complete for all class to be infected. No two emty rows or columns. when using induction take n by n piece from top left and try to proof it from there. But until now I cant find invariant. Can any one send the most sutble of hints or even things to search as I dont want to burn the joy of finding solution
By the way not direct hints and general solving tips will be better

 

[Dr.Peterson]

I am trying to solve beaver flu problem of mit course of leghman leighton.
I have thought about edges needing to be complete for all class to be infected. No two emty rows or columns. when using induction take n by n piece from top left and try to proof it from there. But until now I cant find invariant. Can any one send the most sutble of hints or even things to search as I dont want to burn the joy of finding solution
By the way not direct hints and general solving tips will be better

Apparently you are testing our ability to read your mind! Is there a reason you chose to give us only the most subtle of hints about what the problem is?

Please state the problem, as you found it, and show your actual work, so we can have some idea what you are using induction on.

I do find what I suppose is your problem as Problem 6.10 here, but its hint doesn't mention an invariant. So we do need to see the version of the problem you are asking about.

I find other versions here and there, but those places have more than subtle hints, so I presume you haven't looked there, and don't want to.

Without looking at anyone's answers, what I tried to do first was just to play with the problem: Make a grid using a drawing tool and fill in cells with one color at a time, trying to do what it says can't be done, in order to get a sense of what goes wrong. That should suggest a method of attack.

 

[AbdelRahmanShady]

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 strenthening 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

 

[blamocur]

In case it makes you feel better: this problem is too difficult for my brain too

 

[Dr.Peterson]

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.

 

[AbdelRahmanShady]

Ok thanks i once read the one clue is perimetre but i cant use it until now I will try your way and see if i do progress

 

[Dr.Peterson]

Ok thanks i once read the one clue is perimetre but i cant use it until now I will try your way and see if i do progress

Yes, that's the clue; as I said, it's a geometrical measurement. It will not remain constant, but there will be something about it you need to observe. You might just examine the examples you've tried from that perspective.

 

[AbdelRahmanShady]

Ok I will try

 

[Cubist]

Yes, that's the clue; as I said, it's a geometrical measurement. It will not remain constant, but there will be something about it you need to observe. You might just examine the examples you've tried from that perspective.

Great clues! Got it after a few mins of drawing, and thinking about the situations that allow an infected person to infect someone new.

 

[AbdelRahmanShady]

hello, I think I have found the proof.
Start by defining x to be a part of a shape if x is directly up, down, right, or bottom.
Now lets see the sum of perimeters bounded by this shapes
at most it will be k (number of x) * 4 as sharing an edge will decrease perimeter.
lemma 1: after addition of one x by rules of infection perimeter can decrease or remain the same.
Case 1:
if added x is because of x's of the same shape and not connect two shapes.
Will other shapes wont be affected so perimeter stays the same.
And since for a new x to be added it needs atleast two neighbours so putting x there will decrese number of edges by at least two and new x can only increase perimeter by two since two edges of new x will be the shared border with two neghbours so he new x can increase perimeter by a maximum 2 leading to no change in perimeter or decrease.
so sum of perimeters will either decrease or doesnt change.

Case 2:
if added x connects two shapes.
Then any other shapes except these two will remain the same so the perimetres will remain the same.

But for two shapes they will lose at least one edge each, one from each free border now occupied with new x leading to decrease in perimeter by two or perimetre remaining the same
as perimetre of new shape is perimetre of first shape -1 + perimetre of second shape -1 + perimetre added by new x which can at most be two
as two edges is shared will new shape.
so sum of perimetres will remain the same or decrease.
qed.

lemma 2: after any number of x added after 1 time step sum of perimetre will be the same or less.
Proof by induction
base case: 0 x added and peremetre is the same
induction hypothesis: will after k x's added perimetre is the same or less by induction hypothesis and since by lemma 1 adding one x can only decrease perimetre or do nothing ,so after k+1 x's perimetre will still be either the same or less.
qed

lemma 3: after n time steps the perimetre is the same or less.
Proof by induction:
base case: at time 0 no x's added so perimetre is the same
induction hypothesis: after n time steps perimetre is the same or less and adding one time step by lemma 2 can only decrease perimetre or do nothing so n+1 holds
qed.

so at initial state perimetre is at most (n-1) * 4 and after any number of t steps the perimetre will be (n-1)*4 or less.
but final step where all students are infected has perimetre n*4 so it is impossible to reach this state so it is impossible to infect all people.
Is this correct?

 

[Dr.Peterson]

Start by defining x to be a part of a shape if x is directly up, down, right, or bottom.

I don't know what this means. What sort of thing is "x"? What is "a shape"? What does "directly up, down, right, or bottom" mean?

Maybe drawing a picture would help you communicate what you mean.

at most it will be k (number of x) * 4 as sharing an edge will decrease perimeter.

It took me a minute to realize you are defining k as the number of "x", and then referring to the number 4k.

With effort, I can see what you mean by "sharing an edge will decrease perimeter" [from what??]. Someone who doesn't already know how it works would probably be baffled. Again, a picture might help.

I think you have all the right ideas, but you need to state it more clearly in order for others to follow.

 

[AbdelRahmanShady]

I don't know what this means. What sort of thing is "x"? What is "a shape"? What does "directly up, down, right, or bottom" mean?

Maybe drawing a picture would help you communicate what you mean.


It took me a minute to realize you are defining k as the number of "x", and then referring to the number 4k.

With effort, I can see what you mean by "sharing an edge will decrease perimeter" [from what??]. Someone who doesn't already know how it works would probably be baffled. Again, a picture might help.

I think you have all the right ideas, but you need to state it more clearly in order for others to follow.

I meant with a shape is the something to take perimetre of so I defined an x (imfected student) to be part of shape if he has any neighbouring infected students of this particular shape in north east west south directions.
About k i defined to be number of infected students added.
And about perimetre decreasing it is because of the fact that adding an infected student will block borders of other x's it is touching thats what i mean by perimetre decreasing and it remains the same if borders of new x compernsate for lost borders from adding it and the reason at least two borders will be lost as new x will only be added if has two neghbours so two borders to be lost so best the new shape can do is compensate for lost perimetre not increase it.
Did that make it more clear?
Is my solution correct now?

 

[Dr.Peterson]

I meant with a shape is the something to take perimetre of so I defined an x (infected student) to be part of shape if he has any neighbouring infected students of this particular shape in north east west south directions.
About k i defined to be number of infected students added.
And about perimetre decreasing it is because of the fact that adding an infected student will block borders of other x's it is touching thats what i mean by perimetre decreasing and it remains the same if borders of new x compensate for lost borders from adding it and the reason at least two borders will be lost as new x will only be added if has two neighbours so two borders to be lost so best the new shape can do is compensate for lost perimetre not increase it.
Did that make it more clear?
Is my solution correct now?

In order to describe clearly what you are talking about, you might mention the square cells in which x is found (that is, cells representing infected students), so that the shapes you refer to are polygons consisting of adjacent cells. The perimeter consists of the edge segments of those cells that lie between infected and uninfected cells.

But what you have said here is definitely clearer.

As I sometimes point out, a proof is essentially a persuasive essay, and that requires writing that is as clear as possible. Assume the reader doesn't know what you are thinking, and needs help to understand your ideas.

 

[AbdelRahmanShady]

In order to describe clearly what you are talking about, you might mention the square cells in which x is found (that is, cells representing infected students), so that the shapes you refer to are polygons consisting of adjacent cells. The perimeter consists of the edge segments of those cells that lie between infected and uninfected cells.

But what you have said here is definitely clearer.

As I sometimes point out, a proof is essentially a persuasive essay, and that requires writing that is as clear as possible. Assume the reader doesn't know what you are thinking, and needs help to understand your ideas.

Thanks that is what I meant

 

[AbdelRahmanShady]

By the way how would any body think of taking perimetre it doesnt make sence at first notice. Furthermore I thught by perimetre you meant number of x's that are on border not their edges which clearly change and discovered the border thing by coincidence while trying after your hints.
So my question what lead to you trying perimetre. It doesnt appear as a rational guess until you try it.

 

[Dr.Peterson]

By the way how would any body think of taking perimetre it doesnt make sence at first notice. Furthermore I thught by perimetre you meant number of x's that are on border not their edges which clearly change and discovered the border thing by coincidence while trying after your hints.
So my question what lead to you trying perimetre. It doesnt appear as a rational guess until you try it.

Probably what led me in that direction was observing that the end result of the spread in each example I tried was one or more rectangles; the shape evolved toward convex figures, which have a smaller perimeter relative to their area.

But this sort of thing generally comes to you, if at all, by trying out many ideas -- "lateral thinking".

 

[AbdelRahmanShady]

I mean why you would even consider perimetre over trying to prove it dirrctly ysing induction or looking at properties of final state not found in in initial state. It is naive and didnt work but it doesnt make sense to me. After all i thought of problem for two weeks. Even made a program to draw different grids after time steps.
and one last thing beside not being clear to someone who doesnt know the proof, is my proof complete and correct or is it missing something

 

[Dr.Peterson]

I mean why you would even consider perimetre over trying to prove it dirrctly ysing induction or looking at properties of final state not found in in initial state. It is naive and didnt work but it doesnt make sense to me. After all i thought of problem for two weeks. Even made a program to draw different grids after time steps.
and one last thing beside not being clear to someone who doesnt know the proof, is my proof complete and correct or is it missing something

It's a hard problem! Sometimes, after considering everything that makes sense, you have to try things that don't (yet) make sense to you. This is the nature of proof. (Many proofs that we consider obvious now are so only because someone spent a lifetime trying things, and the trick they discovered is now considered standard.)

Could you write your proof again, including the suggestions I made, so we can see for sure that it is correct? My overall sense was that it was correct, but I didn't try examining every detail, because that was too hard.

 

[AbdelRahmanShady]

It's a hard problem! Sometimes, after considering everything that makes sense, you have to try things that don't (yet) make sense to you. This is the nature of proof. (Many proofs that we consider obvious now are so only because someone spent a lifetime trying things, and the trick they discovered is now considered standard.)

Could you write your proof again, including the suggestions I made, so we can see for sure that it is correct? My overall sense was that it was correct, but I didn't try examining every detail, because that was too hard.

Ok I will write on a piece of paper to be more clear.
Besides that is the leghman leghton lecture the one this problem set is based of needs specific prequisites. I am at grade 11 in high school but looks math on internet. is this enough to watch lectures and solve h.w problems or do I need a more of a solid foundation in a specific thing.
Anyway thanks too much for help