-
Riddle Thread
Number theory in 21 minutes
I'm a fan of riddles with mathematical or programming background ("one guard always tells the truth, one guard always lies, and the third guard stabs people who ask tricky questions"). Maybe you like those too. Anyway, this is my favorite, solvable by anyone who finished school:
p^2 - 1 is divisible by 24 if p is a prime number greater than 3.
Example:
5^2 - 1 = 1*24
7^2 - 1 = 2*24
11^2 - 1 = 5*24
Why is that?
Enjoy,
Philip
-
Number theory in 21 minutes
> Why is that?
Well for one all prime numbers are odd. And we all know given n (an odd number) n - 1 is even. Providing n > 1 :) (depending on your definition of zero's oddness).
Other than that, it's just a pattern. You could of course replace 24 with any other number that 24 is divisible by (der).
Now all you have to do is prove it inductively -- just to make sure :)
-
Number theory in 21 minutes
Quote:
Originally Posted by
zacs7
Well for one all prime numbers are odd.
Wrong. 2 is an even prime number.
Quote:
And we all know given n (an odd number) n - 1 is even.
Right. So?
Greets,
Philip
-
Number theory in 21 minutes
Quote:
Originally Posted by Snafuist
Wrong. 2 is an even prime number.
I think zacs7 forgot the phrase "within the given range" or "greater than 3".
-
Number theory in 21 minutes
> 2 is an even prime number.
And you specified a range > 3. Last time I checked 2 < 3.
> Right. So?
What do you mean so? It's a key property of the pattern.
-
Number theory in 21 minutes
Quote:
Originally Posted by zacs7
What do you mean so? It's a key property of the pattern.
Right, but honestly I do not see how it proves the property. Could you elaborate?
-
Number theory in 21 minutes
I never said it proved it :)
-
Number theory in 21 minutes
Take n where
p = 2*n + 1
p^2 - 1 = (2*n + 1)*(2*n + 1) - 1 = 4*n*n + 2*2*n + 1 - 1
= 4*n*n + 4*n = 4*(n*n + n)
So n*n + n = n*(n+1) must be dividable by 6.
If n is not dividable by 2, then n+1 is. So now we need to proof n*(n+1) is dividable by 3.
If n is not dividable by 3, and n+1 is not dividable by 3, then n+2 must be. Then:
(n+2)*2 = 2*n + 4
must be dividable by 3. And thus
2*n + 4 - 3 = 2*n + 1
must be dividable by 3. However, p = 2*n + 1, and p is a prime number so can't be dividable by 3.
q.e.d.
-
Number theory in 21 minutes
Right, EVOEx!
Your proof is technically perfect, but it hides the fundamental ideas, so I will present a simpler version:
From school, we remember that p^2 - 1 == (p-1)(p+1)
We want to show that (p-1)(p+1) is dividable by 24, i.e. it's dividable by 2^3 and 3 (the prime factors of 24).
Now have a look at the three consecutive numbers (p-1), p and (p+1). We know that p is a prime > 3, so (p-1) and (p+1) are even. And what's more, if you have two consecutive even numbers, one of them is also dividable by 4. Thus, (p-1)*(p+1) is dividable by 2*4.
Another simple fact about numbers is that of three consecutive integers, one of them is dividable by 3. This is not p (as p is a prime greater than 3), so it must be either (p-1) or (p+1).
Hence, (p-1)*(p+1) is dividable by 2*4 and by 3, i.e. 2*3*4, i.e. 24.
Greets,
Philip
-
Number theory in 21 minutes
Heh. That really was a lot easier. ;)
-
Riddle #2: one night in the UAE
This is taken from my exam in "system architecture":
Consider the number abcabc, where a, b and c are arbitrary digits. abcabc is always dividable by 13:
123123 = 13 * 9471
597597 = 13 * 45969
666666 = 13 * 51282
Why is that?
Greets,
Philip
-
Riddle #2: one night in the UAE
Code:
a_number_in_the_form_of(abcabc) =
= c + 10 * b + 100 * a + 1000 * c + 10000 * b + 100000 * a =
= 1001 * c + 10010 * b + 100100 * a =
= 1001 * (c + 10 * b + 100 * a) =
= 13 * 77 * (c + 10 * b + 100 * a)
-
Riddle #2: one night in the UAE
Right, anon!
Or to put it in simpler terms:
abcabc = 1001*abc, and 1001 is dividable by 13.
Where do you guys get those byzantine explanations? :P
Greets,
Philip
-
Riddle #2: one night in the UAE
Quote:
Originally Posted by
Snafuist
Right, anon!
Or to put it in simpler terms:
abcabc = 1001*abc, and 1001 is dividable by 13.
Where do you guys get those byzantine explanations? :P
Greets,
Philip
Actually, that was the proof I wanted to provide before I read the rest of the posts. However, after typing it in my calculator, I found that "10001" wasn't dividable by 13. I always make those kinds of stupid mistakes....
-
Riddle #2: one night in the UAE
Quote:
I always make those kinds of stupid mistakes....
Well, you're not alone. My inability to perform mental arithmetic is famous by now...
Your brother,
Philip
-
Riddle #3: three dwarfs, two paths, one life
In my circle of friends, this one is well-known by now, but maybe you haven't heard of it already:
You walk along a path until you reach a crotch. One way leads to your destination, the other to sudden death, but you don't know which one is right. Fortunately, there is a house with three dwarfs. One always tells the truth (A), one always lies (B), and one sometimes tells the truth and sometimes lies (C).
How do you find out the right path with only two questions?
Greets,
Philip
-
Riddle #3: three dwarfs, two paths, one life
I only knew this one without C and only one question. But it's still fairly similar ;).
-
Riddle #2: one night in the UAE
My question is why was this on a "systems architecture" exam...it seems quite tangential to the material that should be taught in a systems architecture class. :)
-
Riddle #3: three dwarfs, two paths, one life
Actually, I thought about it... I was used to saying, as answer "Which direction would the other say I'd have to go". But I think this one is possible with one question:
- Which way would the one of you that always speaks the truth say you would say I'd have to go?
The one who always speaks the truth would speak the truth about the way and point the proper direction.
The one who always lies knows the one who would speak the truth would tell he'd say the wrong direction. But he lies about that fact, so he points to the proper direction.
The one who sometimes speaks the truth is undecided.
So two always point to the proper way.
-
Riddle #3: three dwarfs, two paths, one life
I'd just choose which direction to take myself, and then hope I took the right one, that way I don't have to go through the hassle with the dwarves ;)
-
Riddle #2: one night in the UAE
Quote:
Originally Posted by
DavidP
My question is why was this on a "systems architecture" exam...it seems quite tangential to the material that should be taught in a systems architecture class. :)
Because back then, our prof told us all questions from the exam in advance, except this one. He didn't want to give 100% of the points to someone who merely learned everything by heart.
BTW, the number of people that managed to pass the exam was below 50%. My prof's theory was that everyone who learns the stuff will pass anyway, and everyone else won't learn enough even if they know exactly what to learn. He was proven right: the overall result was comparable to his other exams.
Greets,
Philip
-
Number theory in 21 minutes
Damn... My argument to why I don't understand any of this is... I haven't finished school xP Now make the algorithm for randomness for me >: D
-
Number theory in 21 minutes
Well that makes for an interesting optimization for large prime number searches. I wonder what percentage of workload it would reduce to first check that a number met that particular criteria.
-
Riddle #3: three dwarfs, two paths, one life
Quote:
Originally Posted by
EVOEx
Which way would the one of you that always speaks the truth say you would say I'd have to go?
The one who always speaks the truth would speak the truth about the way and point the proper direction.
The one who always lies knows the one who would speak the truth would tell he'd say the wrong direction. But he lies about that fact, so he points to the proper direction.
The one who sometimes speaks the truth is undecided.
So two always point to the proper way.
Right. Now you have one question left to determine who's (C), or who's not.
This is the interesting part. Without (C), my grandma would solve this riddle in no time :P
Greets,
Philip
-
Riddle #3: three dwarfs, two paths, one life
I guess that would work...
I would have just used sequential Bayes :)
(I.E. ask two dwarfs which is the right path and use sequential Bayes to calculate the probability of each being the actual correct one)
-
Riddle #3: three dwarfs, two paths, one life
Why? Only one person will answer? :P I thought just ask all three of them at the same time. It's really just one question... And if all three of them answer, you're done.
-
Number theory in 21 minutes
Quote:
Originally Posted by
abachler
Well that makes for an interesting optimization for large prime number searches. I wonder what percentage of workload it would reduce to first check that a number met that particular criteria.
A number is dividable by 2 and 3 if it is dividable by 24, so checking if 2 or 3 divides a given number is probably much faster (and tells you more about the number).
Greets,
Philip
-
Riddle #3: three dwarfs, two paths, one life
Quote:
Originally Posted by
EVOEx
Why? Only one person will answer? :P I thought just ask all three of them at the same time. It's really just one question... And if all three of them answer, you're done.
I guess there's only one dwarf supposed to answer. But if all three were allowed to answer, what would you ask?
Greets,
Philip
-
Riddle #3: three dwarfs, two paths, one life
Like I said before:
Which way would the one of you that always speaks the truth say you would say I'd have to go?
The one who always speaks the truth would speak the truth about the way and point the proper direction.
The one who always lies knows the one who would speak the truth would tell he'd say the wrong direction. But he lies about that fact, so he points to the proper direction.
The one who sometimes speaks the truth is undecided.
So two always point to the proper way.
If all three answer, two point you to the right way, and the other you don't know... And the riddle doesn't say only one dwarf will answer your question :P.
-
Riddle #3: three dwarfs, two paths, one life
Well, now you can imagine why nobody will let me do mental arithmetic...
I hereby establish that only one dwarf is allowed to answer per question.
Greets from Graz,
Philip
-
Hey that's pretty cool, though. Nice one.
-
Riddle #3: three dwarfs, two paths, one life
-
Riddle #3: three dwarfs, two paths, one life
There's a whole book of these problem called Knights and Knaves, something like this:
Knights and Knaves: Knights and Knaves Logic Puzzle
Knights always tell the truth and Knaves always lie. There was a second book about Humans and Vampires. Humans always tell the truth, vampires always lie, insane humans think they are telling the truth but lie, and insane vampires think they are lying but always tell the truth. Then there's a bunch of riddles of this sort.
If you like this, also check out The Puzzling Adventures of Dr. Ecco
-
Number theory in 21 minutes
Its faster to just check if a number, modulo 6469693230 has a prime remainder, since all prime numbers do.
-
Number theory in 21 minutes
The greatest common factor explanation of this is great
-
Number theory in 21 minutes
>> Its faster to just check if a number, modulo 6469693230 has a prime remainder, since all prime numbers do.
Are you sure about that? Can you elaborate?
-
Riddle #3: three dwarfs, two paths, one life
Ok, just to bring this to an end:
First, you ask a random dwarf: "Who of your brothers lies more often?"
If you happen to ask A, he will correctly point to C.
If you happen to ask B, he will incorrectly point to C.
If you happen to ask C, he will randomly point to either A or B.
In either case, the dwarf not asked and not pointed to is not C.
Ask this dwarf the following question: "Which path would the dwarf suggest who is the exact opposite of you?"
If you ask A, he will tell the truth and provide you with the path that B would've suggested, i.e. the wrong path.
If you ask B, he will lie and provide you with the path that A would'nt have suggested, i.e. the wrong path.
So you take the other path.
Greets,
Philip
-
Riddle #3: three dwarfs, two paths, one life
hmm... but that seems to assume that the dwarves are benevolent. If they are (or more accurately, could be) malicious, then you have to phrase that second question more explicitly to your advantage.
-
Riddle #5: more dwarfs
There are seven dwarfs, each one wearing a unique hat. A wind blows off the hats. The dwarfs start running after their hats and each dwarf puts on the first hat that he manages to catch. Eventually every dwarf has a hat again.
What is the probability that exactly six dwarfs are wearing their own hat now?
Greets,
Philip
-
Riddle #3: three dwarfs, two paths, one life
Quote:
Originally Posted by
laserlight
hmm... but that seems to assume that the dwarves are benevolent. If they are (or more accurately, could be) malicious, then you have to phrase that second question more explicitly to your advantage.
Right. I already had several discussions about that. The problem arises due to the inexactness of most natural languages. The most obvious solution is to ask a more concise (and more awful) question. Personally, I prefer adding the proposition to the riddle that the dwarfs are benevolent. I didn't do it in the first place because it only distracts from the intended solution, but it's good that you pointed it out.
Greets,
Philip
-
Riddle #3: three dwarfs, two paths, one life
Quote:
Originally Posted by Snafuist
The problem arises due to the inexactness of most natural languages.
I don't think so. I think that it is merely an unstated assumption. I wanted to propose the solution of just capturing the dwarves and dragging them in a direction to see their response, but then I realised that I could not be sure that the dwarves were not so bored with their existence that they intended suicide, hence I would have to ask them questions anyway :o
-
Riddle #4: if-statement considered harmful
Oops, I skipped #4, so here it is.
Consider the following program:
Code:
int cmp(int a, int b)
{
if(a > b) {
return 1;
} else if(a < b) {
return -1;
} else {
return 0;
}
}
Can you come up with an implementation that doesn't use conditionals, i.e. if, for, while, switch?
Greets,
Philip
-
Riddle #4: if-statement considered harmful
I presume that includes ternary operator, and that this is either C or C++?
-
Riddle #4: if-statement considered harmful
Code:
return (a >b)?1:(a<b)?-1:0;
--
Mats
-
Riddle #5: more dwarfs
I would say that equals (6!/(6*5!))-1.
-
Riddle #4: if-statement considered harmful
How about
Code:
(a>b)-(a<b)+(a==b)-(a==b)
-
Riddle #3: three dwarfs, two paths, one life
Quote:
Originally Posted by
laserlight
I wanted to propose the solution of just capturing the dwarves and dragging them in a direction to see their response, but then I realised that I could not be sure that the dwarves were not so bored with their existence that they intended suicide, hence I would have to ask them questions anyway :o
I love this solution. My little brother suggested killing the dwarves until one of them decides to tell the truth anyway, but this solution suffers in a similar way.
And after all, a 50% chance is not too bad, so simply asking for food and a cold beer is probably ok.
Greets,
Philip
PS: ok, I looked it up and will use "dwarves" from now on. Funny language...
-
Riddle #4: if-statement considered harmful
Quote:
I presume that includes ternary operator, and that this is either C or C++?
Yes.
Code:
return (a >b)?1:(a<b)?-1:0;
Nice try.
Quote:
(a>b)-(a<b)+(a==b)-(a==b)
Right! But you may safely skip the "+(a==b)-(a==b)" part.
Greets,
Philip
-
Riddle #3: three dwarfs, two paths, one life
I was inspired by this: Security.
-
Riddle #3: three dwarfs, two paths, one life
And I was inspired by this: Labyrinth Puzzle.
-
Riddle #4: if-statement considered harmful
Oh, this is good. Every since iMalc pointed out that a simple return a - b; is vulnerable to arithmetic overflow, I have been rather depressed over having to use the more verbose ternary operator version, or resort to an if-else chain. So, return (a > b) - (a < b); is good enough :)
-
Riddle #5: more dwarfs
Right!
Can someone else explain it?
Greets,
Philip
-
Riddle #4: if-statement considered harmful
They are not equivalent if I remember correctly. (a < b) will return 0 if false and something non-zero otherwise (but not necessarily 1). The original program returned 1.
-
Riddle #4: if-statement considered harmful
Quote:
Originally Posted by Perspective
(a < b) will return 0 if false and something non-zero otherwise (but not necessarily 1).
No, it will return 1 for non-zero (or true, in the case of C++, which will be converted to 1).
-
Riddle #6: natural languages
I introduce two new adjectives fooish and barish.
A word is fooish if it denotes a property that it has itself.
A word is barish if it doesn't.
Examples for fooish words:
- "short" is a short word.
- "English" is an English word.
- "unfrequent" is an unfrequent word.
Examples for barish words:
- "long" is not a long word.
- "German" is not a German word.
- "rife" is not a rife word.
I claim that every adjective is either fooish or barish.
Is "barish" fooish or barish?
Greets,
Philip
-
Number theory in 21 minutes
Quote:
Originally Posted by
Sebastiani
>> Its faster to just check if a number, modulo 6469693230 has a prime remainder, since all prime numbers do.
Are you sure about that? Can you elaborate?
Yes I'm sure, no I won't elaborate. Well, maybe a little. Specifically, any prime number P modulo a primorial X such that P=> primorial X will have a prime remainder. Obviously it also works for P< X btu then you just check it agaisnt he known primes. This is not a guarantee that the number tested is prime, but it will guarantee it is composite if it fails. It will nto however give you any of the factors of the composite number. The greater the value of X the stronger the evidence for being prime. This method of checking very large primes is an embarrisingly parallelizable method. Since as X grows, it increases teh number of independant checks very quickly. It does however require a very large and comprehensive database of known primes for values of X larger than ~31. The size of the database approaches (X primorial / ln(X primorial)) * sizeof(N) where N is the type of teh storage unit for a single prime. For X = 23 and N is a DWORD its about 46MB, while for 29 its over 1GB, and it grows more rapidly after that.
-
Riddle #4: if-statement considered harmful
This would be more fun if you also banned '<' and '>'
-
Riddle #4: if-statement considered harmful
This reminds me when I listened to Steve Gibson talk about a version of assembly that had no OR. You had to implement your own.
-
Riddle #4: if-statement considered harmful
Quote:
This would be more fun if you also banned '<' and '>'
I can see some ugly bit twiddling here. Any volunteers? :))
Quote:
This reminds me when I listened to Steve Gibson talk about a version of assembly that had no OR. You had to implement your own.
Nothing easier than that if you know that double negation doesn't change the value:
a OR b == !(!a AND !b)
I once had to show that AND and NOT form a logical basis, i.e. that one can express every boolean formula by only using AND and NOT (and variables, of course). An even smaller logical basis is NOR. Sounds like a good riddle...
A far more intriguing example of simplicity is the "One Instruction Set Computer", which only has a single instruction. One possible solution is the SBN instruction, subtract-and-branch-if-negative. It has three operands a, b and c. It works by subtracting the contents of memory location a from those at address b, storing the result at address b and jumping to c if *a > *b. Of course, this machine can be proven to be Turing-complete.
This takes the meaning of RISC to a higher level.
Greets,
Philip
-
Riddle #4: if-statement considered harmful
Quote:
Originally Posted by Snafuist
I once had to show that AND and NOT form a logical basis, i.e. that one can express every boolean formula by only using AND and NOT (and variables, of course). An even smaller logical basis is NOR. Sounds like a good riddle...
I had the impression that proving that NAND and NOR are universal gates is a pretty common assignment for first or second year computing and engineering students.
-
Riddle #6: natural languages
-
Riddle #6: natural languages
-
Riddle #6: natural languages
"Everything I say is a lie."
"This statement is wrong."
I feel that this falls into the same category of oxymorons. If barish were barish, it'd be fooish. If it'd be fooish, it wouldn't be fooish.
-
Riddle #6: natural languages
-
Riddle #4: if-statement considered harmful
Quote:
Originally Posted by
laserlight
I had the impression that proving that NAND and NOR are universal gates is a pretty common assignment for first or second year computing and engineering students.
Maybe. This used to be true for CS students at my university (that's why I knew about it). Now, the corresponding lecture isn't mandatory anymore. It seems to me that the focus has shifted from logic towards algorithms (which is good for me, because these two are the only topics that I appreciate in CS). BTW, my fellow students in theoretical philosophy tended to be much better in boolean logic than most CS students.
Greets,
Philip
-
Riddle #6: natural languages
Quote:
If barish were barish, it'd be fooish. If it'd be fooish, it wouldn't be fooish.
For those who don't see it right away, here's the full proof:
Suppose that "barish" is barish. Then it denotes a property that it has itself, hence it is fooish. Contradiction.
Suppose that "barish" is fooish. Then by definition of "fooish", it must be barish. Contradiction.
Hence "barish" is neither barish nor fooish.
Quote:
Grelling–Nelson paradox
Or more correctly, the Grelling-Nelson antinomy. Back in 1908, they hadn't heard of "foo" and "bar" yet, so instead they used autological and heterological respectively.
In 1884, Gottlob Frege published "The Foundations of Arithmetic", where he tries to deduce mathematics from logic (Frege is way ahead of his time: a few years earlier, Leopold Kronecker said "God made the integers, all the rest is the work of man"). In a letter to Frege, Bertrand Russell points out a fundamental flaw in Frege's design, which later came to be known as "Russell's antinomy". This letter is fun to read, but unfortunately I only have access to the original version, which is in German. Anyway, the Grelling-Nelson antinomy is a reformulation of Russell's antinomy which is a bit easier to understand (the original version isn't too hard either). In 1931, Kurt Gödel used the same technique in his proof of the First Incompleteness Theorem which states that "any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete". Read this as "math is either inconsistent or incomplete or both, and so are any of its reformulations". I highly appreciate the proof and I consider it to be the most important discovery of the 20th century, so I will summarize it below:
1) in a given theory T, assign a unique number to each theorem, e.g. theorem 1, theorem 2, theorem 3, ..., n.
2) add a new theorem n+1 which claims that "theorem X is not provable".
3) apply this theorem to itself, which yields a claim similar to "This sentence is not provable".
This claim is either true or false. If it is true, than the theory is incomplete (it lacks a proof). If it is false, then there exists a proof, hence the theory is inconsistent (it has a proof for something that says that there is no proof).
In today's mathematics, there are a lot of claims for which no proof can exist. The first one discovered (40 years after Gödel) is the continuum hypothesis which claims that "there is no set whose cardinality is strictly between that of the integers and that of the real numbers". Being unprovable means that you cannot find such a set, but you also can't show that it doesn't exist.
Another funny issue that suffers from the same problem: one can prove that it's possible to split a ball from the 3-dimensional space of the reals into six pieces such that out of these, you can construct two balls which both have the same size and volume as the original ball. But one can also prove that it's not possible to find a concrete decomposition such that it works.
I'm planning to write an article about the whole story to improve my English skills. Is this stuff somehow appealing to non-mathematicians?
Greets,
Philip
-
Riddle #7: two smallest elements
The natural numbers are usually ordered in the following way:
1 < 2 < 3 < 4 < ...
There is exactly one element (the first) which has no predecessor. Note that we are free to invent our own order for the natural numbers, e.g. 2 < 1 < 3 < 4 < ...
Can you find an order for the natural numbers such that there are two elements that have no predecessor?
Greets,
Philip
-
Riddle #7: two smallest elements
Does the order have to be total and strict? If it has to be, then there cannot be more than one. Assume there were e1 and e2 that are both "smallest". By the rules of total, strict ordering, either e1 < e2 or e2 < e1 must be true, otherwise e1 = e2.
-
Quote:
Originally Posted by
CornedBee
Does the order have to be total and strict? If it has to be, then there cannot be more than one. Assume there were e1 and e2 that are both "smallest". By the rules of total, strict ordering, either e1 < e2 or e2 < e1 must be true, otherwise e1 = e2.
Yes, the order has to be total and strict. Note that an element without a specific predecessor is not necessarily a smallest element (although a smallest element certainly doesn't have a predecessor).
Hint: can you find an order such that there is no smallest element?
Greets,
Philip
-
Riddle #7: two smallest elements
There's ... < 3 < 2 < 1, where no element has no predecessor, but exactly one has no successor. But I'm not sure if that could really be called a distinct ordering. Predecessor and successor are just a matter of perspective.
An ordering that really has no predecessor would be ... < 5 < 3 < 1 < 2 < 4 < ..., i.e. mirror the odd (or even) numbers.
Code:
int oddneg(unsigned i) { return isodd(i) ? -(int)i : (int)i; }
bool operator <(unsigned l, unsigned r) { oddneg(l) < oddneg(r); }
-
Riddle #7: two smallest elements
Quote:
Originally Posted by
CornedBee
There's ... < 3 < 2 < 1, where no element has no predecessor, but exactly one has no successor. But I'm not sure if that could really be called a distinct ordering.
As there are infinitely many natural numbers, the two orderings ... < 2 < 1 and 1 < 2 < ... are distinct because they have different properties (there's a clear difference between successor and predecessor). If the natural numbers were finite, these two orderings would be the same (apart from the labeling of the symbols, which is irrelevant).
Quote:
An ordering that really has no predecessor would be ... < 5 < 3 < 1 < 2 < 4 < ..., i.e. mirror the odd (or even) numbers.
That's exactly what I had in mind. From here, it's only a small step to an order where two elements don't have a predecessor.
Hint: an element may have an ancestor, even if it doesn't have a predecessor.
Greets,
Philip
-
Riddle #7: two smallest elements
So: 1 < 3 < 5 < ... < 2 < 4 < 6 < ...
i.e. order all odd numbers before all even numbers, or vice versa. Given the definition of predecessor as "a is pred. of b if a < b and there's no c such that a < c < b", 2 has no predecessor.
The second hint did it.
-
Riddle #7: two smallest elements
Quote:
Originally Posted by
CornedBee
So: 1 < 3 < 5 < ... < 2 < 4 < 6 < ...
i.e. order all odd numbers before all even numbers, or vice versa. Given the definition of predecessor as "a is pred. of b if a < b and there's no c such that a < c < b", 2 has no predecessor.
Right!
It may sound silly, but I feel happy now.
Greets,
Philip
-
Riddle #6: natural languages
>I'm planning to write an article about the whole story to improve my English skills. Is this stuff somehow appealing to non-mathematicians?
I'd read it. I was actually planning on taking a class this summer that looks at the foundations of logics, including things loke Gödel's theorem. I'll be away on an internship instead though so I won't get to take the course.
-
Bonus Riddle
Since Snafuist posts all of the riddles he doesn't get the fun of trying to solve them. Here's one you guys may enjoy, the solution is more computer sciency than you might think ;)
Every year in a village of dwarves, an evil ogre comes to play a deadly game. The dwarves get lined up by hight and are not permitted to look any direction but forward (this means each dwarf can only see the dwarfs ahead of him/her). Each dwarf is then given a hat, which he can not see. The hat is either black or white. This means each dwarf can see all of the hats in front of him, but not his own or any behind him.
Starting from the tallest dwarf, they go in order down the line calling out either "black" or "white". If a dwarf correctly identifies the colour of their hat, they live. If they get the colour wrong, they die.
The dwarves spend all year planning a strategy to save the most dwarves as possible.
Problem: design a strategy to save the most dwarves. You can assume that all dwarves are cooperative since they want to save as many of themselves as possible.
Example:
======
Each dwarf calls out the colour of the final dwarfs hat. When it gets to the final dwarf, he knows the colour of his hat (because he's heard it n-1 times), and he just says his own hat colour. This is guaranteed to save at least one dwarf.
You should easily be able to find a solution that saves half of the dwarves. The optimal solution will always save at least n-1 dwarves.
-
Bonus Riddle
The only way I could think that could work is if the dwarves followed the pattern (starting with the first):
[1] identifiy the next dwarfs hat color (and die)
[2] identify own hat color (and live)
...thus saving n/2 dwarves...
-
Bonus Riddle
I assume this is not allowed:
The one in the back guesses his own color. And they say "I think I have ***" if the one in front of them has a white hat and, "***, I think", if the one in front of them has a black hat.
If that's not allowed, then they could change some slight way they speak the word that is only audible if you know they're doing it.
Not allowed, I guess? ;)
But,so, they start at the back of the line? And there are no limitations to the number of hats? Eg. they may all be black?
-
Bonus Riddle
The tallest dwarf exchanges hats with the next tallest and says the color of his original hat. The second dwarf says this color, lives, and switches hats again with a shorter dwarf. This always saves at least n-1 dwarfs since they all, at one point, wore the same color hat.
-
Bonus Riddle
Very clever! But wouldn't that be cheating?
-
Yet another riddle
Okay, Perspective's riddle reminded me of a riddle I heard a while ago. A riddle I liked a lot ;).
Three people are lined up. They may not look back or touch each other. They can only see the people in front of them.
So let's say we have person A, B and C. A can see B and C. B can see C. C can't see anyone.
Then, someone comes with 5 stickers: 3 black and 2 white, and puts one on the back of each. So, again, A can see B's and C's dots, B can see C's dot.
They are not allowed to speak unless they want to say which color they think the dot they have on their back is. If one gets it wrong, they all die. If one gets it right, they all live.
They're smart, and all always survive. How?