Talk:Imo 2009 q6 - Revision history

Mark Bennet: Adding reference to proof #5

2009-07-25T17:18:43Z

Adding reference to proof #5

← Older revision		Revision as of 10:18, 25 July 2009
Line 3:		Line 3:
	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].		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.		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. An 'end' version of this now appears as proof #5 (which is very similar to proof #4).

	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.		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).		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).

Mark Bennet at 08:56, 24 July 2009

2009-07-24T08:56:43Z

← Older revision		Revision as of 01:56, 24 July 2009
Line 1:		Line 1:
	~~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~~. It ~~might generalise more easily eg~~ in ~~more dimensions, where the blocking sets might be more complex~~, and ~~working back from the end might not be so easy~~ to ~~achieve nicely~~. ~~Proof #2 has been converted into~~ an ~~algorithm and programmed in Mathematica (unchecked by me) [http://pastebin~~.~~com/f13130032] by jc, whereas~~ proof #1 is ~~non constructive~~. ~~Proof #1 gives no~~ special status to the ~~longest leap~~.		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. ~~This seems~~ to ~~reduce~~ the ~~number~~ of ~~cases~~, ~~but~~ the argument is ~~not quite~~ so ~~straightforward~~.		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).

Mark Bennet: 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...

2009-07-23T08:36:10Z

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

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. It might generalise more easily eg in more dimensions, where the blocking sets might be more complex, and working back from the end might not be so easy to achieve nicely. Proof #2 has been converted into an algorithm and programmed in Mathematica (unchecked by me) [http://pastebin.com/f13130032] by jc, whereas proof #1 is non constructive. Proof #1 gives no special status to the longest leap.

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. This seems to reduce the number of cases, but the argument is not quite so straightforward.