Archive

Archive for the ‘puzzles’ Category

Three interesting puzzles

Here are three puzzles I got from 3 different people recently. The first I got from Charles, who got it from a problem set of the Brazilian Programming Competition.

Puzzle #1: Given $n$ and a vector of in-degrees and out-degrees $\text{in}_i$ and $\text{out}_i$ for $i=1..n$, find if there is a simple directed graph on $n$ nodes with those in and out-degrees in time $O(n \log n)$. By a simple directed graph, I mean at most one edge between each pair $(i,j)$, allowing self loops $(i,i)$.

Solving this problem in time $O(n^3)$ is easy using a max-flow computation – simply consider a bipartite graph with and edge $(i,j)$ between each pair with capacity $1$. Add a source and connect to each node in the left size with capacity $\text{in}_i$ and add also a sink in the natural way, compute max-flow and check if it is $\sum_i \text{in}_i$. But it turns out we can do it in a lot more efficient way. The solution I thought works in time $O(n \log n)$ but maybe there is a linear solution out there. If you know of one, I am curious.

The second puzzle was given to me by Hyung-Chan An:

Puzzle #2: There is grid of size $n \times m$ formed by rigid bars. Some cells of the grid have a rigid bar in the diagonal, making that whole square rigid. The question is to decide, given a grid and the location of the diagonal bars if the entire structure is rigid or not. By rigid I mean, being able to be deformed.

We thought right away in a linear algebraic formulation: look at each node and create a variable for each of the 4 angles around it. Now, write linear equations saying that some variables sum to 360, since they are around one node. Equations saying that some variable must be 90 (because it is in a rigid cell). Now, for the variables internal to each square, write that opposite angles must be equal (since all the edges are of equal length) and then you have a linear system of type $Ax = b$ where $x$ are the variables (angles). Now, we need to check if this system admits more then one solution. We know a trivial solution to it, which is all variable is 90. So, we just need to check if the matrix $A$ has full rank.

It turns out this problem has a much more beautiful and elegant solution and it is totally combinatorial – it is based on verifying that a certain bipartite graph is connected. You can read more about this solution in Bracing rectangular frameworks. I by (Bolker and Crapo 1979). A cute idea is to use the the following more general linear system (which works for rigidity in any number of dimensions). Consider a rigid bar from point $p_a \in \mathbb{R}^n$ to point $p_b \in \mathbb{R}^n$. If the structure is not rigid, then there is a movement it can make: let $v_a$ and $v_b$ be the instantaneous velocities of points $a$ and $b$. If $p_a(t), p_b(t)$ are the movements of points $a,b$, then it must hold that: $\Vert p_a(t) - p_b(t) \Vert = \Vert p_a(0) - p_b(0) \Vert$, so taking derivatives we have:

$(p_a(0) - p_b(0)) \cdot (v_a - v_b) = 0$

This is a linear system in the velocities. Now, our job is to check if there are non zero velocities, which again is to check that the matrix of the linear system is or is not full-rank.  An interesting thing is that if we look at this question for the grid above, this matrix will be the matrix of a combinatorial problem! So we can simply check if it has full rank by solving the combinatorial problem. Look at the paper for more details.

The third puzzle I found in the amazing website called The Puzzle Toad, which is CMU’s puzzle website:

Puzzle #3: There is a game played between Arthur and Merlin. There is a table with $n$ lamps disposed in a circle, initially some are on and some are off. In each timestep, Arthur writes down the position of the lamps that are off. Then Merlin (in an adversarial way) rotates the table. The Arthur’s servant goes and flips (on –> off, off –> on) the lamps whose position Arthur wrote down (notice now he won’t be flipping the correct lamps, since Merlin rotated the table. if Arthur wrote lamp 1 and Merlin rotated the table by 3 positions, the servant will actually be flipping lamp 4. The question is: given $n$ and an initial position of the table, is there a strategy for Merlin  such that Arthur never manages to turn all the lamps on.

See here for a better description and a link to the solution. For $n = 2^k$ no matter what Merlin does, Arthur always manages to turn on all the lamps eventually, where eventually means in $O(n^2)$ time. The solution is a very pretty (and simple) algebraic argument. I found this problem really nice.

Categories: Tags:

Do we believe the Axiom of Choice ?

Continuing on my series of posts from Israel, I’d like to share some exciting puzzle that I heard today from Omer Tamuz. I’ve learned before about the Axiom of Choice in a Measure Theory class, but never saw a so striking and counter-intuitive application of it. Ok, you might say the Banach–Tarski paradox is a pehaps better example – but since it’s proof is so complicated, it is not as striking as seeing how a simple application of it can generate un-intuitive results. First, let me present two puzzles:

