Math and Logic Puzzles

[Who]

Spoiler: Proof of 3

Lemma: For any two disjoint nonempty sets of vassals, the total number of ingots on the scale from the first set cannot equal the total number of ingots on the scale from the second set. If this were the case, it would be impossible to distinguish between (first set is guilty with all 9s and second set is innocent) and (second set is guilty with all 9s and first set is innocent).
The scale can return anything from 9n to 11n, thus there are 2n+1 possible answers. There are 3^5=243 possibilities, thus we need at least 121 ingots if we are to detect all possibilities.
"But wait!" says the King, "I don't need you to distinguish between all possibilities, only guilt and innocence. I don't care if you know that Vassal 1 gave me 9kg ingots or 11, I only care that you know it's fake".
The King is correct, but unfortunately it's impossible to map equivalent strings to the same weight if we are to preserve the property that nonequivalent strings map to different weights. Proof:
Suppose we have numbers of ingots on the scale which map two equivalent strings to the same weight. That is, you can replace some vassals who gave 9 with 11 and some vassals who gave 11 with 9, and the total weight will be the same. (You do not replace any 10s, and you do not replace anything with 10). Then, the total ingots provided by the vassals who gave 9 which got swapped to 11 is the same as the total ingots provided by the vassals who gave 11 which got swapped to 9. This is illegal, as per the lemma, unless both sets are empty. (If one's empty the other has to be too, since everyone needs an ingot on there to distinguish between everyone real and everyone but them real)
Thus, the type of fake must be distinguished, thus all possibilities need to be accounted for, thus at least 121 ingots are needed.

Also, since I don't think I ever actually said: To find guilt just subtract 9*121 from the total returned, convert to base 3, anyone who has a 1 in their corresponding digits place is legit, anyone with a 0 or a 2 is fake.

Spoiler: Trick I wanted to use but would not have returned enough information even if it would beat 3^n

If there were more vassals, I could in binary add an unbounded constant number of bits, or add a logarithmic number of bits, or add bits and have the last added bit be not a bit but a a value. What I wanted to do was add 32 ingots from every vassal, thereby telling the sum of the total offness, I thought that from there I might have been able to do something, but I couldn't because the proof generalizes to any number of vassals. Also for a while I considered adding a bit to every pair of bits, yielding which I think might lose to trinary with 5 vassals but not more. None of these would have worked, the proof generalizes to any positive integer number of vassals.

[Mitillos]

We both survive. Well done.

[Sudo_Nym]

Suppose we're going to play a game. The rules of the game are such: using an ordinary deck of cards whose cards have been shuffled, we each call out a sequence of colors (say, Red/Black/Red), then deal out the cards one at a time. Any time three cards in a row are dealt in a way that matches one of our called sequences, we take all three cards as a trick, and then continue dealing until all the cards are dealt, and then the player with the most tricks win.

Assuming I call RBR, what sequence should you call to maximize your chance at winning?

There is a general rule that allows P2 to maximize winnings against any sequence, if somebody feels like working that out as well.

[Who]

I think it's RRB but I can't come up with a proof of optimality. Brute force seems possible, it's only 7 possibilities, but that feels like cheating.
General solution would be (not2)(1)(2), so that to get theirs they have to not be yours (Yours ends in 12, meaning that their 3 card trick 123 is secretly four cards, 2123, unless it's the first three cards), and by picking not-2 they don't do the same thing to you. (BRB would steal their tricks but also make them steal yours)
Also I treated it as random binary strings with 50% chance of either being next, I don't think the fact that it's cards changes that much but I'm not 100% sure.

[Sudo_Nym]

Yeah, that's the basic logic. BRR beats RBR 922 times out of 1000 in the simulation, if you're curious, and you're right about why it works. Cards instead of coin flips, if you're curious, party because you can "steal" cards, but not really recorded flips, and also because the finite number of cards in the deck raises P2's odds somewhat.

[Sudo_Nym]

Two men jointly own x cows. They sell the cows for x dollars a piece, and use the money to buy sheep at $12 each. They don't have exactly enough money from the sale of the cows to buy an integer number of sheep, so they buy a lamb with the remainder, then divide the flock so that each man has an equal number of animals. They both decide to sell their flocks at market value; the man who agreed to take the lamb is a little shortchanged, though, so the other man gives him his harmonica to make the deal even. How much was the harmonica worth?

[Who]

Is it assumed that all goods (Lamb/Harmonica) are worth an integer number of dollars?

Given that there are x cows it has to be

[implosion]

Spoiler:

After some fiddling, is the answer "something something quadratic residues mod 12? Actually scratch that, mod 24?"

The harmonica is worth $4.

We know that they bought an odd number of sheep with leftover money, therefore:
x^2 mod 24 ϵ {13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23}. Quadratic residues mod 24 can be broken down into quadratic residues mod 3 (which can be 0 or 1) and residues mod 8 (which can be 0, 1, or 4) which further reduces this list to {16}. So we know that the number of dollars that the number of dollars that they have to spend must be congruent to 16 mod 24, meaning that they will buy some even number of sheep (for some amount of money that is a multiple of $24) and then use the remaining $16 to buy one more $12 sheep and a $4 lamb.

Therefore, after they sold their flocks, the man with the sheep got $8 more, so he owed the other man $4 (because all the money he gives is both lost by him and gained by the other man), which is the value of the harmonica.

[Sudo_Nym]

Implosion is correct.

[Sudo_Nym]

Suppose you're a King, and one day, messengers from two different lands come bearing cash to bribe you for your support. The first messenger has an infinite number of envelopes; the first envelope contains $1, the second contains $2, the nth envelope contains $n, and so on. The second messenger also has an infinite number of envelopes, such that the first contains $2, the second contains $4, and the nth contains $2n.

The second messenger claims that you should thus aid him, because for each envelope the first gave you, his envelope contains twice as much cash, and therefore, his bribe is greater. The first counters that his envelopes contain every integer amount of dollars, while the second messenger only brought half the integers, and therefore his own bribe is greater. Which one is correct?

Yes, I know it's silly.

[Who]

Real answer: Neither is correct. It doesn't make sense to talk about who brought "more" because they both brought a divergent sum. What does make sense, is to say that opening envelopes takes time, assuming that you can't just open an arbitrary envelope and either you have to open all the envelopes which precede any envelope you open or you have to at least flip through the envelopes until you find the one you want (So opening the nth envelope without the preceding ones takes linear time based on n), the second messenger brought money which was easier to access, and thus you should aid him.
Specific refutations to both arguments:
They both brought the same number of envelopes, so the first one's claim that the second only brought half of his is wrong.
The claim of the second is true, if you look at it in a specific way. But there are different orderings of envelopes which lead to most of the first's being greater. For example, if you reorder the envelopes of the first to go 1,2,3,4,8,16,32,5,64,128,256,512,1024,2048,6,... (2^n except every 2^n elements there's a small element), yes the first occasionally has an envelope smaller than the second but after every envelope opened after the first few the first has given much much more.

Silly answer: Uhh, "bribes" should be positive amounts of money, not negative. The first one gave -1/12$. The second one gave -1/6$. (That's how it works, right?) Send both of these con artists home. If you're forced to aid one aid the first one I guess because he took less money from you.

[serrapaladin]

I've been working on this problem as an application of some undergrad math. Any comments would be appreciated.

---

The Tower of Hanoi (ToH) is a popular kid's toy and mathematical game consisting of different sized disks on three rods. Disks may only rest on smaller disks, and you may only move one disk at a time. It looks like this:



Let us consider the infinite-ToH, where there are infinitely many disks on three rods.

1) A configuration of disks of the ToH is valid iff no disk rests on a smaller disk. What proportion of possible configurations of the infinite-ToH are valid?

2) Let us define the r-neighbourhood of an initial valid configuration as the set of other valid configurations that can be reached in at most r valid steps. Let the r-mass M(r) of a point be the number of configuration in its r-neighbourhood. Find the relationship between the average r-mass <M(r)> and r.

