Well, after the chaos of the previous visit's events, I decided to chance another trip to the H > P club. And sure enough, the management had the players running rings round them so fast they were like Saturn. In an ingenious twist of plot writing, the players had formed cliques with other players who preferred certain openings, and even the bouncers of the management took part in the squabble. I found out the following:
0. An individual may be in any number of cliques, and be a bouncer or a player, it matters not which for the below conditions.
1. All the bouncers alone formed the clique of the Sicilian O'Kelly. "And we are all good chessplayers who know better!" they rallied.
2. All the players alone vehemently insisted the Benko Gambit was better. "And we are all poor chessplayers!" they yelled somewhat ironically.
3. Each individual had a favourite opponent, and an opponent he most despised (not the same person; they're not that insane.)
4. Given any clique, all individuals whose favourite sparring partner/opponent/punchbag was on the clique, formed their own clique.
5. Ditto of 4, just replace "favourite" with "most despised".
6. Given any 2 cliques, there was at least one individual (let's call him Sad) whose favourite opponent thought Sad was on one clique, and whose most depised opponent thought Sad was on the other clique.
Well, this wouldn't do. Amidst the rat-tat-tat of Alekhine's Gun and the table-turning (sacrifices) that formed part of a huge brawl, I talked to the manager (wisely taking no part in this, hiding under a hedgehog.)
Me: "Are all your bouncers sane?!"
Manager: "Yes, at least they're supposed to be! What the heck is going on!"
Me: "Interesting! Do you know, there's at least one person who deserves to be thrown out of this establishment?"
Manager: "You think!?!!"
The Frighteningly Mad Professor Edalpo: Well, this is a rather queer parable. But indeed, the narrator was absolutely right; can you prove that there was some individual who shouldn't be there in that stead? Remember, all bouncers are supposed to be sane, while any poor chessplayers should not be allowed in.
Tuesday, June 21, 2011
Monday, June 20, 2011
What
I believe separately in all the following statements:
- Sane people have true beliefs.
- Insane people have false beliefs.
- Questions are asked only by questioners, who may be sane or insane.
- Type A questioners ask questions that they believe the answer to which must be true. Type B, false.
- Questioners may be sane or insane.
- Everyone utters what they believe is true.
Well then. Hello. So, I believe you know that I am insane? I'd have to be to be posting here, after all. So, to alleviate the boredom spent in the land of the mushroom clouds, here is a nice little set of questions, adapted from a little book of such.
So I took a little stroll to the H > P chess club down the street, where they had a couple of sane and insane players. Some were good players, some poor players. The good players believed the value of H > P, the poor ones believed H =< P. Due to the name of the chess club, it was obvious that the management would kick out the dissenters, but they were doing a lousy job of it! Can you spot all the infidels/heretics/cannon-lovers from the following interactions? [The management, represented by M, are all sane type As.]
M: You seem to be a good player.
Turtler: Thanks, but I believe I'm quite poor at this, really. Do bings move like queens?
M: *facepalms* [To M's opponent, Sacr] Is that why you're losing?
Sacr: I'll be kippered, 'tis so! Aren't you a smart one, laddie! I must be 'orrible at chess to not pick that up!
Turtler [To M]: You're saying bings don't move like queens?
M: *sigh* Am I the type who could lie about that? Now, if you're not convinced, ask him.
C. King: Do you believe I am the type who could ask you if you're insane?
Turtler: He's talking like a nutcase.
M: Tell it to him, CK. Just leave me out of this madhouse. *walks away*
C. King: You're a rather poor player to get into this position.
Turtler: For a good player, you're thoroughly insane. I'm winning!
Sacr [To Turtler]: Who're you to judge, madman?
*fight* *All 3 were thrown out for rowdiness*
The Frighteningly Sane Doctor Tarrfether: So, is everyone a good player? Or were there poor players? Am I the type who could ask you these questions? Am I sane? Are you? Is the writer of this post? [All can be answered.]
Thursday, May 12, 2011
Big numbers
We once learned to count, and for a while, 10 seemed like a big number. Then 100 seemed the limit of numbers, until one thousand came...
As we learn how to count without a limit (you do know what forty-five thousand, six hundred and seventy-eight plus one is right...), it seems that we have mastered all ways of expressing numbers, no matter how big. Yet, this is often nearly not the case in practice. When writing out the rest mass of an electron, we do not write 0.000000000000000000000000000000911 kg. (Well usually we don't, don't be a weird person)
Instead, we use a more powerful, space saving notation for numbers of this small magnitude: 9.11*10^-31. Neat. This also works for larger numbers, like 3.14*10^8=314000000. Looks perfect, but is not quite the best yet.
This is also clearly a use (abuse) of the power notation, where a^b= a*a*a*a*a*a... b times. So how about we get a little creative.
Note:
a*b = a+a+a+a+a+a+a+a... b times
a^b = a*a*a*a*a*a*a*a... b times
We shall define tetration as a b, where the power is applied b times. And we notice that we can extend it further. Hmm... Conway chain notation... ...
Too mind-bogglingly big, and suspect usefulness. Ah well. But anyway, a rather skimpy list of functions in order of bigginess:
+ < */polynomial < ^ < ! < tetration
As we learn how to count without a limit (you do know what forty-five thousand, six hundred and seventy-eight plus one is right...), it seems that we have mastered all ways of expressing numbers, no matter how big. Yet, this is often nearly not the case in practice. When writing out the rest mass of an electron, we do not write 0.000000000000000000000000000000911 kg. (Well usually we don't, don't be a weird person)
Instead, we use a more powerful, space saving notation for numbers of this small magnitude: 9.11*10^-31. Neat. This also works for larger numbers, like 3.14*10^8=314000000. Looks perfect, but is not quite the best yet.
This is also clearly a use (abuse) of the power notation, where a^b= a*a*a*a*a*a... b times. So how about we get a little creative.
Note:
a*b = a+a+a+a+a+a+a+a... b times
a^b = a*a*a*a*a*a*a*a... b times
We shall define tetration as a
Too mind-bogglingly big, and suspect usefulness. Ah well. But anyway, a rather skimpy list of functions in order of bigginess:
+ < */polynomial < ^ < ! < tetration
Monday, April 4, 2011
Saturday, March 26, 2011
Number theory
I found a nice Number Theory question, so for those people who want to attack it directly, here it is:
Prove that exp 2^2(x) is eventually constant mod n (as x increases), where n is an arbitrary positive integer.
But since I expect few to solve it from there (main because of notation), I guess I should explain the weird notation.
exp 2^2(x) actually came from my interpretation of the Wikipedia article (wanted to add Knuth's up arrows, but I'm a lazy person). So what it's supposed to mean is 2^2^2^2..., with x number of 2s. This might not be standard notation, but it's what I got from Wikipedia.
Next mod n, for those who don't know, is basically asking what the remainder when the number is divided by n, eg 42=19 (mod 23), and 31 = 5 (mod 26).
So before I go on hinting like a maniac, it's time to talk about number theory in general. Number theory, in general, talks about the properties of integers. For example, number theory attempts to describe the properties of primes. However, Wikipedia lists at least 5 fields of number theory, such as algebraic number theory. In general, fields such as analytic number theory are more for research problems, which are still relatively open problems, but elementary number theory has a large number of solved problems which have elegant solutions and are light to solve (well, not as bad as researching a problem for months).
Number theory is rather interesting; when you look at a problem, it's hard to tell whether it might be easy or hard, with some messes quickly reducing to workable expressions, but stuff like proving that x^n+y^n=z^n has no integer solutions for n>=3 looks simple, but involves elliptic curves (see Fermat's Last Theorem). However, in this case, it both looks easy and is pretty doable.
Now, for people who have done some kind of number theory before, for the original question in this post, it helps to define it as a recurrence relation, with a1=2 and a2=2^a1 = 2^2 = 4. Then it suffices to prove that 2^ai = 2^a(i+1) (mod n) for any sufficiently large i.
Next, it helps to know Euler's Theorem, but is completely unnecessary (really).
The next important thing to know is the idea of induction. The general format of induction can go something like this: Student 1 is a boy. If Student i is a boy, then Student i+1 must necessarily be a boy as well. Therefore, Student 2 is a boy, therefore Student 3 is a boy, et cetera. We thereby conclude that Students 1 to the last student are all boys.
There is a similar form of induction, which works backwards. This works by say, concluding that Student i is a boy if Student i-1 is a boy. Student i-1 is a boy if Student i-2 is a boy, and this traces all the way back to Student 1, who is a boy. We are done.
An important thing to know is that the sequence 2, 4, 8, 16, 32, 64, ... enters a cycle mod n. To prove this, the most primitive way I can think of is to think of the ith term and the (i+1)th term. Say the remainder when i/n is x. This means that 2^i=kn+x, for some integer k. Therefore, 2^(i+1) = 2kn+2x, which when divided by n, gives a remainder solely defined by x. Hence, one can think of walking the remainders like a path, and with finite number of destinations to visit, one must eventually go back to the same point. Since the direction from any starting point is uniquely defined (ie you're forced to walk the same way from any same point), once you get back to the same point, there is no way you're ever going to break out from the cycle.
The substep to prove is that the length of the cycle is less than n. (Hint: consider 0 mod n)
Bad Spoiler Alert: (highlight to see)
Following this, you may realise that if the length of the cycle mod n is x, then the value of 2^i mod n is dependent on the value of 2^i mod x, where x is smaller than n. This is the induction step.
Don't forget your base case when induction though.
P.S.: This post is shorter than I expected it to be, my essay spamming skills must have deteriorated. Ohnoes.
Prove that exp 2^2(x) is eventually constant mod n (as x increases), where n is an arbitrary positive integer.
But since I expect few to solve it from there (main because of notation), I guess I should explain the weird notation.
exp 2^2(x) actually came from my interpretation of the Wikipedia article (wanted to add Knuth's up arrows, but I'm a lazy person). So what it's supposed to mean is 2^2^2^2..., with x number of 2s. This might not be standard notation, but it's what I got from Wikipedia.
Next mod n, for those who don't know, is basically asking what the remainder when the number is divided by n, eg 42=19 (mod 23), and 31 = 5 (mod 26).
So before I go on hinting like a maniac, it's time to talk about number theory in general. Number theory, in general, talks about the properties of integers. For example, number theory attempts to describe the properties of primes. However, Wikipedia lists at least 5 fields of number theory, such as algebraic number theory. In general, fields such as analytic number theory are more for research problems, which are still relatively open problems, but elementary number theory has a large number of solved problems which have elegant solutions and are light to solve (well, not as bad as researching a problem for months).
Number theory is rather interesting; when you look at a problem, it's hard to tell whether it might be easy or hard, with some messes quickly reducing to workable expressions, but stuff like proving that x^n+y^n=z^n has no integer solutions for n>=3 looks simple, but involves elliptic curves (see Fermat's Last Theorem). However, in this case, it both looks easy and is pretty doable.
Now, for people who have done some kind of number theory before, for the original question in this post, it helps to define it as a recurrence relation, with a1=2 and a2=2^a1 = 2^2 = 4. Then it suffices to prove that 2^ai = 2^a(i+1) (mod n) for any sufficiently large i.
Next, it helps to know Euler's Theorem, but is completely unnecessary (really).
The next important thing to know is the idea of induction. The general format of induction can go something like this: Student 1 is a boy. If Student i is a boy, then Student i+1 must necessarily be a boy as well. Therefore, Student 2 is a boy, therefore Student 3 is a boy, et cetera. We thereby conclude that Students 1 to the last student are all boys.
There is a similar form of induction, which works backwards. This works by say, concluding that Student i is a boy if Student i-1 is a boy. Student i-1 is a boy if Student i-2 is a boy, and this traces all the way back to Student 1, who is a boy. We are done.
An important thing to know is that the sequence 2, 4, 8, 16, 32, 64, ... enters a cycle mod n. To prove this, the most primitive way I can think of is to think of the ith term and the (i+1)th term. Say the remainder when i/n is x. This means that 2^i=kn+x, for some integer k. Therefore, 2^(i+1) = 2kn+2x, which when divided by n, gives a remainder solely defined by x. Hence, one can think of walking the remainders like a path, and with finite number of destinations to visit, one must eventually go back to the same point. Since the direction from any starting point is uniquely defined (ie you're forced to walk the same way from any same point), once you get back to the same point, there is no way you're ever going to break out from the cycle.
The substep to prove is that the length of the cycle is less than n. (Hint: consider 0 mod n)
Bad Spoiler Alert: (highlight to see)
Following this, you may realise that if the length of the cycle mod n is x, then the value of 2^i mod n is dependent on the value of 2^i mod x, where x is smaller than n. This is the induction step.
Don't forget your base case when induction though.
P.S.: This post is shorter than I expected it to be, my essay spamming skills must have deteriorated. Ohnoes.
Sunday, March 6, 2011
Yet another 26 move chess match
START{
1. H2+3 p3+1 2. P3+1 h2+3 3. C2.1 c2.1
4. R1.2 c8.9 5. C8.7 h8+7 6. C7+3 e3+5
7. C7+1 r9+1 8. H8+7 r1.2 9. E7+5 r9.4
10. C7.3 h3+4 11. A6+5 r2+7 12. R9.6 r2.3
13. H3+4 h4+6 14. C1.7 r4+8 15. A5-6 h6-7
16. R2+3 c1+4 17. C7.9 h++6 18. C9+4 h6+4
19. C9.7 h7+6 20. R2-2 c1+3 21. E5-7 h6+5
22. R2+2 h5-7 23. R2.6 h7+6 24. K5+1 h6-4
25. K5.6 e5+3 26. C7.1 c9.4 }END
1. H2+3 p3+1 2. P3+1 h2+3 3. C2.1 c2.1
4. R1.2 c8.9 5. C8.7 h8+7 6. C7+3 e3+5
7. C7+1 r9+1 8. H8+7 r1.2 9. E7+5 r9.4
10. C7.3 h3+4 11. A6+5 r2+7 12. R9.6 r2.3
13. H3+4 h4+6 14. C1.7 r4+8 15. A5-6 h6-7
16. R2+3 c1+4 17. C7.9 h++6 18. C9+4 h6+4
19. C9.7 h7+6 20. R2-2 c1+3 21. E5-7 h6+5
22. R2+2 h5-7 23. R2.6 h7+6 24. K5+1 h6-4
25. K5.6 e5+3 26. C7.1 c9.4 }END
Just a chess match
1. H2+3 c2.5 2. H8+7 p7+1 3. C8.9 h2+3
4. R9.8 h8+7 5. P7+1 h7+6 6. R8+5 c8+2
7. R8+1 r1.2 8. R8.7 r2+2 9. C2.1 c8-3
10. R1.2 c8.3 11. R7.9 r2+6 12. R9-1 h6+7
13. R9.3 h7+9 14. E3+1 r9+1 15. R3+4 h3-5
16. R3-4 c3+6 17. E1-3 r9.6 18. R3+1 r6+7
19. A4+5 r2.3 20. E7+5 r3.4 21. A5-4 c5.2
22. C9.8 c2.4 23. A6+5 r4.2 24. R2+7 r2+1
25. A5-6 r6.4 26. A4+5 c3+2 }END
4. R9.8 h8+7 5. P7+1 h7+6 6. R8+5 c8+2
7. R8+1 r1.2 8. R8.7 r2+2 9. C2.1 c8-3
10. R1.2 c8.3 11. R7.9 r2+6 12. R9-1 h6+7
13. R9.3 h7+9 14. E3+1 r9+1 15. R3+4 h3-5
16. R3-4 c3+6 17. E1-3 r9.6 18. R3+1 r6+7
19. A4+5 r2.3 20. E7+5 r3.4 21. A5-4 c5.2
22. C9.8 c2.4 23. A6+5 r4.2 24. R2+7 r2+1
25. A5-6 r6.4 26. A4+5 c3+2 }END
Subscribe to:
Posts (Atom)