Puzzle #0: There are $n+1$ people in a line, and each has a $0/1$ number on his hat. Each player can look to the numbers of the players in front of him. So, if $x_i$ is the number of player $i$, then player $i$ knows $x_{i+1},\hdots,x_n$. Now, from $i = 0 \hdots n$ the players will say his own number. Is there a protocol such that players $1,\hdots,n$ will get their own number right? (Notice that they hear what the players before him said).

Puzzle #1: Consider the same puzzle with an infinite number of players. I.e. there are $x_i; i \in \mathbb{Z}_+$ and player $i$ knows $x_j$ for all $j > i$. Show a protocol for all players, except the first to get the answer right?

Puzzle #2: Still the same setting, but now players don’t hear what the previous player said. Is there a protocol such that only a finite number of players get it wrong ? (notice that it needs to be finite, not bounded).

Puzzle #0 is very easy and the answer is simply parity check. Player $0$ could  simply declares $y = x_1 \otimes\hdots \otimes x_n$ where $\otimes$ stands for XOR. Now, player $1$ can for example reconstruct $x_1$ by $y \otimes x_2 \otimes \hdots \otimes x_n$. Now, player $2$ can do the same computation and figure out $x_1$. Now, he can calculate $x_2 = y \otimes x_1 \otimes x_2 \otimes \hdots \otimes x_n$ and so on… When we move to an infinite number of players, however, we can’t do that anymore because taking the XOR of an infinite number of bits is not well defined. However, we can still can solve Puzzles #1 and #2 if we believe and are willing to accept the Axiom of Choice.

Axiom of Choice: Given a family of sets $\{ S_i \}_{i \in I}$ there is a set $\{x_i; i \in I\}$ such that $x_i \in S_i$, i.e. a set that takes a representative from each element in the family.

It is used, for example to show that there is no measure $\mu : 2^{[0,1)} \rightarrow \mathbb{R}$ that is shift invariant (say under addition modulo $1$) and $\mu([0,1)) = 1$. The proof goes the following way: define the following equivalence relation on $[0,1)$: $x \sim y$ if $x - y \in \mathbb{Q}$. Now, consider the family of all the equivalence classes and invoke the Axiom of Choice. Let $K$ be the set obtained. Now, we can write the interval as a disjoint union:

$[0,1) = \cup_{x \in \mathbb{Q}} (K+x)$

where all operations are modulo $1$ and $K+x = \{y+x; y \in K\}$. Since it is an enumerable union, if such a measure existed, then: $\mu([0,1)) = \sum_{x \in \mathbb{Q}} \mu(K+x) = \sum_{x \in \mathbb{Q}} \mu(K)$ which is either $0$ if $\mu(K) = 0$ or $\infty$ if $\mu(K) >0$.

This is kinda surprising, but more surprising is how we can use the exact same technique to solve the puzzles: first, let’s solve Puzzle #2: let $S$ be the set of all infinite $\{0,1\}$-strings and consider the equivalence relation on $S$ such that $x \sim y$ if the strings differ in a finite number of positions. Now, invoke the axiom of choice in the equivalence classes and let $S_0$ be the set of representatives. Now, if $F$ is the set of all strings with finite number of $1$‘s and $\otimes$ the operation such that $z = x \otimes z$ if $z_i = x_i \otimes y_i$. We can therefore write:

$S = \cup_{x \in F} (S_o \otimes x)$

Now, a protocol the players could use is to look ahead and since they are seeing an infinite number of bits, they can figure out which equivalence class from $S/\sim$ they the entire string is. Now, they take $y \in S_0$ the representative of this class and guess $y_i$. Notice that $y$ will differ from the real string by at most a finite number of bits.

Now, to solve puzzle #1, the player $0$ simply looks at $x = x_1 x_2 \hdots$ and figure out the equivalence class he is and let $y \in S_0$ be the representative of this class. Now, since $x$ and $y$ differ by a finite number of bits, he can simply calculate XOR of $x$ and $y$ (now, since it is a finite number of them, XOR is well defined) and announce it. With this trick, it just becomes like Puzzle #0.

Categories: Tags:

Probability Puzzles

Today in a dinner with Thanh, Hu and Joel I heard about a paradox I haven’t heard so far. Probability is full of cute problems that challenge our understanding of the basic concepts. The most famous of them is the Monty Hall Problem, which asks:

You are on a TV game show and there are ${3}$ doors – one of them contains a prize, say a car and the other two door contain things you don’t care about, say goats. You choose a door. Then the TV host, who knows where the prize is, opens one door you haven’t chosen and that he knows has a goat. Then he asks if you want to stick to the door you have chosen or if you want to change to the other door. What should you do?

Probably you’ve already came across this question in some moment of your life and the answer is that changing doors would double your probability of getting the price. There are several ways of convincing your intuitions:

