Secret Santa 3: The Paradox.

Last time I discussed the solution to Sam’s problem:

Sam’s Problem. Is it possible for two people to each choose a natural number so that both numbers are exactly 1 apart and neither person knows who has the larger of the two numbers?

I established, by induction, that it is impossible to do this. Great. We write “QED” and move on. There is a very convincing counter-argument that was brought to my attention by Jacob Tsimerman and a student at the Winter Canadian IMO camp. They proposed a method that seems like it should solve Sam’s problem in the positive. What exactly is going on in their method? Where is the mistake?

Jacob’s method. Player 1 chooses a large enough number N (say greater than 100); this is now their number. Player 1 writes down the numbers N+1 and N-1 on different pieces of paper and presents them face-down to Player 2. Player 2 chooses one of them and burns the other one without looking at it. The number Player 2 sees is their number.

Continue reading Secret Santa 3: The Paradox.

The Secret Santa Problem (Part 2)

Last time, just in time for Christmas, we looked at the Secret Santa Problem. Basically the problem is to set up a secret santa type gift exchange without using any external aids like random number generators. A similar problem given to me by Sam Coskey is the following:

Sam’s Problem. Is it possible for two people to each choose a natural number so that both numbers are exactly 1 apart and neither person knows who has the larger of the two numbers?

When Sam gave the problem to me he intended that each player would choose a natural number and then they would sequentially ask questions to each other, possibly refining their original numbers. In this sense it is more like a game of Guess Who than secret santa.

After much thinking, it turns out that there is a fairly easy solution to this problem.

Part 1. Can either player choose the number 0?

Well no, because that person would know that they have a smaller number than the other player.

Part 2. If both players know that 1, 2, \dots, k cannot be chosen then k+1 cannot be chosen (as k+1 would have to be the smaller of the two numbers). So by induction, no number can be chosen by either player.

The lesson here is that induction is a very useful technique! This sounds naive but, when problem solving for contests, induction is often overlooked. Here is another related problem:

Father/Son problem. Is it possible for two players to each choose a human being so that the two humans are father and son, but neither player knows who has the father and who has the son?

The solution is again fairly simple, and uses induction. This time we need a different type of induction. We observe that no player can pick the first ever human being (as they would have the father of the other player’s choice). Now if there is a set S of humans that cannot be chosen, then the sons of people in S cannot be chosen either.

There you go, induction wins again!

 

The Secret Santa Problem

Happy holidays everyone! As Christmas approaches so do the Christmas related problems. I’m not talking about the long lines at stores or the busy days filled with errands, I’m talking about Christmas math problems. Here is one I learned at my department holiday party from Eric Hart and Jeremy Voltz.

This whole post is going to be directed at a general audience.

Secret Santa Problem (simplified). An office needs to determine how to set up a secret santa gift exchange, but they have lost all of their dice and paper! How can each person in the office have exactly one person for whom they are buying a gift and also each person does not know who is buying them a gift?

Here we allow some of the employees to have private conversations if they wish.

Attempt 1: The obvious first thing to do (that doesn’t work) is to have one person tell everyone whose gift they are buying. You can tell right away why this won’t work: It is too much work for that one person the designator will have to designate someone to buy a gift for the designator!

Attempt 1.a: Have the boss tell everyone what they should do. Well… I don’t think the boss is going to like this idea. We should really try to find an internal solution. That is, let’s try to find a solution that does not use anything external (like random number generators, extra people, secret santa consultants, etc.)

Continue reading The Secret Santa Problem

Reading the Dictionary

I have a confession to make: I am a bibliophile. Reading, owning, perusing, lending, alphabetizing and buying books are all things that make me happy. High on my list are hardcover graphic novels and quality dictionaries. One of the skills you learn quickly while reading a dictionary (so I hear) is how to look up words. Of course the words in a dictionary are laid out in a very orderly fashion; first the ‘A’s then the ‘B’s, etc.. This order turns out to be a useful example of an interesting linear order.