[Who]

In 1), are the disks labeled by the natural numbers? Also what do you mean by "proportion"? The limit of the proportions of arbitrarily large but finite ToHs? There are the same number of valid configurations as there are configurations.

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

[serrapaladin]

0 is correct, I should probably work on the wording. By configurations I mean putting any disc anywhere, while valid ones are ones in the right order. Finding an analytic expression for n discs is an interesting idea.

Part 2 is probably going to be more guided, but I thought I'd see if it makes any sense as is.

For both parts, it's probably going to push people towards interpreting the task as an undirected graph.

[Who]

I think you're much better off not using the word "infinite".

An infinite tower of Hanoi could exist but it would look very different to the arbitrarily large ones you're talking about. There are continuum many configurations and continuum many valid configurations, so proportions make no sense. "Average" doesn't make much sense unless they're all (or almost all) the same.

[serrapaladin]

I believe the total number of configurations for n disks Is (n+2)!/2. And the limit of the ratio that gives is 0, for which one could use something like l`hopital. Unless I'm missing something, you can avoid the sum of permutations by dividing the discs among rods before labelling them.

I guess referring to the limit of arbitrarily large n makes this more reasonable. The sets are both countably infinite, but the limit of the ratio of cardinality is 0.

Another question that comes to mind is the maximum number of steps between two valid configurations (ie the graph diameter) as a function of n.

[Who]

The sets are both countably infinite

No, they're uncountable.

Consider the function f maps valid configurations to the power set of N, where f(configuration) = the set of disks on the first peg. f is surjective, thus the sets are at least continuum. (They are continuum, not larger. There are two proofs of this, you could either be formal and define an injection to P(N)^3 times [the set of functions from N to N]^3, or you could just say its obvious because they can't be that big)

Maximum number of steps is 2^n-1, the number of steps needed to solve the game in its normal version.

[serrapaladin]

You're right, of course, as there are 3^n configurations.

The number of steps is right, too, although I don't thinks it's entirely obvious why that's the number of steps you need to solve the normal form of the game.

Examining the relationship between the number of configurations and the maximum number of steps is one way of approaching part 2).

[Who]

It's not obvious that they're the same until you try to prove that either of them is 2^n-1. Simple induction yields either result.

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

[serrapaladin]

The 4-rod generalisation is a really interesting one, particularly when it comes to finding the shortest path.

The ToH makes a fun combinatorics problem, but this is actually for a slightly more advanced course on graphs, networks, and complexity.

After some of the combinatorics, I'm thinking of questions along the line of:

Spoiler:

- Considering valid configurations as nodes, and valid moves as edges, how would you draw the infinite ToH as a graph? (hint, consider small cases and how to generate the n+1-ToH from the n-ToH)

- What can you say about the properties of this network? (is it scale-free?, is it small-world?)

- How does the diameter of the graph, or the maximum number of moves between two configurations, vary with the number of discs, and hence the number of valid configurations?

- For the (limit as n becomes) infinite-ToH, how does the average number of nodes reachable in r steps vary with r? (hint: consider different ways in which you could calculate the fractal dimension of the graph)?

As a note, it'll have been taught that we can generalise from dimensions of a vector space to graphs by considering the relationship between diameter (a 'distance') and number of nodes (a 'volume'). For the present graph, the configuration-diameter relationship interprets this in a global sense, while the question of average r-neighbourhood sizes addresses it locally.

[implosion]

Inspired by idle thoughts about a speedrun:

You have ten fair coins in front of you, one with each integer value from 1 to 10. You must flip each coin in increasing order of value. If a coin comes up heads, you can go onto the next coin (if coin 10 comes up heads, you're done). If a coin with value i comes up tails, you must pay i dollars, and you have to flip that coin again instead of moving on. You may instead choose to treat the coin as though it had landed on heads. You may only do this once, however, after which point you have no control and must accept every flip.

Your goal is to minimize the expected amount you have to pay. What's the best strategy and how much do you expect to pay using it?

[Who]

Save the treat it as heads for coin 9 or 10. Use it on 9 if 9 is tails, use it on 10 if 9 isn't and 10 is. The expected loss is 41$.

Work:
Expected loss for any given coin with no treat it as heads is i/2+i/4+...=i. Expected loss for any given coin when it just came up tails and deciding whether or not to treat it as heads is 2i (Because you just got tails and then you're back to the beginning). So if you flip tails at 9, expected gain from treating it as heads is 18, expected loss is 10. If you flip tails at 8, expected gain from treating it as heads is 16, expected loss is 19. Your total expected loss is 1+2+...+8=36, plus .5*(Expected loss of coin 10) (If 9 is heads then 10 is automatic heads, if 9 is tails you lose the expected loss of 10)

[implosion]

I believe that's incorrect.