On Sun, Nov 13, 2011 at 12:04 PM, Marc LeBrun <mlb@well.com> wrote:
Could anyone supply me with elementary examples that illustrate the idea of a non-constructive proof, for those with a "Martin Gardner reader" level of mathematical sophistication that also has a not-too-trivial but reasonably easily-verified case? For example a non-constructive proof that some set of numbers is non-empty, along with an example of such a number that can be fairly easily checked? Thanks!
This too is in a slightly different direction than the other examples given, but I think it might prove useful to you: Demonstrate that the game of Chomp <http://en.wikipedia.org/wiki/Chomp> has a winning strategy for the first player while making the point that finding an actual strategy is much more difficult and in most cases remains a mystery. Once the (fairly simple) rules of the game are laid down, it's pretty easy to convince the audience that either the first player has an opening move that stumps the opponent, or they don't; in the latter case, the opponent has a winning response to anything the first player throws at them. But this latter case is seen to be impossible by "strategy stealing": if that were the case, the second player could respond to a "nip the corner" first move, and that response might well have been played by the first player to begin with. Thus, there is a strategy, but we don't know what it is. A simple case where it *is* known is the square board, and you can probably show one also for some small board like the 2x3, but it shouldn't fail to impress your audience that we have just logically shown that there must be a winning play for the 17x29 board but we have no idea what it is - and probably nobody else does either.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun