PDA

View Full Version : try your heads on this



Pages : [1] 2

jasrajva
11-01-2001, 08:14 AM
hi peepl

thought i'd give you peepl a puzzle to ponder over
(if you've heard this already pls let other people bend their minds ok you can pm me the solns)

ok here we go

once upon a time-space
there lived superintelligent beings on a Planet called Cprog
on sunday in a church on the island of tutu the priest made a declaration

he said:

among those of you who have gathered here are some sinners
on their heads a mark will appear
this mark may not be seen by the person who has it on his/her head
but evryone can see the mark on any other person

as soon as any one of you with the marks comes to know that he/she has it, they should stop coming to church

and all of you shall come to this church everyday until all the sinners have left

finally no one shall tell any other if the other has a mark

the priest went away and the people followed

after a week none of the people with the mark were left

can you tell me how many people had the mark initially


jasraj

dbaryl
11-01-2001, 09:51 AM
How about one - the priest

:)

jasrajva
11-01-2001, 11:34 AM
no thats not possible
the logic is much more involved
and i can prove that its not the priest alone
but if i give the proof here then i'll give out a very big hint
so..

Betazep
11-01-2001, 11:40 AM
All of them

jasrajva
11-01-2001, 11:50 AM
this thing really has 'some ' logic behind it ok

and any more answers should end with a QED i want proof peepl not guesses

Betazep
11-01-2001, 11:55 AM
Assuming someone had a mark because they are sinners (which most pentecostal believe everyone are sinners and would have marks in this case), then the only way they would know that they had a mark is if some one told them.

If someone told them, then that person too has sinned and would gain a mark. This would lead to all of them leaving too.

I don't know... this is my best shot at it right now. ;)

I can't wait to hear the answer to this. PM me and let me know so you don't ruin it for others. :)

jasrajva
11-01-2001, 12:00 PM
well nice try but lemme put more words into the priests mouth to cut that answer out
all those who squeel will turn into stone and will permanently remain in the church

apart from that why did it take them all a week to figure out????

think peepl think
ive just given you a huge clue

C_Coder
11-01-2001, 01:06 PM
all the people who are sinners lied to non-sinners saying they had marks when they didn't, the sinners then turned to stone so couldn't go back to church(lucky for them).
thats my theory.

except they are in the church anyway so that wouldn't work, damm.

or maybe they did lie in church then turn to stone then it took the non-sinners a week to carry them out.

Betazep
11-01-2001, 03:01 PM
Dammit... I am tired of trying. All of us at work have been thinking about it. We cannot figure it out.

jasrajva
11-01-2001, 08:06 PM
ok give you a hint beta..

think
principle of mathematical induction

Betazep
11-01-2001, 08:08 PM
I just keep thinking that it is cool that you live in India... :)

jasrajva
11-01-2001, 08:17 PM
why is that

(try selling that idea to anyone here)
its november and still 35*C
some one send me an AC..

Justin W
11-01-2001, 09:38 PM
If you have the mark and can not see it, presumably you can not know you have it.

Furthermore, if no one that can see it can indicate to you that you have it and there is again, no loophole, then you again can not know you have it.

Since no other way of knowing presents itself, then no one discovered they had the mark.

If no one with the mark came to church the next week, then all cprogrammers were holy and without sin. 0 had the mark. Yeah right. :p

?

-Justin

Aran
11-01-2001, 09:45 PM
*puts a golden crown upon Justin's head*

Thou beith holy for thou hath defineth this solution to this riddle.

*smashes a chair of Justin's bacl*

Thou wast named after a backstreet boy! Blasphemy!


.....remember from Monty Python and The Holy Grail?
"What do we burn with ... Backstreet Boys?"
"more ... Backstreet boys!"

Justin W
11-01-2001, 11:54 PM
Aye, 'tis my curse. *sniffle* ;)

jasrajva
11-02-2001, 02:33 AM
no justin wrong

if its zero why did it take them 7 days to figure out???

biterman
11-02-2001, 03:42 AM
How can they console their superb reason with faith?

adios,
biterman.

