Solve Enjoyable Enigmas with Mr.E's Challenge

[Enigman]

mathematical induction may help if the previous post is correct...

 

[collinsmark]

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.

 

[CompuChip]

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.

Spoiler

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.).

 

[collinsmark]

I have eleven dalmations. Prove that it is always possible to select some or all of them such that the sum of the spots of the selected dogs is an integer multiple of eleven.

You may consider eleven bunches of grapes, if that makes the problem more familiar.

Solved it! 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.

Spoiler

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 s₁ be the number of spots on dog 1, s₂ be the number of spots on dog 2, and s_n 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, s₁, 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 F₀(n), such that
F₀(n) = 0,
for all n.
Now we formalize our restriction on s₁,
s₁ ≠ F₀(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, s₂ ≠ -s₁. Let me formalize that with a new function, F₁(n),
F₁(n) = F₀(n-1) - s_n-1
and our restrictions on the second dog are:
s₂ ≠ F₀(2)
s₂ ≠ F₁(2)
Don't forget that F_n(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 F₀(2) and F₁(2) are unique. If they weren't unique but instead equal, it would mean that
F₁(2) = F₀(2), and expanding both sides gives,
-s₁ = 0, or simply s₁ = 0.
But that's not possible since s₁ cannot be 0 (restriction on the first dog) so F₀(2) and F₁(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 F₁ restriction twice, one for each of the previous dogs. The new restriction is that s₃ ≠ - (s₁ + s₂). Formalizing that with a new function,
F₂(n) = F₁(n-1) - s_n-1
our restrictions become,
s₃ ≠ F₀(3)
s₃ ≠ F₁(2)
s₃ ≠ F₁(3)
s₃ ≠ F₂(3)
Here I'm going to just remove the s₃ ≠ F₁(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:
s₃ ≠ F₀(3)
s₃ ≠ F₁(3)
s₃ ≠ F₂(3)
Now we know that F₁(3) and F₀(3) are not equal. But we can explicitly show that here. If they were equal,
F₁(3) = F₀(3), and expanding both sides gives,
-s₂ = 0, or more simply s₂ = 0, which is impossible due to earlier restrictions.
Similarly we can show that F₂(3) and F₁(3) are not equal. If they were,
F₂(3) = F₁(3), and expanding
F₁(2) - s₂ = - s₂, and expanding more and simplifying,
s₁ = 0, which is impossible.
But what about F₂(3) and F₀(3)? They are also not equal. If they were equal,
F₂(3) = 0,
F₁(2) - s₂ = 0,
-s₁ - s₂ = 0, which is impossible due to previous restrictions on s₂.

So finally, when choosing a number for s₃, there are only 8 choices: down one from number of choices from s₂.

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
s_m ≠ F_m-1(m)
where
F_n(k) = F_n-1(k-1) - s_k-1.
[Edited above equation.]

So when we get to the eleventh dog, the restrictions on its spots are,
s₁₁ ≠ F₀(11)
s₁₁ ≠ F₁(11)
s₁₁ ≠ F₂(11)
s₁₁ ≠ F₃(11)
s₁₁ ≠ F₄(11)
s₁₁ ≠ F₅(11)
s₁₁ ≠ F₆(11)
s₁₁ ≠ F₇(11)
s₁₁ ≠ F₈(11)
s₁₁ ≠ F₉(11)
s₁₁ ≠ F₁₀(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 F₂(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.

 

[CompuChip]

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.

If there is a dog with no spots, you pick that one, and you have 11n spots in total, with n integer

 

[Enigman]

This belongs more to O_S' Math challenge thread rather than my thread...Congrats collinsmark!

 

[lisab]

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".

 

[collinsmark]

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?

 

[CompuChip]

I know this one. It's pretty cool!

 

[JorisL]

I see what you did there CompuChip. Know it as well

 

[Ibix]

Spoiler

He climbed on a block of ice to tie the rope. It subsequently melted, leaving a water stain and a locked room mystery.

 

[collinsmark]

Spoiler

He climbed on a block of ice to tie the rope. It subsequently melted, leaving a water stain and a locked room mystery.

This is correct. (It is the solution to the hanging man enigma.)

 

[Ibix]

Regarding the dalmations, I think collinsmark's solution is correct, but can be expressed rather more simply.

Spoiler

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 S_i 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.

 

[collinsmark]

Regarding the dalmations, I think collinsmark's solution is correct, but can be expressed rather more simply.

Spoiler

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 S_i 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.

Yes. I like your solution in that it's far easier to conceptualize compared to mine, me thinks.

Spoiler

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 F_n 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.

 

[consciousness]

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?

 

[CompuChip]

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.

Spoiler

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?

 

[consciousness]

Spoiler

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?

Correct.

Spoiler

More clear might be "the first person to lift his leg will be shot."

 

[Office_Shredder]

consciousness, if the guard does that then as a prisoner I

Spoiler

shove another prisoner, making him stumble and wasting the guard's bullet

 

[Enigman]

Or everyone agrees to go together...
1/n chance...

 

[consciousness]

consciousness, if the guard does that then as a prisoner I

Spoiler

shove another prisoner, making him stumble and wasting the guard's bullet

Spoiler

The best answer is perhaps then "the first one to make any movement in the next second will be shot!"

Or everyone agrees to go together...
1/n chance...

Spoiler

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)

 

[Enigman]

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)

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]

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.

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.

 

[consciousness]

(The prisoners know that the other prisoners are perfectly brave.)
Hint-

Spoiler

You can assign numbers to make the prisoners distinguishable.

 

[JorisL]

Spoiler

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.

 

[Office_Shredder]

Spoiler

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.

 

[Enigman]

Next one-

.-- --- .-- / -.-- --- ..- / -.-. .- -. / ... . . / -- .
Google search is allowed.

 

[Enigman]

Running out of ideas for Enigmas...

 

[consciousness]

Spoiler

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.

Correct!

Also shooting the tecnician might work but the prisoners will most probably not believe the guard.

 

[cArma]

Next one-

Spoiler

Samuel Morse. No need to search. Answer is in the URL of the picture.

 

[Enigman]

Spoiler

Samuel Morse. No need to search. Answer is in the URL of the picture.

Not the question ...
What does that post mean?
A bit 'under the belt' Enigma...
But since you quoted it, it should be easier...