Example: Consider \{a,b,c\}\times\{a,b\} with the dictionary ordering. We get aa < ab < ba < bb < ca < cb .

In general to get a dictionary ordering on A\times B out of two linear orders A,B we do the following:

  1. Compare first elements. If they are the different, use the ordering on A.
  2. If the first coordinates are different, compare the second coordinates. If the second coordinates are different, use the ordering on B . If the second coordinates are the same, the elements you are comparing are the same (as they have the same first and second coordinates).

You can extend this process if you want and compare third, fourth or fifth coordinates if you start with three, four or five linear orders. Of course this is just saying something you already know; I don’t need to tell you how to figure out whether ‘oscillate’ comes before ‘ossifrage‘.

Example: Now my fellow sesquipedalians might be interested in the following linear order: Let D = \{*, a,b,c, \ldots, z\} where * < a < b < \ldots < z and * stands for a blank space. Now consider D^{189819} with the dictionary ordering. This will contain every English word both technical and non-technical. Granted it will also contain silly non-words like: “this*word*asserts*that*it*is*a*silly*word”.

Continue reading Reading the Dictionary

Every Day I’m Simulating

You can simulate buying this shirt!

 

Have you ever tried to explain/inflict forcing on your non-set theory friends? Let me tell you it is hard. In my ongoing effort to try to explain everything to everyone here is my attempt at explaining the idea of forcing, without explaining forcing.

First, I direct you to this post which explains the simulation argument.

tl; dr – Imagine that our civilization could simulate (artificially) intelligent civilizations. They wouldn’t know that they are in a simulation and could also run their own simulations.

Reading this post reminded me about forcing. Here is my reply to the OP (who happens to be my brother-in-law), and I would appreciate feedback on this so that I can refine my analogy:

Cool. This illustrates a key observation that underlies a lot of the mathematics (set theory) that I do. It goes like this for the interested parties:

We run a simulation as you’ve described, but we make sure that the simulation only has “a small number of things in it”. Perhaps we have some sort of minimal simulation, like we don’t include the letter Z in their languages or something (Call this SIM1). Now we check that the simulation can come up with its own simulations. It can? Great! So now we know that “having the letter Z in your language” is not a requirement for coming up with simulations. Or we could add a whole bunch of new crazy letters (in say SIM2) and see if they can still run simulations. Lets say they can still come up with simulations. Continue reading Every Day I’m Simulating

Creeping Along

In my ongoing love affair with compactness I am constantly revisiting a particular proof of the Heine-Borel theorem, a characterization of compactness in \mathbb{R} . There are two proofs that I know of: the standard “subdivision” proof and the “creeping along” proof. I am going to focus on the creeping along proof.

Heine-Borel Theorem. A subset A \subseteq \mathbb{R} is compact if and only if it is closed and bounded.

To do some creeping we need to collect some useful facts.

Fact 1. A subset \mathcal{A} \subseteq \mathbb{R} is bounded if and only if is contained in some closed interval [a,b]

Fact 2. The set \mathbb{R} is complete (as a linear order) because every non-empty set A \subseteq \mathbb{R} with an upper bound has a least upper bound, called \sup A .

Fact 3. Closed subsets of compact subsets of \mathbb{R} are in fact themselves compact. With fact 1 this means that it is enough to show that closed and bounded intervals in \mathbb{R} are compact. (In general closed subsets of compact T_2 spaces are compact.)

So now let us creep:

Continue reading Creeping Along

Helly’s Theorem (2/2)

Last week we looked at the concepts of a collection of sets being n-linked or having the finite intersection property. The key theorem was Helly’s theorem which says:

Helly’s Theorem: If a (countable) family of closed convex sets (at least one of which is bounded) in the plane are 3-linked, then they have a point in common, as they have the FIP.

Now I will look at some of the generalizations that Alexander Soifer, author of “The Mathematical Coloring Book”, makes in Chapter 28 of that book. More than pure generalizations they are the combination of Ramsey theory and Helly’s Theorem

Continue reading Helly’s Theorem (2/2)