PS: I'd love to know the answer to this. Something tells me it's exceedingly simple, and when we find out we're just gonna smack ourselves upside the head for not realizing it.

nvoigt
11-02-2001, 03:48 AM
Okay, first the story edited to get the bare facts

in a group are some who have a mark.
the mark is only visible to others.
no one gets to know if s/he wears a mark
7 times they met until finally, all marked left.


You didn't tell how many people were in the group.
That leads to the conclusion that this fact is not important.

You did say you wanted proof, so the seventh gathering
was NOT a random success.

No group can determine such facts with EXACTLY seven
tries if the size is variable. A group of two will have the
perfect solution after 4 tries AT LEAST. And with any luck
way before that. And that would be a random success.

So that leaves us with either possibility: None or All.
Neither would take 7 days to figure out, but again a random
time, depending on how they check.

There is no way to make sure that while testing you do not
accidently hit the right number by leaving the marked out of
the test. So there is no way to make sure it takes EXACTLY
seven tries. No matter how large the group is.

Which leaves me with the conclusion that the bare mathematical
facts are not important to solve this riddle, or rather it can't be
solved, which would be another kind of solution.

So lets get back to the seemingly unimportant facts.

The priest started sunday. They figured out the next sunday.
Depending on the religion, could it be all their sins are forgiven
before sunday service ?

Then, without telling they could have found another way...
maybe the just silently jailed all the sinners or something.

?

*Michelle*
11-02-2001, 04:04 AM
I'm stumped!! :(

jasrajva
11-02-2001, 07:14 AM
nvoigt said
>>>>>No group can determine such facts with EXACTLY seven
tries if the size is variable. A group of two will have the
perfect solution after 4 tries AT LEAST. And with any luck
way before that. And that would be a random success.

