Math and Logic Puzzles

[Mitillos]

Part 1 is indeed easy, and Who's answer works. Zorb's slightly more complicated answer probably works too, but I haven't looked at it carefully.

Part 2 may be difficult, but it is definitely not impossible. Also, there are two interesting variants to 2:

2a) Change the number of colours to k.
2b) Allow prisoners to hear the previous responses (originally they can't in 2, and I should have mentioned this). How many people must you lose, at most?

[Who]

Wait what? What do you mean "can't hear previous responses"? Can't hear the guesses? Then it's definitely impossible.

[Mitillos]

@Who: I am sorry to contradict you again, but you are incorrect. You can save all but finitely many of the prisoners, even if they can't hear previous guesses.

Edit: Let me qualify that, by saying again that we are assuming that all the prisoners can perfectly receive and process infinite information, even though that is not possible in the real world.

[Zorblag]

@Mitillos do you intend to have the prisoners know whether the previous prisoners lived or what color their hats were? Clearly not both as that would be equivalent to hearing the guesses. Troll assumed neither was the case, but Troll's solution to part one did rely on hearing previous answers (as well as having perfect reasoning.)

-Zorblag R`Lyeh

[Mitillos]

@Zor: No to both questions. Hearing previous guesses on part 1 is fine; not mentioning this difference between the two situations was my mistake.

[Who]

Spoiler:

Let S be the set of functions which map binary strings to the set {0,1}.
By the well ordering theorem, S has a well-ordering. Agree on such a well ordering in advance.
Each prisoner looks at the prisoners in front of him, looks at the elements of S, finds all functions which would lead to only a finite number of prisoners dying, picks the least such function, and applies it to himself.

They will all choose the same function. Proof:
If prisoner m sees a finite number of prisoners live with the function, prisoner n will too. There are only a finite number in between them. Thus, the sets both are dealing with are the same, thus both sets will have the same least element, thus they'll both pick the same function.

There is always such a function. Proof:
There are two cases:
If the string does not eventually repeat forever, no substring matches another substring which starts at a different place. Thus, there exists a function which saves everyone.
If the string does eventually repeat, there is a function which saves everyone in the repeating part. (Just guess the hat of the thing in the repeat before the next part of it you see), thus only the prisoners before the repeat die, thus there exists a function in which finitely many prisoners die.
Thus the subset is nonempty.

[Who]

For part b, do they get to hear whether or not the person behind them lived?

Irrelevant.

Spoiler: a

The original solution but replace the 2s with ks.

Spoiler: b

The first prisoner checks the function, sees the last prisoner who would have died, says the parity up to that prisoner. (Might die). If nobody ahead of him dies guesses according to the function.
The nth prisoner checks the function found, if anyone ahead of him would die by it he guesses according to parity and previous guesses. If nobody ahead would die, guesses according to the function.
(Prisoner who would have died last by the function will die, because since nobody ahead of him dies he guesses according to the function)
At most 2 deaths. I don't think it's possible to get at most 1 death, but no proof.

[Mitillos]

Nifty. You can get the same result, by partitioning binary (or k-ary) sequences into equivalence classes, where two sequences are in the same class if they have a finite number of elements different.

For the second variant, if you label these sequences based on whether the number of elements which is different is odd or even, the first prisoner can use his guess to give this information to everyone ahead of him, so that only he need potentially die.

[Scigatt]

Let's bring back the prisoners and hats.

There is a countably infinite number of prisoners, who are being offered the chance to be released. They will each have a black or white hat placed on their head, and be arranged in a line, so that each prisoner can see all the prisoners and hats ahead of him, but not behind or on him (don't worry about how they will manage to see an infinite number of people, just go with it). Then, starting from the person who can see everyone else, they will each make a guess as to whether their hat is black or white. Those who get it right can leave, but the rest will be killed. The prisoners can confer for a strategy in advance, but not during the event.

1) For any given fraction, find a strategy that saves at least all but that fraction of the prisoners.
2) Find a strategy that saves all but a finite number of prisoners.

What if the prisoners are arranged to have order type ω + (ω* + ω) ⋅ η?

[TheDominator37]

What is 3+2?

[Mitillos]

What if the prisoners are arranged to have order type ω + (ω* + ω) ⋅ η?

For the purpose of this problem, it can be assumed that each individual prisoner is assigned a fixed natural number for his position, so we don't run into that problem, given that this automatically implies an order type ω.

[Who]

What is 3+2?

10.
(In base 10)

[Felissan]

What is 3+2?

Spoiler: Answer

[animorpherv1]

Solution re: Mtillos. Pass on my end if I'm right.

Spoiler: This is a solution with a 50% chance of success to save everyone, 50% chance to save all but one for black & white

While the prisoners are talking, they determine to give each colour a value. For this example, if the person guessing sees an odd number of black hats, that person will say black. Otherwise, they say white.

The first person will see all black and all hats but their own and answer accordingly. Before the next person goes, they check the number of hats they see. So for example, if guesser #1 says 'black', that means he sees an odd number of black hats. If guesser #2 sees an odd number of black hats, that means their hat is white, then answers 'white'.

This continues down the line.

[Mitillos]

@ani: Your answer works for a finite number of prisoners. Unfortunately, here we have an infinite number of prisoners. There is no "all hats" or "all black hats" to see.

[animorpherv1]

Sadly that's the only version of the problem I know.

[Mitillos]

Necromancy powers, go!

You have been tasked by a king to make sure that the tribute paid to him by vassal states is not made of counterfeit gold. Specifically, each year each of the five vassals must send one hundred gold ingots, each weighing 10kg. The number of ingots they send each year is correct, but the king has information that something is amiss with the ingots themselves. He will let you use the royal scale which, when loaded with any number of ingots, will give you their precise weight. Unfortunately, operating the scale is both time-consuming and expensive, so the king will only allow you to use it once each year. If you fail to find which of the vassals have not paid their appropriate tribute, you will be put to death. Also, the king doesn't like other people touching his gold too much, so if you use more ingots than is absolutely necessary, you will be put to death.

1) On the first year, exactly one of the vassals is sending fake ingots, which are exactly 1kg off the correct weight. You do not know in advance if they are 9kg or 11kg, but you know that they all weigh the same.
2) On the second year, some of the vassals are sending fake ingots, all of which are known to only weigh 9kg each.
3) On the third year, some of the vassals are sending fake ingots which could be lighter or heavier than normal by 1kg. The ingots from each individual vassal are the same weight, but different vassals can send different ingots.

What strategies will you use each year, to find who is sending fake ingots?

[KuroiXHF]

What is 3+2?

Spoiler: Answer

He asked what 3 + 2 is, not 2 + 3!

[Mitillos]

Addition is usually commutative.

[Who]

Spoiler: Gold

1) Weigh 1 ingot from the first vassal, 2 from the 2nd, 3 from the 3rd, 4 from the 4th, none from the 5th.
If the total is 100 kg, it's the 5th vassal. If the total is 104 kg or 96 kg, it's the 4th. If it's 103 or 97, it's the 3rd. If it's 102 or 98, it's the 2nd, if it's 99 or 101, it's the first.
2) 1,2,4,8,16. Subtract the weight from 310, convert to binary, look at digits.
3 I need to think about more in case there's a way which involves touching less gold, I don't want to be put to death. My gut instinct says 1 3 6 9 27 81, but that seems inefficient. If he had more vassals I know of tricks which might help, but he has too few vassals for them.

[Mitillos]

@Who: Correct on first and second year.

Also, after someone solves year 3, you can go ahead and expand with your tricks for more vassals.

[Mitillos]

@Who: After you solved the first two parts, the king still wanted to have you killed. He said that you are trying to trick him, and that you probably could have done at least the second part with fewer than 31 ingots, insisting that you could have cut some corners like you did in the first part. I tried telling him that this was not possible, but he wouldn't let me speak, and had me imprisoned for contradicting him. Then, in his anger, he decided that you (or someone else) must prove that you used the smallest number of ingots possible in both your answers, otherwise he will have us both executed. Also, the same will hold for the third part, once someone answers it.

[Who]

2 proof)
There are 32 total possible combinations of fakes. If n ingots are weighed, the scale will return an integer result from 9n to 10n, inclusive. Thus, there are n+1 total possible answers the scale can give. There must be a surjection from the set of scale results to possibilities that we use to determine guilt, thus the set of answers must be at least as big as the set of possibilities, thus the set of answers must be at least of size 32, thus there must be at least 31 ingots used.
1 proof:
The amount from two different vassals cannot be the same, if it were the same then it would be impossible to distinguish which one is guilty of exactly one of those two is guilty. All ingot amounts must be nonnegative, thus it cannot decrease below 0, all must be integers, I took the set of 5 distinct nonnegative integers with the smallest sum.
3 is in fact 1 3 9 27 81. Proof incoming.

[Mitillos]

Very nice. And yes, your answer for 3 is also correct. Looking forward to the proof.

[Who]

The proof I thought would work for 3 is blatantly wrong. (I thought that it would just be an argument about how many possibilities like 2, but then with the added section where you prove that two different but equivalent possibilities (For example: vassal 1 gives 9 and vassal 1 gives 11) can't cancel out, but that line of argument won't work because there are 364 total possibilities for the scale to return with 121 ingots, but there are only 243 possibilities for answers, that argument just says you need at least 81 ingots) Also I'm back to thinking that the answer is wrong.

I cannot do basic arithmetic.