PDA

View Full Version : Riddle Thread

Pages : [1] 2 3

Snafuist
03-26-2009, 04:45 AM
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

zacs7
03-26-2009, 05:16 AM
> 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 :)

Snafuist
03-26-2009, 05:33 AM
Well for one all prime numbers are odd.

Wrong. 2 is an even prime number.

And we all know given n (an odd number) n - 1 is even.

Right. So?

Greets,
Philip

laserlight
03-26-2009, 05:36 AM
Wrong. 2 is an even prime number.
I think zacs7 forgot the phrase "within the given range" or "greater than 3".

zacs7
03-26-2009, 05:41 AM
> 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.

laserlight
03-26-2009, 05:48 AM
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?

zacs7
03-26-2009, 05:49 AM
I never said it proved it :)

EVOEx
03-26-2009, 05:52 AM
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.

Snafuist
03-26-2009, 06:31 AM
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

EVOEx
03-26-2009, 06:39 AM
Heh. That really was a lot easier. ;)

Snafuist
03-26-2009, 06:46 AM
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

anon
03-26-2009, 06:57 AM
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)

Snafuist
03-26-2009, 07:06 AM
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

EVOEx
03-26-2009, 07:26 AM
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....

Snafuist
03-26-2009, 07:38 AM
I always make those kinds of stupid mistakes....

Well, you're not alone. My inability to perform mental arithmetic is famous by now...

Philip

Snafuist
03-26-2009, 07:44 AM
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

EVOEx
03-26-2009, 07:59 AM
I only knew this one without C and only one question. But it's still fairly similar ;).

DavidP
03-26-2009, 08:19 AM
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. :)

EVOEx
03-26-2009, 08:22 AM
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.

Akkernight
03-26-2009, 08:32 AM
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 ;)

Snafuist
03-26-2009, 08:33 AM
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

Akkernight
03-26-2009, 08:39 AM
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

abachler
03-26-2009, 08:40 AM
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.

Snafuist
03-26-2009, 08:41 AM
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

DavidP
03-26-2009, 08:44 AM
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)

EVOEx
03-26-2009, 08:48 AM
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.

Snafuist
03-26-2009, 08:49 AM
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

Snafuist
03-26-2009, 08:52 AM
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

EVOEx
03-26-2009, 09:14 AM
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.

Snafuist
03-26-2009, 10:12 AM
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

Sebastiani
03-26-2009, 10:35 AM
Hey that's pretty cool, though. Nice one.

CornedBee
03-26-2009, 11:30 AM
Giant In the Playground Games (http://www.giantitp.com/comics/oots0327.html)

That's all I'll say. :)

Perspective
03-26-2009, 11:44 AM
There's a whole book of these problem called Knights and Knaves, something like this:
Knights and Knaves: Knights and Knaves Logic Puzzle (http://www.hku.hk/cgi-bin/philodep/knight/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 (http://store.doverpublications.com/0486296156.html)

abachler
03-27-2009, 01:40 AM
Its faster to just check if a number, modulo 6469693230 has a prime remainder, since all prime numbers do.

Tonto
03-27-2009, 03:33 AM
The greatest common factor explanation of this is great

Sebastiani
03-27-2009, 09:02 AM
>> 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?

Snafuist
03-27-2009, 10:27 AM
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

laserlight
03-27-2009, 10:31 AM
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.

Snafuist
03-27-2009, 10:34 AM
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

Snafuist
03-27-2009, 10:46 AM
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

laserlight
03-27-2009, 10:56 AM
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

Snafuist
03-27-2009, 10:57 AM
Oops, I skipped #4, so here it is.

Consider the following program:

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

laserlight
03-27-2009, 11:00 AM
I presume that includes ternary operator, and that this is either C or C++?

matsp
03-27-2009, 11:00 AM
return (a >b)?1:(a<b)?-1:0;

--
Mats

tabstop
03-27-2009, 11:06 AM
I would say that equals (6!/(6*5!))-1.

PING
03-27-2009, 11:08 AM

(a>b)-(a<b)+(a==b)-(a==b)

Snafuist
03-27-2009, 11:08 AM
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...

Snafuist
03-27-2009, 11:12 AM
I presume that includes ternary operator, and that this is either C or C++?

Yes.

return (a >b)?1:(a<b)?-1:0;

Nice try.

(a>b)-(a<b)+(a==b)-(a==b)

Right! But you may safely skip the "+(a==b)-(a==b)" part.

Greets,
Philip

laserlight
03-27-2009, 11:12 AM
I was inspired by this: Security (http://xkcd.com/538/).

Snafuist
03-27-2009, 11:15 AM
And I was inspired by this: Labyrinth Puzzle (http://xkcd.com/246/).