no they can even if the group is variable in size
remember they are superintelligent beings(something like an islandful of mensa members(i wouldn't lke to live in such a place though)

another hint i'll drop
>>>>
try figuring out the 7 days part of it
and as i said before try mathematical induction

that means something like

if P(1) is true and p(k) implies p(k+1) then p(n)(generalisation) is true

and no the answer is not very obvious
to us non superintelligent beings

i was stumped for a week with this first time i heard this and am yet to see a person who answered this correctly without hints and prodding

so lets see if thisboard can produce someone

when you peepl get bored tell me i'll post the answer

nvoigt
11-02-2001, 07:38 AM
Well,

1 Person will have a solution in 2 tries
2 persons will have a solution in 4 tries
3 persons will have a solution in 8 tries

AT LEAST !

Fact is, they try until the priest says it's ok.
No try will reveal anthing about anybody,
as the priest will not say why this is the
wrong combination ( could be a sinner in,
could be a sheep missing ).
So they can as well hit the right combination
on the very first try. We don't know which
combination they start with. They might start
with all out, or all in. It's completely beyond
our control or knowledge, so it's nothing we
can build our proof on.

With this kind of feedback from the priest
( Yes/No ) and two different error conditions
( sheep missing / sinner in ) you are lost.

I'm eager to get an explanation, though ;-)

jasrajva
11-02-2001, 07:46 AM
nvo

no you are missing something here
1 person needs 2 tries is wrong

why dont you peepl try and use the data provided
no one to my knowledge has used the data abt 7 days yet

another hint
the solution requires no form of communication at all
all the people need to do is to come to church
and watch

jv

nvoigt
11-02-2001, 08:06 AM
I'm not taking in account the priest here... it's just one more
person. If neither person where a sinner, there wouldn't be a
task, so there has to be at least one.


1 Person...

assume he's a sinner:

Goes -> Error
leaves -> Right
2 tries

leaves - > Right
1 try

assume he's a sheep:

Goes -> Right
1 try

leaves -> Error
goes -> Right
2 tries

4 possibilities, all same probability, 6 tries, statistically that makes
1.5 tries. Actually, it depends on luck, and implying you need
logic and not luck, you need 1 to be sure, and another one to
make the right decision to leave or stay. Assuming that happened
on the first try is not something you can build a proof on.
Assuming a statistical middle way is also nothing you can build
a proof on. So either it's all luck, or you assume 2 tries...
As we all know from binary calcs, this is like a bit...
1 bit, 2 states, 2 bits, 4 states, 3 bits, 8 states... and you will
have to test them all to know which is right, and hitting the
right combination anytime is pure luck. You don't need all tries
most of the time.

Actually, you need one try less, because the group can assume
that all sheep is not an option.

1 -> 1
2 -> 3
3 -> 7

ah, the magical seven... which doesn't mean we know how many
it were... that completely depends on how they test. They could
hit the right combination on the very first day...

I'm going to try your way...

X people needed 7 days to identify Y sinner(s)
X people needed 7 days to identify ( X - Y ) sheep
( whatever is shorter )

Obviously, X is at least 3, or it gets really ridiculous.
Y should be at least 1 or the task is fullfilled the
second it was spoken out.


I'm stumped here...



>no they can even if the group is variable in size

Do you realize what you want to prove here ?
You want to prove that with seven instructions you can
compare any two binary streams for equality, regardless
of size. You should break that knowledge to some
database corporations. I bet Oracle or Microsoft would
kill a small country to obtain that strategy and patent it.

jasrajva
11-02-2001, 08:13 AM
Originally posted by nvoigt

>no they can even if the group is variable in size

Do you realize what you want to prove here ?
You want to prove that with seven instructions you can
compare any two binary streams for equality, regardless
of size. You should break that knowledge to some
database corporations. I bet Oracle or Microsoft would
kill a small country to obtain that strategy and patent it.

:) i dont think you are quite on the rite track here

they dont go by the trial and error method they think it out and keep their eyes open that is all

nvoigt
11-02-2001, 08:25 AM
Sorry, without communication and an infinite amount of people, I see no chance of thinking it out...


Can you give the solution ?

jasrajva
11-02-2001, 09:08 AM
to nvo

no i wont give out the soln in public
let otherpeoplethink abt it
i can do so in private if you want though

ill give you a step towards the answer now
priv ok

nvoigt
11-02-2001, 09:13 AM
ok, let the others have fun...

I for one surrender. Can you send a solution to

Niels.Voigt@T-OnlineXXX.de ?

oh, and delete the XXX after T-Online, i hate webspiders :p

jasrajva
11-02-2001, 09:31 AM
ok nvoigt

i've pmed it to you and mailed it too

tell me if you get it?

jv

Justin W
11-02-2001, 10:02 AM
There were two essential facts missing. First, that they apparently meet every day. I thought the seven days was just implying "next Sunday when they met again". So they meet once a day?

In that case (2.) how do they discover they have the mark? Is the priest allowed to say something? Your description made it seem that there would be no way for anyone to discover if they have it or not. But if the priest can say (three today) or even (one gone today, three sheep missing) then that changes things quite a bit.... or did I just miss this piece of the puzzle? Presumably, they meet once a day for seven days, hence they must discover they do or don't have the mark by meeting once a day for seven days... right? Wrong? If this is too much of a give away, please PM me... ;p

Betazep
11-02-2001, 11:33 AM
Well...

In reality I would think that everyone that had the mark would be stared at considerably by everyone else.

So if you deduce the number of people it would take to stare a number of people out over a seven day process, I would think that you would have the answer.

I am going to think along these lines. Am I off....?

Betazep
11-02-2001, 11:40 AM
A week is seven days.

They met on sunday and left. Then after a week they no longer had to come every day.

So does this mean that the beginning of their 'week' was monday and the the last day was monday?

It is either six or seven people.

All the people looked at one of the members that had a mark. That person didn't come back. They did this for one weeks time. On the eighth day they didn't have to return. I am going to go with seven people.

jasrajva
11-02-2001, 08:17 PM
yes beta
youre way off

and justin as i said in one of my prev messages no one speaks they just think it out

and as nvoigt will tell you it is possible
read the prev mesgs for more hints

Betazep
11-02-2001, 08:41 PM
They wouldn't have to speak.

Imagine a room that has five people and a moderator.

The moderator says that some in the room have marks...

Each person cannot see their own mark and cannot tell others if they have a mark.

Each person that has one has to leave.

*****

Ok... one and two have a mark.

Without communicating individually at all, if two, three, four, and five all look at one for a while... one should figure that he has a mark and leave. Then three, four, and five look at two until he leaves.

:):)

