- #691
Enigman
- 643
- 312
mathematical induction may help if the previous post is correct...
Solve Enjoyable Enigmas with Mr.E's Challenge
- Thread starter Enigman
- Start date
Click For Summary
The forum thread invites puzzle enthusiasts to share various types of puzzles, including cryptograms and whodunnits, while emphasizing that participants should know the answers without resorting to online searches. A code message is presented, which participants attempt to decode, leading to discussions about its meaning and possible interpretations. Participants also engage in solving additional puzzles, such as cutting a cake into pieces with minimal cuts and a physics challenge involving water and matchsticks. The conversation highlights the enjoyment of problem-solving and the creative thinking required to tackle these enigmas. Overall, the thread fosters a collaborative atmosphere for sharing and solving intriguing puzzles.
- #692
collinsmark
Science Advisor
Homework Helper
- 3,443
- 3,417
I can prove it conclusively for 3 dalmatians and total spots of selected dogs being an integer multiple of 3 (proof involves proof by contradiction). But I haven't yet been able to carry that over to 11.
- #693
CompuChip
Science Advisor
Homework Helper
- 4,305
- 49
Actually I'll put my reply in spoiler tags, it's not a complete answer but it's my thoughts about the problem so far.
I'm thinking more along the lines of a group theoretic proof, where there is probably some cool result about ##\mathbb Z_{11}## that will show it.
If all dalmatians had equally many spots ##a##, it would be fairly straightforward, because since ##p = 11## is prime and any element of ##\mathbb Z_p## generates the whole group, you need to multiply your generator ##[a]## by at most ##p## (and if I recall correctly, exactly ##p##, since the order of any element is the order of the group) before at some point you hit the identity ##[0] \in \mathbb Z_p##.
The problem is that all the dalmatians have a different number of spots, so you need to take ##p## arbitrary elements and show that a subset of them gives the identity. Proof by contradiction may work. I was also thinking about "reverse" induction: you cannot have all ##p## elements be the same (otherwise you are back to the easy case) so there must be at least one different one - if we can show that a subset of the remaining ##p - 1## identical elements produces its inverse you might be able to continue this line of reasoning (##p - 2## identical elements, ##p - 3##, etc.).
If all dalmatians had equally many spots ##a##, it would be fairly straightforward, because since ##p = 11## is prime and any element of ##\mathbb Z_p## generates the whole group, you need to multiply your generator ##[a]## by at most ##p## (and if I recall correctly, exactly ##p##, since the order of any element is the order of the group) before at some point you hit the identity ##[0] \in \mathbb Z_p##.
The problem is that all the dalmatians have a different number of spots, so you need to take ##p## arbitrary elements and show that a subset of them gives the identity. Proof by contradiction may work. I was also thinking about "reverse" induction: you cannot have all ##p## elements be the same (otherwise you are back to the easy case) so there must be at least one different one - if we can show that a subset of the remaining ##p - 1## identical elements produces its inverse you might be able to continue this line of reasoning (##p - 2## identical elements, ##p - 3##, etc.).
- #694
collinsmark
Science Advisor
Homework Helper
- 3,443
- 3,417
Solved it!Ibix said:
Solution below.Btw, before I give the solution, it might be necessary to rephrase to the puzzle such that each dalmatian is required to have at least one spot. That makes sense with the bunches of grapes (it's difficult to call a bunch of grapes a bunch of grapes if the bunch has no grapes) but it probably should be explicitly stated for the dalmatians version.
This solution relies on an overall scheme of "proof by contradiction" combined with some smaller steps involving "mathematical induction."
And before I start I should apologize for my poor rigor. I'm not a mathematician and have never taken a math class beyond what is required for engineering.
Before getting to the proof, I need to introduce the concept of Galois Fields. They're not difficult to comprehend: they're just a finite number system that "loops" around as one continues to count up or down. For example, Galois Field 11, denoted as GF(11) contains the natural numbers 0 through 10, and that's it. 11, 22, 33 are all the same thing as 0. If you try to count beyond 10 in GF(11) you wrap back around to 0.
0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5...
The addition operator is pretty straightforward. We define "+" such that in terms of standard integers, it is the sum of a and b MOD 11. Some examples for GF(11) are:
1 + 1 = 2,
2 + 5 = 7,
8 + 2 = 10,
8 + 3 = 0,
8 + 4 = 1,
8 + 5 = 2.
The negation operator maps the number to a new number between 0 and 10 [for GF(11)]. Examples are:
-1 → 10
-2 → 9
-3 → 8
So the subtraction operator examples [for GF(11)] are,
5 - 4 = 1
5 - 5 = 0
5 - 6 = 10
5 - 7 = 9
5 - 8 = 8
We could also define multiplication and addition operators, but its not necessary for this puzzle.
Why Galois fields? Because we're trying to ensure that the total number of spots on the selected dogs, after dividing by 11, has a remainder of 0. We've succeeded in solving the problem if we can prove that there is always a selection of dogs such that (Total number of spots of selected dogs) MOD 11 = 0. And modulo arithmetic is what Galois fields are good at.
So now on to the meat of the solution. We're going to use a "proof by contradiction." What we're going to do is assume that the puzzle statement is false. All we need to do is find a configuration of dog spots -- any configuration -- such that it is impossible to choose a set of dogs such that the spots can be divided by 11 [Same as saying the spots sum to 0 in GF(11) math]. We will later show this to be impossible.
Let s1 be the number of spots on dog 1, s2 be the number of spots on dog 2, and sn be the number of spots on dog n, where n goes from 1 to 11 (there are 11 dogs).
The approach we will take is we get to pick the number of spots on the dogs. The goal is to restrict our picks such that is impossible to divide the total spots by 11 with just one dog. Then moving on, restrict our selection such that is impossible to divide by 11 with either one or two dogs with dog 2; one, two or three dogs with dog 3, and so on.
It should be noted here that in terms of our math, 12 spots is the same thing as 1 spot, which is equal to 23 spots, 34 spots, etc. Since we are only interested in the remainder after dividing by 11, the number of spots on each dog ranges only from 0 to 10 (where '0' doesn't really mean '0' in normal integers; it can be any integer multiple of 11. But for the math here, we call it 0).
Now for the first dog. We restrict the number of spots on this dog, s1, such that it's not equal to 0. (remember 0 is the same thing as 11, 22, 33, 44, etc). That's because if any given dog has a number of spots that are an integer multiple of 11, one could just pick that dog alone, and call it quits. Therefore no individual dog can have a number of spots that are an integer multiple of 11 (in our Galois field math we say the dog's number of spots cannot be 0). For reasons which should become apparent later, allow me to define the function F0(n), such that
F0(n) = 0,
for all n.
Now we formalize our restriction on s1,
s1 ≠ F0(1).
Again, I hope that the function notation will be more clear later. An interesting thing to point out is that we've reduced the number of possibilities for the first dog's spots by 1.
Now let's move on to our second dog. It's number of spots needs to have the same restrictions as the first dog, plus a new one. The new one is that the spots on the second dog, plus the spots on the first dog, cannot add to 0 (same thing as "cannot add to an integer multiple of 11"). In other words, s2 ≠ -s1. Let me formalize that with a new function, F1(n),
F1(n) = F0(n-1) - sn-1
and our restrictions on the second dog are:
s2 ≠ F0(2)
s2 ≠ F1(2)
Don't forget that Fn(m) is ultimately just a number that can range from 0 to 10. It's just some number. And it can be easily shown that F0(2) and F1(2) are unique. If they weren't unique but instead equal, it would mean that
F1(2) = F0(2), and expanding both sides gives,
-s1 = 0, or simply s1 = 0.
But that's not possible since s1 cannot be 0 (restriction on the first dog) so F0(2) and F1(2) must represent unique numbers.
You might notice something neat happening here. We've reduced our possible choices by 1 again. There are 10 numbers to choose from for the first dog, but only nine for the second. Now let's move on to the third dog.
The third dog has all the same restrictions as the first dog and second dog plus a new restriction. Well, a couple new restrictions. Firstly, we need to apply the F1 restriction twice, one for each of the previous dogs. The new restriction is that s3 ≠ - (s1 + s2). Formalizing that with a new function,
F2(n) = F1(n-1) - sn-1
our restrictions become,
s3 ≠ F0(3)
s3 ≠ F1(2)
s3 ≠ F1(3)
s3 ≠ F2(3)
Here I'm going to just remove the s3 ≠ F1(2) restriction. It turns out to be redundant for this particular puzzle. Remember, we are going to use a "proof by contradiction" approach. And later, if we can show that it is impossible to choose spots that falsify the puzzle statement with fewer restrictions, it is still impossible with greater restrictions. So the only restrictions we need to worry about for the third dog are:
s3 ≠ F0(3)
s3 ≠ F1(3)
s3 ≠ F2(3)
Now we know that F1(3) and F0(3) are not equal. But we can explicitly show that here. If they were equal,
F1(3) = F0(3), and expanding both sides gives,
-s2 = 0, or more simply s2 = 0, which is impossible due to earlier restrictions.
Similarly we can show that F2(3) and F1(3) are not equal. If they were,
F2(3) = F1(3), and expanding
F1(2) - s2 = - s2, and expanding more and simplifying,
s1 = 0, which is impossible.
But what about F2(3) and F0(3)? They are also not equal. If they were equal,
F2(3) = 0,
F1(2) - s2 = 0,
-s1 - s2 = 0, which is impossible due to previous restrictions on s2.
So finally, when choosing a number for s3, there are only 8 choices: down one from number of choices from s2.
So now is where our mathematical induction comes in. With each new dog, we place the same restrictions as with previous dogs plus an additional restriction which keeps the sum of all dogs, up to that dog from summing to 0. The new restriction comes in the form, for dog m
sm ≠ Fm-1(m)
where
Fn(k) = Fn-1(k-1) - sk-1.
[Edited above equation.]
So when we get to the eleventh dog, the restrictions on its spots are,
s11 ≠ F0(11)
s11 ≠ F1(11)
s11 ≠ F2(11)
s11 ≠ F3(11)
s11 ≠ F4(11)
s11 ≠ F5(11)
s11 ≠ F6(11)
s11 ≠ F7(11)
s11 ≠ F8(11)
s11 ≠ F9(11)
s11 ≠ F10(11)
Here's the kicker: There are 11 restrictions (starting at 0 and ending at 10, making 11 total). Each restriction removes a possible number from the choosing. But there are only 11 numbers total that we are working with. It is impossible to choose a number of spots for the eleventh dog, such that one can't sum the spots to 0 (where 0 is the same thing as an integer multiple of 11). Our "goal" of trying to disprove the puzzle statement is impossible.
[Edit: There are actually many more restrictions than just the 11 above. For example, there is only a single restriction involving the spot sum of exactly two dogs. And those are dogs 10 and 9, involving F2(11). But there could be restrictions involving the spot sum of any two dogs. But including those restrictions make the contradiction of the puzzle statement even more impossible. The eleven restrictions given above are alone sufficient to prove this puzzle by "proof by contradiction."]
Therefore, there will always be a way to select some or all of the dogs such that the total number of spots on selected dogs adds to an integer multiple of 11.
And before I start I should apologize for my poor rigor. I'm not a mathematician and have never taken a math class beyond what is required for engineering.
Before getting to the proof, I need to introduce the concept of Galois Fields. They're not difficult to comprehend: they're just a finite number system that "loops" around as one continues to count up or down. For example, Galois Field 11, denoted as GF(11) contains the natural numbers 0 through 10, and that's it. 11, 22, 33 are all the same thing as 0. If you try to count beyond 10 in GF(11) you wrap back around to 0.
0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5...
The addition operator is pretty straightforward. We define "+" such that in terms of standard integers, it is the sum of a and b MOD 11. Some examples for GF(11) are:
1 + 1 = 2,
2 + 5 = 7,
8 + 2 = 10,
8 + 3 = 0,
8 + 4 = 1,
8 + 5 = 2.
The negation operator maps the number to a new number between 0 and 10 [for GF(11)]. Examples are:
-1 → 10
-2 → 9
-3 → 8
So the subtraction operator examples [for GF(11)] are,
5 - 4 = 1
5 - 5 = 0
5 - 6 = 10
5 - 7 = 9
5 - 8 = 8
We could also define multiplication and addition operators, but its not necessary for this puzzle.
Why Galois fields? Because we're trying to ensure that the total number of spots on the selected dogs, after dividing by 11, has a remainder of 0. We've succeeded in solving the problem if we can prove that there is always a selection of dogs such that (Total number of spots of selected dogs) MOD 11 = 0. And modulo arithmetic is what Galois fields are good at.
So now on to the meat of the solution. We're going to use a "proof by contradiction." What we're going to do is assume that the puzzle statement is false. All we need to do is find a configuration of dog spots -- any configuration -- such that it is impossible to choose a set of dogs such that the spots can be divided by 11 [Same as saying the spots sum to 0 in GF(11) math]. We will later show this to be impossible.
Let s1 be the number of spots on dog 1, s2 be the number of spots on dog 2, and sn be the number of spots on dog n, where n goes from 1 to 11 (there are 11 dogs).
The approach we will take is we get to pick the number of spots on the dogs. The goal is to restrict our picks such that is impossible to divide the total spots by 11 with just one dog. Then moving on, restrict our selection such that is impossible to divide by 11 with either one or two dogs with dog 2; one, two or three dogs with dog 3, and so on.
It should be noted here that in terms of our math, 12 spots is the same thing as 1 spot, which is equal to 23 spots, 34 spots, etc. Since we are only interested in the remainder after dividing by 11, the number of spots on each dog ranges only from 0 to 10 (where '0' doesn't really mean '0' in normal integers; it can be any integer multiple of 11. But for the math here, we call it 0).
Now for the first dog. We restrict the number of spots on this dog, s1, such that it's not equal to 0. (remember 0 is the same thing as 11, 22, 33, 44, etc). That's because if any given dog has a number of spots that are an integer multiple of 11, one could just pick that dog alone, and call it quits. Therefore no individual dog can have a number of spots that are an integer multiple of 11 (in our Galois field math we say the dog's number of spots cannot be 0). For reasons which should become apparent later, allow me to define the function F0(n), such that
F0(n) = 0,
for all n.
Now we formalize our restriction on s1,
s1 ≠ F0(1).
Again, I hope that the function notation will be more clear later. An interesting thing to point out is that we've reduced the number of possibilities for the first dog's spots by 1.
Now let's move on to our second dog. It's number of spots needs to have the same restrictions as the first dog, plus a new one. The new one is that the spots on the second dog, plus the spots on the first dog, cannot add to 0 (same thing as "cannot add to an integer multiple of 11"). In other words, s2 ≠ -s1. Let me formalize that with a new function, F1(n),
F1(n) = F0(n-1) - sn-1
and our restrictions on the second dog are:
s2 ≠ F0(2)
s2 ≠ F1(2)
Don't forget that Fn(m) is ultimately just a number that can range from 0 to 10. It's just some number. And it can be easily shown that F0(2) and F1(2) are unique. If they weren't unique but instead equal, it would mean that
F1(2) = F0(2), and expanding both sides gives,
-s1 = 0, or simply s1 = 0.
But that's not possible since s1 cannot be 0 (restriction on the first dog) so F0(2) and F1(2) must represent unique numbers.
You might notice something neat happening here. We've reduced our possible choices by 1 again. There are 10 numbers to choose from for the first dog, but only nine for the second. Now let's move on to the third dog.
The third dog has all the same restrictions as the first dog and second dog plus a new restriction. Well, a couple new restrictions. Firstly, we need to apply the F1 restriction twice, one for each of the previous dogs. The new restriction is that s3 ≠ - (s1 + s2). Formalizing that with a new function,
F2(n) = F1(n-1) - sn-1
our restrictions become,
s3 ≠ F0(3)
s3 ≠ F1(2)
s3 ≠ F1(3)
s3 ≠ F2(3)
Here I'm going to just remove the s3 ≠ F1(2) restriction. It turns out to be redundant for this particular puzzle. Remember, we are going to use a "proof by contradiction" approach. And later, if we can show that it is impossible to choose spots that falsify the puzzle statement with fewer restrictions, it is still impossible with greater restrictions. So the only restrictions we need to worry about for the third dog are:
s3 ≠ F0(3)
s3 ≠ F1(3)
s3 ≠ F2(3)
Now we know that F1(3) and F0(3) are not equal. But we can explicitly show that here. If they were equal,
F1(3) = F0(3), and expanding both sides gives,
-s2 = 0, or more simply s2 = 0, which is impossible due to earlier restrictions.
Similarly we can show that F2(3) and F1(3) are not equal. If they were,
F2(3) = F1(3), and expanding
F1(2) - s2 = - s2, and expanding more and simplifying,
s1 = 0, which is impossible.
But what about F2(3) and F0(3)? They are also not equal. If they were equal,
F2(3) = 0,
F1(2) - s2 = 0,
-s1 - s2 = 0, which is impossible due to previous restrictions on s2.
So finally, when choosing a number for s3, there are only 8 choices: down one from number of choices from s2.
So now is where our mathematical induction comes in. With each new dog, we place the same restrictions as with previous dogs plus an additional restriction which keeps the sum of all dogs, up to that dog from summing to 0. The new restriction comes in the form, for dog m
sm ≠ Fm-1(m)
where
Fn(k) = Fn-1(k-1) - sk-1.
[Edited above equation.]
So when we get to the eleventh dog, the restrictions on its spots are,
s11 ≠ F0(11)
s11 ≠ F1(11)
s11 ≠ F2(11)
s11 ≠ F3(11)
s11 ≠ F4(11)
s11 ≠ F5(11)
s11 ≠ F6(11)
s11 ≠ F7(11)
s11 ≠ F8(11)
s11 ≠ F9(11)
s11 ≠ F10(11)
Here's the kicker: There are 11 restrictions (starting at 0 and ending at 10, making 11 total). Each restriction removes a possible number from the choosing. But there are only 11 numbers total that we are working with. It is impossible to choose a number of spots for the eleventh dog, such that one can't sum the spots to 0 (where 0 is the same thing as an integer multiple of 11). Our "goal" of trying to disprove the puzzle statement is impossible.
[Edit: There are actually many more restrictions than just the 11 above. For example, there is only a single restriction involving the spot sum of exactly two dogs. And those are dogs 10 and 9, involving F2(11). But there could be restrictions involving the spot sum of any two dogs. But including those restrictions make the contradiction of the puzzle statement even more impossible. The eleven restrictions given above are alone sufficient to prove this puzzle by "proof by contradiction."]
Therefore, there will always be a way to select some or all of the dogs such that the total number of spots on selected dogs adds to an integer multiple of 11.
Last edited:
- #695
CompuChip
Science Advisor
Homework Helper
- 4,305
- 49
collinsmark said:
If there is a dog with no spots, you pick that one, and you have 11n spots in total, with n integer
- #696
Enigman
- 643
- 312
This belongs more to O_S' Math challenge thread rather than my thread...Congrats collinsmark!
- #697
lisab
Staff Emeritus
Science Advisor
Gold Member
- 2,026
- 623
CompuChip said:If there is a dog with no spots, you pick that one, and you have 11n spots in total, with n integer
I think a Dalmatian with no spots is called a "White Dog".
- #698
collinsmark
Science Advisor
Homework Helper
- 3,443
- 3,417
Okay, here's a rather morbid one. (Then again, many enigmas/riddles are rather morbid. So this one is in good company.)
You are investigating what might be a murder, or maybe it's a suicide. You haven't figured it out yet.
A man was found dead by hanging.
The body was found hanging by a rather short rope attached to a chandelier (the rope was just long enough to be tied to the chandelier on one end and to make a noose on the other). The room has particularly high ceilings and the body is high enough off the ground such that one couldn't jump up to grab the rope used as the noose. (Even if the rope hadn't yet been tied into a noose, it's still too high off the ground to jump and grab.)
The room he was found in was securely locked from the inside (you and the police had to break the door down to gain entrance). The room has no other doors, windows or any other entrances or exits (no tunnels either, or any holes in the ceiling or anything like that). (Presumably the room isn't air-tight though; you don't need to be concerned with suffocation or carbon dioxide poisoning).
The room is also devoid of furniture. As a matter of fact, it's nearly an empty room. The only things in the room are the man/body, the rope, the chandelier the rope is attached to, and a water-stain on the floor.
Was this man murdered? Did he commit suicide? How did he die?
You are investigating what might be a murder, or maybe it's a suicide. You haven't figured it out yet.
A man was found dead by hanging.
The body was found hanging by a rather short rope attached to a chandelier (the rope was just long enough to be tied to the chandelier on one end and to make a noose on the other). The room has particularly high ceilings and the body is high enough off the ground such that one couldn't jump up to grab the rope used as the noose. (Even if the rope hadn't yet been tied into a noose, it's still too high off the ground to jump and grab.)
The room he was found in was securely locked from the inside (you and the police had to break the door down to gain entrance). The room has no other doors, windows or any other entrances or exits (no tunnels either, or any holes in the ceiling or anything like that). (Presumably the room isn't air-tight though; you don't need to be concerned with suffocation or carbon dioxide poisoning).
The room is also devoid of furniture. As a matter of fact, it's nearly an empty room. The only things in the room are the man/body, the rope, the chandelier the rope is attached to, and a water-stain on the floor.
Was this man murdered? Did he commit suicide? How did he die?
Last edited:
- #699
CompuChip
Science Advisor
Homework Helper
- 4,305
- 49
I know this one. It's pretty cool!
- #700
JorisL
- 489
- 189
I see what you did there CompuChip. Know it as well
- #701
Ibix
Science Advisor
- 13,433
- 15,979
He climbed on a block of ice to tie the rope. It subsequently melted, leaving a water stain and a locked room mystery.
- #702
collinsmark
Science Advisor
Homework Helper
- 3,443
- 3,417
This is correct. (It is the solution to the hanging man enigma.)Ibix said:
- #703
Ibix
Science Advisor
- 13,433
- 15,979
Regarding the dalmations, I think collinsmark's solution is correct, but can be expressed rather more simply.
It is indeed a proof by contradiction. Imagine a set of eleven dogs from which we cannot pick a subset divisble by eleven. Line the dogs up in a row - sit! Stay! Let us say that the ith dog has Si spots.
In front of each dog, write the remainder when its spots plus the spots of all dogs to its left are divided by eleven. That is, in front of the ith dog, write the remainder when \sum_{k=1}^i S_k is divided by 11.
You now have eleven numbers. If any two of them are the same, then the intervening dogs' spots must add to a multiple of 11 (so if the nth and mth remainders are the same then \sum_{k=n+1}^m S_k is divisible by eleven.
So if no sets are divisible by eleven then you have eleven distinct non-zero remainders from division by eleven - but there are only ten such numbers. That is a contradiction - therefore you can always find a subset whose spots add to a multiple of eleven.
In front of each dog, write the remainder when its spots plus the spots of all dogs to its left are divided by eleven. That is, in front of the ith dog, write the remainder when \sum_{k=1}^i S_k is divided by 11.
You now have eleven numbers. If any two of them are the same, then the intervening dogs' spots must add to a multiple of 11 (so if the nth and mth remainders are the same then \sum_{k=n+1}^m S_k is divisible by eleven.
So if no sets are divisible by eleven then you have eleven distinct non-zero remainders from division by eleven - but there are only ten such numbers. That is a contradiction - therefore you can always find a subset whose spots add to a multiple of eleven.
- #704
collinsmark
Science Advisor
Homework Helper
- 3,443
- 3,417
Yes. I like your solution in that it's far easier to conceptualize compared to mine, me thinks.Ibix said:
It does add some insight into what I was doing though. In your solution, the striving to keep any resulting number (in front of the dog) from being 0 or from being equal to any other dog's number, is equivalent to my solution's Fn number restrictions removing a unique, non-zero number as a valid choice (for each dog). After that, your solution and mine are pretty much identical in the fact that we run out of numbers before we run out of dogs.
- #705
consciousness
- 132
- 13
Next one-
A group of prisoners are trapped in a forcefield (like an invisible wall). These prisoners are perfectly brave, meaning that a prisoner would attempt an escape if he has any positive probability of success. The prisoners are monitored by a guard who has only one bullet in his gun, but who also has perfect marksmanship skills (he never misses).
The prisoners have overheard the guard saying "I have only one bullet left!". A maintenance technician needs to tune up the forcefield generator, and so for one second, the forcefield is released. How can the prisoners be kept detained?
A group of prisoners are trapped in a forcefield (like an invisible wall). These prisoners are perfectly brave, meaning that a prisoner would attempt an escape if he has any positive probability of success. The prisoners are monitored by a guard who has only one bullet in his gun, but who also has perfect marksmanship skills (he never misses).
The prisoners have overheard the guard saying "I have only one bullet left!". A maintenance technician needs to tune up the forcefield generator, and so for one second, the forcefield is released. How can the prisoners be kept detained?
- #706
CompuChip
Science Advisor
Homework Helper
- 4,305
- 49
Taking "any positive probability of success" literally, the problem is that if all n > 1 prisoners dash out, the guard can only shoot one of them so they have a probability of (n - 1)/n of escaping. So I'm thinking that this is the "problem" you need to solve / prevent.
Is it something as simple as saying "I will shoot the first one to come out", after which they will all wait for another one to go first?
- #707
consciousness
- 132
- 13
Correct.
More clear might be "the first person to lift his leg will be shot."
- #708
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
- 5,705
- 1,589
consciousness, if the guard does that then as a prisoner I
shove another prisoner, making him stumble and wasting the guard's bullet
- #709
Enigman
- 643
- 312
Or everyone agrees to go together...
1/n chance...
1/n chance...
- #710
consciousness
- 132
- 13
Office_Shredder said:
The best answer is perhaps then "the first one to make any movement in the next second will be shot!"
Enigman said:
There is bound to be a small time lag so technically they can't go together. It is assumed that the guard is very alert. He can detect this small lag and know who moved first. (In hindsight a programmable turret gun would have worked better)
- #711
Enigman
- 643
- 312
So? The other prisoners still escape. The act of moving first is random and hence all of them as far they are concerned have 1 -1/n chance of survival.consciousness said:
- #712
consciousness
- 132
- 13
Enigman said:
I always made the assumption that the prisoners would wait for others to move and ensure their survival. But now I am convinced that your post destroys this solution!
So the correct answer hasn't been posted yet. An alternative solution that doesn't warrant assumptions about the behaviour of the prisoner exists.
- #713
consciousness
- 132
- 13
(The prisoners know that the other prisoners are perfectly brave.)
Hint-
Hint-
You can assign numbers to make the prisoners distinguishable.
- #714
JorisL
- 489
- 189
Shoot the technician and wait until more bullets arrive. This is assuming the force field won't break down if the tune up gets delayed a little.
- #715
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
- 5,705
- 1,589
Assuming it takes the prisoners more than one second to escape the guard's line of fire: Assign the prisoners numbers 1,...,n. Then the guard announces "When the shield goes back up I will kill the prisoner whose number is lowest that is not inside the shield.
1 can't try to escape or he will die. 2 knows this, so knows he can't try to escape either. Etc.
1 can't try to escape or he will die. 2 knows this, so knows he can't try to escape either. Etc.
- #716
Enigman
- 643
- 312
Next one-
.-- --- .-- / -.-- --- ..- / -.-. .- -. / ... . . / -- .
Google search is allowed.
.-- --- .-- / -.-- --- ..- / -.-. .- -. / ... . . / -- .
Google search is allowed.
- #717
Enigman
- 643
- 312
Running out of ideas for Enigmas...
- #718
consciousness
- 132
- 13
Office_Shredder said:
Correct!
Also shooting the tecnician might work but the prisoners will most probably not believe the guard.
- #719
cArma
Enigman said:Next one-
Samuel Morse. No need to search. Answer is in the URL of the picture.
- #720
Enigman
- 643
- 312
cArma said:
Not the question ...
What does that post mean?
A bit 'under the belt' Enigma...
But since you quoted it, it should be easier...
Similar threads
- · Replies 20 ·
- · Replies 57 ·
Challenge
Basic Math Challenge - September 2018
- · Replies 38 ·
- · Replies 28 ·
Challenge
Math Challenge - October 2018
- · Replies 71 ·
Challenge
Math Challenge - December 2018
- · Replies 67 ·
Challenge
Can You Solve These Math Challenges?
- · Replies 82 ·
Admissions
Comments on PhD Statement of Purpose
- · Replies 6 ·
- · Replies 15 ·
Challenge
Intermediate Math Challenge - May 2018
- · Replies 61 ·