Big Red Bits

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 and a vector of in-degrees and out-degrees and for , find if there is a simple directed graph on nodes with those in and out-degrees in time . By a simple directed graph, I mean at most one edge between each pair , allowing self loops .

Solving this problem in time is easy using a max-flow computation – simply consider a bipartite graph with and edge between each pair with capacity . Add a source and connect to each node in the left size with capacity and add also a sink in the natural way, compute max-flow and check if it is . But it turns out we can do it in a lot more efficient way. The solution I thought works in time 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 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 where 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 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 to point . If the structure is not rigid, then there is a movement it can make: let and be the instantaneous velocities of points and . If are the movements of points , then it must hold that: , so taking derivatives we have:

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 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 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 no matter what Merlin does, Arthur always manages to turn on all the lamps eventually, where eventually means in time. The solution is a very pretty (and simple) algebraic argument. I found this problem really nice.

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 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 probability and in the other door with probability (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 doors. You choose one and the TV host open 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 bucks. Now, you don’t know if the other envelope has bucks or bucks. Then someone asks you if you wanted to pay 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 bucks, if I change I pay a penalty of and I get either or with equal probability, so my expected prize if I change is , so I should change.
2. I know there is one envelope with and one with , then my expected prize if I don’t change is . If I change, my expected prize is , 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 bucks or it contains 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 probability?

A related problem is: given that you are playing the envelope game and there are number and (with ). 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 ?

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 be a random variable on such that for each we have , for example, the normal distribution or the logistic distribution.

Sample then open the envelope and find a number now, if say the other number is lower and if say the other number is higher. You get it right with probability

which is impressive. If you follow your guess, your expected earning is:

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.

In my last post about hats, I told I’ll soon post another version with some more problems, which I ended up not doing and would talk a bit more about those kind of problems. I ended up not doing, but here are a few nice problems:

Those people are again a room, each with a hat which is either black or white (picked with probability at random) and they can see the color of the other people’s hats but they can’t see their own color. They write in a piece of paper either “BLACK” or “WHITE”. The whole team wins if all of them get their colors right. The whole team loses, if at least one writes the wrong color. Before entering the room and getting the hats, they can strategyze. What is a strategy that makes them win with probability?

If they all choose their colors at random, the probability of winning is very small: . So we should try to correlate them somehow. The solution is again related with error correcting codes. We can think of the hats as a string of bits. How to correct one bit if it is lost? The simple engineering solution is to add a parity check. We append to the string a bit . So, if bit is lost, we know it is . We can use this idea to solve the puzzle above: if hats are places with probability, the parity check will be with probability and with probability . They can decide before hand that everyone will use and with probability they are right and everyone gets his hat color right. Now, let’s extend this problem in some ways:

The same problem, but there are hat colors, they are choosen independently with probability and they win if everyone gets his color right. Find a strategy that wins with probability .

There are again hat colors, they are choosen independently with probability and they win if at least a fraction () of the people guesses the right color. Find a strategy that wins with probability .

Again to the problem where we just have BLACK and WHITE colors, they are chosen with probability and everyone needs to find the right color to win, can you prove that is the best one can do? And what about the two other problems above?

The first two use variations of the parity check idea in the solution. For the second case, given any strategy of the players, for each string they have probability . Therefore the total probability of winning is . Let , i.e., the same input but with the bit flipped. Notice that the answer of player is the same (or at least has the same probabilities) in both and , since he can’t distinguish between and . Therefore, . So,

. This way, no strategy can have more than probability of winning.

Another variation of it:

Suppose now we have two colors BLACK and WHITE and the hats are drawn from one distribution , i.e., we have a probability distribution over and we draw the colors from that distribution. Notice that now the hats are not uncorrelated. How to win again with probability (to win, everyone needs the right answer).

I like a lot those hat problems. A friend of mine just pointed out to me that there is a very nice paper by Bobby Kleinberg generalizing several aspects of hat problems, for example, when players have limited visibility of other players hats.

I began being interested by this sort of problem after reading the Derandomization of Auctions paper. Hat guessing games are not just a good model for error correcting codes, but they are also a good model for truthful auctions. Consider an auction with a set single parameter agents, i.e., an auction where each player gives one bid indicating how much he is willing to pay to win. We have a set of constraints: of all feasible allocations. Based on the bids we choose an allocation and we charge payments to the bidders. An example of a problem like this is the Digital Goods Auction, where .

In this blog post, I discussed the concept of truthful auction. If an auction is randomized, an universal truthful auction is an auction that is truthful even if all the random bits in the mechanism are revealed to the bidders. Consider the Digital Goods Auction. We can characterize universal truthful digital goods auction as bid-independent auctions. A bid-independent auction is given by function , which associated for each a random variable . In that auction, we offer the service to player at price . If we allocate to and charge him . Otherwise, we don’t allocate and we charge nothing.

It is not hard to see that all universal truthful mechanisms are like that: if is the probability that player gets the item bidding let be an uniform random variable on and define . Notice that here , but we are inverting with respect to . It is a simple exercise to prove that.

With this characterization, universal truthful auctions suddenly look very much like hat guessing games: we need to design a function that looks at everyone else’s bid but not on our own and in some sense, “guesses” what we probably have and with that calculated the price we offer. It would be great to be able to design a function that returns . That is unfortunately impossible. But how to approximate nicely? Some papers, like the Derandomization of Auctions and Competitiveness via Consensus use this idea.