Math and Logic Puzzles

[Mitillos]

Wouldn't gxh6, Kg5, Qg8, Kxh6, Qg7 work?

[Mitillos]

^Pretty much this. Maybe Timmy was also buying ice cream for his sister, and wanted two small ones. Since the ice cream man doesn't know Timmy, he also doesn't know if Timmy has a sister. Therefore, I call bullshit on this one.

[Mitillos]

You never mentioned Timmy's reaction, at all. And maybe Timmy is a shy boy, who doesn't feel comfortable raising a fuss. (Also, why was neither boy asked about a specific flavour they wanted? This ice cream man is obviously not very good.) Anyway, you're now saying that Timmy asked for a single ice cream, but that contradicts your statement that Timmy got the ice cream "without asking".
The claim of bullshit stands.

[Mitillos]

You can always guarantee at least 8 points. Draw the lines through each pair of given points. Since there are five such points, no three of which are colinear, there will be 5C2 = 10 such lines. Each such line will be parallel with at most 1 other line, and coincide at one of the given points with 6 other lines (three at each of its given points). This leaves at least 2 lines it can cross at a point that is not already given. This means that in the worst case there are 10 points, each of which can be chosen for a score of +2. (Note that it's impossible for two lines to cross at a given point, without being defined by it, as the five original points score 0.) So, even if no three crossing points are colinear, and no two crossing points are colinear with a given point that does not define them, you are guaranteed to get a minimum of 8 points, by picking four of these crossing points.

This method is very naive, of course, so it's possible that there's some other way that can give you more points.

[Mitillos]

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.

[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?

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

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

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

[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 ω.

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

[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?

[Mitillos]

Addition is usually commutative.

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

[Mitillos]

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

[Mitillos]

We both survive. Well done.

[Mitillos]

For 1) I assume you actually want the limit as n goes to infinity of (valid configurations on n disks)/(all configurations on n disks). This is 0.
Suppose you are dealing with n disks. At least one of the pegs has at least N = ceiling(n/3) disks. There are at least N! ways to arrange these, of which exactly one is valid (the one without any inversions). So, the proportion of valid configurations on n disks to all configurations on n disks is no more than 1/(ceiling(n/3))! (in fact, it's significantly smaller, if you're careful about calculating things, but for this argument, a crude bound is good enough), which goes to 0 as n goes to infinity.

By the way, finding the number of valid configurations for n disks is easy. It's a matter of taking the disks in decreasing order, and simply picking the peg to place them, so it's 3^n. Calculating the total configurations is harder, though, as it would take the sum of products of permutations and Stirling numbers. I believe the first four terms of the sequence are 3, 12, 60, 324, which could be 3 times the sequence https://oeis.org/A225621, but I don't feel like digging further into this, right now.

EDIT: Scratch my part 2) stuff. I wasn't thinking clearly.

[Mitillos]

@serra: You're right about there being (n + 2)!/2 total configurations, of course.
Also, if you want another direction for your students to explore, you can also tell them to consider a modification to ToH with a second "middle" peg, for 4 pegs in total. (My sig actually comes from just such a discussion.)

Next time I teach Intro to Discrete Maths or Combinatorics, I'm definitely stealing some of this.

[Mitillos]

WLOG let n < m. Assume BA = I_m. Denote the columns of A as a_i and the columns of I_m as e_i. Then, we can rewrite the given equation as the family of equations B(a_i) = e_i. This implies that each e_i is in the column space of B. This further implies that the rank of B is m. However, rank(B) <= min(n, m) <= n < m. Contradiction.

[Mitillos]

It had bloody better be, I'm teaching undergrad linear algebra this semester. (Yes, it's cheating a bit, I know.)
I should consider putting that question in an exam.

[Mitillos]

@Sob: (Cool choice of name, by the way.) For the first question in 3, your wording is any positive number n. I'm not sure about that, but I think that for positive integers n, the product is 1 + (-1)^(n-1), so it's 0 for even n, and 2 for odd n. The derivation can be done separately for odd and even n. I haven't looked at the second part, yet.