So... I guess I really suck at this. Please email me the answer before I start killing my neighbors.

betazep@hawaii.rr.com

jasrajva
11-02-2001, 10:42 PM
ok so betazap gives up as well
ill mail you the answer(or atleast a part) beta

any more people with any ideas???

Justin W
11-02-2001, 11:32 PM
Look, I just don't think there is enough info provided. There are currently an infinite number of possibilities. The key to this is, if there is no way to know you have the mark, and no way for the others to let you know or keep you from attending, then there is no longer a solution. If the others can do anything but speak, then they jailed the sinners the first day, then took the next six days off to congratulate themselves.

Maybe I missed this, but can the priest say anything about it, like "there are still sinners" or "there are no longer sinners". The mathematical possibilities without any limitations are infinite. The mathematical possibilities with perfectly strict limitations are 0. So either no one was a sinner, or the riddle has some important missing information.. Consider that I give up and PM me, unless there is some limitation that was neglected earlier that you can tell everyone.

If there is a solution with the given info, then please PM and explain to me why 0 sinners does not meet the requirements. Thanks. :p :D

Nick
11-02-2001, 11:39 PM
Here is an outline of a proof.



among those of you who have gathered here are some sinners

there is at least one sinner.

Base case.


I assume this all would happen simutanously.

day one passes
1.1
If there is one sinner left by process of elimination
not seeing any other sinners would know that
they are the sinner and leave.

day two passes
1.2
If there are two sinners left by process of elimination
they are able to tell that they are sinners.
This is because sinner #1 would see the sinner #2.
sinner #1 would be able to reason
case 1: I'm not a sinner.
sinner #2 would then would have left by 1.1
case 2: I'm a sinner
only possible case
They would both leave.

Generalizing it is possible to see that if a sinner sees
two other sinners who havn't left due to 1.k-1 then
they would be able to reason by 1.k-1 that they are
sinners. Therefore my rough guess is 7 sinners.

gamegod3001
11-02-2001, 11:52 PM
1/2 of the people are sinners.

Nick
11-03-2001, 12:06 AM
I'll try to do a better proof of this as it's worded
pretty bad and leaves out some stuft.

Nick
11-03-2001, 12:33 AM
This is still an outline.


1.1
There is at least one sinner.

Let N = Number of sinners
Let n = number of days past

if N=1 and n=0 then that one sinner would see no other
sinners. By 1.1 he would reason that he was the sinner.

if N=2 and n=1 then both sinners would realize that
when n=0 no one left. But both sinners would see each other
by process of elimination both would leave.

Generalizing
if N=k and n=N-1 then N sinners would realize that
when n=N-2 no one left. So the N sinners would by the proccess
of elimination leave.



after a week none of the people with the mark were left

I'm assumming that on the 7 day when n=6 all the sinners leave.
Solving for N in n=N-1 gives N=7.

Betazep
11-03-2001, 01:15 AM
I get it now... I even had to think about it after I saw the solution. It makes sense now, though.

jasrajva
11-03-2001, 07:22 AM
HI NICK
WELL DONE YOUVE GOT THE ANSWER

im in a hurry now but ill post the complete answer tonight

jv

Justin W
11-03-2001, 12:37 PM
Ah Ha! There was missing info if that is the solution. This assumes we know how many sinners there are to start with. If there are two sinners, and they don't know how many, then the one looks at the other one and thinks, "oh good, that person is the sinner". But they can't tell each other, so they just both comming to church. That solution does work if and only if there are a fixed and given number of sinners.

Granted I didn't read the original riddle carefully enough the first time I posted, but I'm pretty sure I'm right on this. Just because they know there are still sinners, by the fact they keep coming to church, doesn't mean they know how many sinners there are.

jasrajva
11-04-2001, 01:17 AM
GRRRR JUSTIN

YOU STILL DONT GET IT OK ILL EXPLAIN

imagine and i mean imagine that there is just one sinner(this is hypothetical)