• Do the math: when you chose the door, there were three options so the prize is in the door you chose with ${\frac{1}{3}}$ probability and in the other door with probability ${\frac{2}{3}}$ (note that the presenter can always open some door with a goat, so conditioning on that event doesn’t give you any new information).
• Do the actual experiment (computationally) as done here. One can always ask a friend to help, get some goats and perform the actual experiment.
• To convince yourself that “it doesn’t matter” is not correct, think ${100}$ doors. You choose one and the TV host open ${98}$ of them and asks if you want to change or stick with your first choice. Wouldn’t you change?

I’ve seen TV shows where this happened and I acknowledge that other things may be involved: there might be behavioral and psychologic issues associated with the Monty Hall problem – and possibly those would interest Dan Ariely, whose book I began reading today – and looks quite fun. But the problem they told me about today in dinner was another: the envelope problem:

There are two envelopes and you are told that in one of them there is twice the amount that there is in the other. You choose one of the envelopes at random and open it: it contains ${100}$ bucks. Now, you don’t know if the other envelope has ${50}$ bucks or ${200}$ bucks. Then someone asks you if you wanted to pay ${10}$ bucks and change to the other envelope. Should you change?

Now, consider two different solutions to this problem: the first is fallacious and the second is correct:

1. If I don’t change, I get ${100}$ bucks, if I change I pay a penalty of ${10}$ and I get either ${50}$ or ${200}$ with equal probability, so my expected prize if I change is ${\frac{200+50}{2}-10 = 115 > 100}$, so I should change.
2. I know there is one envelope with ${x}$ and one with ${2x}$, then my expected prize if I don’t change is ${\frac{x + 2x}{2} = \frac{3}{2}x}$. If I change, my expected prize is ${\frac{x + 2x}{2} - 10 < \frac{3}{2}x}$, so I should not change.

The fallacy in the first argument is perceiving a probability distribution where there is no one. Either the other envelope contains ${50}$ bucks or it contains ${200}$ bucks – we just don’t know, but there is no probability distribution there – it is a deterministic choice by the game designer. Most of those paradoxes are a result of either an ill-defined probability space, as Bertrand’s Paradox or a wrong comprehension of the probability space, as in Monty Hall or in several paradoxes exploring the same idea as: Three Prisioners, Sleeping Beauty, Boy or Girl Paradox, …

There was very recently a thrilling discussion about a variant on the envelope paradox in the xkcd blag – which is the blog accompaning that amazing webcomic. There was a recent blog post with a very intriguing problem. A better idea is to go there and read the discussion, but if you are not doing so, let me summarize it here. The problem is:

There are two envelopes containing each of them a distinct real number. You pick one envelope at random, open it and see the number, then you are asked to guess if the number in the other envelope is larger or smaller then the previous one. Can you guess correctly with more than ${\frac{1}{2}}$ probability?

A related problem is: given that you are playing the envelope game and there are number ${A}$ and ${B}$ (with ${A < B}$). You pick one envelope at random and then you are able to look at the content of the first envelope you open and then decide to switch or not. Is there a strategy that gives you expected earnings greater than ${\frac{A+B}{2}}$ ?

The very unexpected answers is yes !!! The strategy that Randall presents in the blog and there is a link to the source here is: let ${X}$ be a random variable on ${{\mathbb R}}$ such that for each ${a we have ${P(a < X < b) > 0}$, for example, the normal distribution or the logistic distribution.

Sample ${X}$ then open the envelope and find a number ${S}$ now, if ${X < S}$ say the other number is lower and if ${X > S}$ say the other number is higher. You get it right with probability

$\displaystyle P(\text{picked }A) P(X > A) + P(\text{picked }B) P(X < B) = \frac{1}{2} (1 + P(A < X < B))$

which is impressive. If you follow your guess, your expected earning ${Y}$ is:

\displaystyle \begin{aligned} &P(\text{picked }A) \mathop{\mathbb E}[Y \vert \text{picked }A] + P(\text{picked }B) \mathop{\mathbb E}[Y \vert \text{picked }B] = \\ & = \frac{1}{2} [P(XA) B] + \frac{1}{2} [P(XB) A] \\ &= \frac{1}{2}[A [P(XB)] + B [P(X>A) + P(X \frac{A+B}{2} \\ \end{aligned}

The xkcd pointed to this cool archive of puzzles and riddles. I was also told that the xkcd puzzle forum is also a source of excellent puzzles, as this:

You are the most eligible bachelor in the kingdom, and as such the King has invited you to his castle so that you may choose one of his three daughters to marry. The eldest princess is honest and always tells the truth. The youngest princess is dishonest and always lies. The middle princess is mischievous and tells the truth sometimes and lies the rest of the time. As you will be forever married to one of the princesses, you want to marry the eldest (truth-teller) or the youngest (liar) because at least you know where you stand with them. The problem is that you cannot tell which sister is which just by their appearance, and the King will only grant you ONE yes or no question which you may only address to ONE of the sisters. What yes or no question can you ask which will ensure you do not marry the middle sister?

copied from here.

Categories: puzzles Tags: