Talk:Imo 2009 q6: Difference between revisions
Mark Bennet (talk | contribs) New page: It seems to me that proof #1 says 'let's make as much progress as possible', and by working with sets of partial paths extends the counting approach used in proof #2 case 4 to do more work... |
Mark Bennet (talk | contribs) No edit summary |
||
| Line 1: | Line 1: | ||
The approach adopted in proof #1 is 'let's make as much progress as possible, and then show that we can do an extra step'. It introduces an observation fundamental to a number of successful strategies- that if I can pass k mines in k leaps (with k>0), I have only n-k-1 mines left to jump and n-k leaps to do it. So if I can do smaller problem, I can do this one - which sets up an induction. In proof #1 this is used to provide constraints on an impossible minefield, and then the number of options available for paths is shown to overwhelm the constraints. This is the most sophisticated proof so far, in that it does not give the longest leap a special status. It looks set up to deal with more challenging generalisations of the problem. | |||
The discussion on the Mathlinks Math Forum here [http://www.mathlinks.ro/Forum/viewtopic.php?t=289051] has another proof a bit similar to #2 where the inductive step is to remove the mine closest to the beginning (the proof by qwerty414 as stated has it at the end) and to look at two cases: the first where doing the longest leap first lands on one of the remaining mines, and the second where it doesn't. | Proof #2 uses a greedy approach - try to make the longest leap. Case 4 of proof #2 is akin to the approach in proof #1, though it is set up differently. The description of the approach in proof #2 suggests that there are essentially two cases to deal with (though the trivial case where the induction works might be considered a third) and proof #3 gives a two case approach which was discovered by programming proof #2 and being careful over the details which is set out here [http://www.erisian.com.au/wordpress/2009/07/23/solving-hard-maths-olympiad-problems]. | ||
The discussion on the Mathlinks Math Forum here [http://www.mathlinks.ro/Forum/viewtopic.php?t=289051] has another proof a bit similar to #2 where the inductive step is to remove the mine closest to the beginning (the proof by qwerty414 as stated has it at the end) and to look at two cases: the first where doing the longest leap first lands on one of the remaining mines, and the second where it doesn't. | |||
Proof #2 has a 'working from both ends' feel - the dual approach in proof #4 uses the inductive hypothesis to get as far as possible without using the longest leap, and this automatically collapses cases 2.2 and 3 of proof #2. What can go wrong? Well we can land on the last mine (we know we can dodge all but one) - and we swap in the longest leap to clear it, or we land on a mine with the last leap and still have some to clear - in which case the counting argument of proof #2 case 4 is used. | |||
Useful counterexamples to false proofs can be constructed by putting all the mines together in some part of the minefield. For the jump set {1,2 ... n} this forces the longest leap, so the proof needs to make sure that the longest leap is available at this point. It is also possible to mine all but one of the possible first leaps (or last ones). | |||
Revision as of 00:56, 24 July 2009
The approach adopted in proof #1 is 'let's make as much progress as possible, and then show that we can do an extra step'. It introduces an observation fundamental to a number of successful strategies- that if I can pass k mines in k leaps (with k>0), I have only n-k-1 mines left to jump and n-k leaps to do it. So if I can do smaller problem, I can do this one - which sets up an induction. In proof #1 this is used to provide constraints on an impossible minefield, and then the number of options available for paths is shown to overwhelm the constraints. This is the most sophisticated proof so far, in that it does not give the longest leap a special status. It looks set up to deal with more challenging generalisations of the problem.
Proof #2 uses a greedy approach - try to make the longest leap. Case 4 of proof #2 is akin to the approach in proof #1, though it is set up differently. The description of the approach in proof #2 suggests that there are essentially two cases to deal with (though the trivial case where the induction works might be considered a third) and proof #3 gives a two case approach which was discovered by programming proof #2 and being careful over the details which is set out here [1].
The discussion on the Mathlinks Math Forum here [2] has another proof a bit similar to #2 where the inductive step is to remove the mine closest to the beginning (the proof by qwerty414 as stated has it at the end) and to look at two cases: the first where doing the longest leap first lands on one of the remaining mines, and the second where it doesn't.
Proof #2 has a 'working from both ends' feel - the dual approach in proof #4 uses the inductive hypothesis to get as far as possible without using the longest leap, and this automatically collapses cases 2.2 and 3 of proof #2. What can go wrong? Well we can land on the last mine (we know we can dodge all but one) - and we swap in the longest leap to clear it, or we land on a mine with the last leap and still have some to clear - in which case the counting argument of proof #2 case 4 is used.
Useful counterexamples to false proofs can be constructed by putting all the mines together in some part of the minefield. For the jump set {1,2 ... n} this forces the longest leap, so the proof needs to make sure that the longest leap is available at this point. It is also possible to mine all but one of the possible first leaps (or last ones).