so all other people in the church see his mark and hope that he is the only marked one

now the sinner doesnt see a mark and knows that atleast one person is marked so s/he knows that it has to be him/herself

and so stops coming from monday

now imagine there are two sinners then they each see 1 person with the mark on sunday so they both come back on monday

now A wonders why B came back it could only be if b had also seen a mark so it must be A who also has a mark and in the same way B also figures it out that s/he has a mark

so they both stop coming on tuesday

and this can now be extended to seven days

i cant write down the whole proof obviously but mathematical inductio helps me there

it says if
p(1) is true and p(k) implies p(k+1) then p(n) generilastion is true

so 7 is the soln
if you cant still figure it out i cant help you

Justin W
11-04-2001, 06:59 PM
I don't believe it is logical to solve this backwards. There couldn't be one or two people with the mark, because it took seven days. So if there are three or more with the mark to start with, then A sees B and C. B sees A and C. C sees A and B. D, who does not have the mark, sees that A, B, and C have the mark. A assumes B doesn't leave because B sees C (and what, three others?). So on and so forth until D, who is COMPLETELY innocent, decides to leave because he is also paranoid. Everyone else stays for another three or four days until the sinners are sick of going to church and ditch. This then, is the only reason all the sinners are gone by the seventh day, and there is no way to tell how many there were to start with.

You can't get rid of one per day with several people marked because there is no reason A should leave over B over C over the next four sinners. It is a stalemate. Put yourself in the shoes of one who doesn't know if you are a sinner or not and seeing several sinners return every day. Do you assume that makes you one?

Furthermore, if with geometry we can prove that a point is an infinitely small but existent amount of space, and that in the measure we call an inch, there are an infinite amount of said points, then how is movement possible? Must you not pass through all points? How long would it take you to travel through an infinite distance? It takes me about .01 seconds usually. Does this mean I skip space like in animation? Am I running at 4000FPS?!?!??! ;)

Natase
11-04-2001, 07:26 PM
I'm with Justin... either:

1 - the priest has to say how many sinners there are to start with, in which case they all realise the next day according to your logic, ie each sinner sees only 6 other sinners... or

2 - each day they go to church the priest has to say whether there are any sinners left or not... without this communication there is absolutely no reason why the last sinner would leave.

jasrajva
11-04-2001, 09:53 PM
You peepl are not getting the point here
im not saying that there are 1 or two people to start with that is just a hypotheses

if only one person has the mark then he is eliminated in a day

if two then in two days etc

so if all the people with the mark are gone in 7 days
it follows that seven people originally had the mark

ask betazap or nvoigt or NICK they all agree with me

and justin if there are three to start with each sees two people with the mark and believes that there are only two sinners so thy should stop coming in two days so they all come back on tuesday and realise that there have to be three people with the mark

and so on

and natase

you still dont get it at all read my prev posts properly again

Natase
11-05-2001, 06:21 PM
you still dont get it at all read my prev posts properly again

Oh, believe me, I did... now how about you go back and read my second point properly.

jasrajva
11-05-2001, 08:21 PM
natase
the point you dont get is that they all (no matter how many sinners they are to start with stop coming on the same day
ie if 5 sinners were there then they would all come till thursday and stop coming on friday

(read back for the explanation and you'll see why)

Natase
11-05-2001, 09:01 PM
That makes absolutely no sense... I believe the maths, I just don't think it's being implemented properly.

If there were 5 sinners, and each day they come to church they see 4 other sinners, why would they assume the others are coming because they see their own mark?

Surely each of the 5 sinners would assume that there are only 4 sinners and wait for them to figure it out...

Justin W
11-05-2001, 09:18 PM
Exactly.


and justin if there are three to start with each sees two people with the mark and believes that there are only two sinners so thy should stop coming in two days so they all come back on tuesday and realise that there have to be three people with the mark

Why does the third person leave then? Why not number 1? Or number 2? Or all three? Put yourself in the shoes of the fourth person. Don't assume you have the mark, wonder about it. Three people with the mark show up the first day. Then they show up the second day. Why do you assume that they are waiting for you to leave instead of one of them?