On computer role-playing forums, I have seen a lot of general strategy advice regarding difficult group battles ("attack the boss monster first", "start with the highest-damage enemies", etc.). I have decided to see for myself which the optimal tactics is. The answer requires some basic (school-level but nontrivial) mathematics: see http://www.mathlinks.ro/viewtopic.php?t=326811 , scroll down to the remark (the problem turned out to be more or less identical to an American Math. Monthly question which is older than CRPG).
Is it possible to brute-force a combination lock by repeatedly changing a digit without checking one and the same combination several times? (Yes, by induction, at least if you can cycle every digit all the way from 0, 1, 2, ... to 9 and back to 0. If you cannot move between 9 and 0 without going through the intermediate digits, then no, by a semi-invariant argument. The keyword here is Hamiltonian path. If none exists, the next natural question is how to find a path through every vertex of minimal length...) And as we are talking about Hamiltonian paths, Euler paths can be interesting as well...
Huffman coding. It's in your base compressing your files.
For some reason I never understood, many people not particularly close to mathematics seem to be fascinated by Rubik's cube. As opposed to some other popular riddles like Sudoku, this one becomes more or less trivial once one knows the maths behind it.
Huh, the four-color theorem has not been mentioned yet? This is the best example for the notion of beautiful vs. ugly in mathematics that comes into my mind. The five-color theorem is not difficult and rather nice to prove; the only proofs of the four-color theorem known go the "classify and solve for hundreds of particular cases" way. Mathematics is probably the only science where people care for the difference.
The isoperimetric inequality, with all of its, sorry for the pun, variations (such as the case of a curve in a half-plane with two given ends).
You want to encrypt a message in a way that each of $n$ persons gets a key such that any $k$ of them can, in a joint effort, unambiguously decrypt the it, while any $k-1$ will not have the slightest idea about the message (i. e., every possible message including gibberish will be equiprobable). It's called Shamir's Secret Sharing.
No comments:
Post a Comment