Antichains: Crocodiles and schoolgirls in parliament

Antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable.

I’ve mentioned them a couple of times explicitly or implicitly: in Crocodile Dinner, in Important Theorems From Combinatorics, in the Crossing Lines problem and in its “anime variation”.

Here is another elementary problem that is kind of in between “schoolgirl rivalry” and “crocodiles that swallow each other”.

Consider 435 persons. Assume that every one of them has lied to exactly one other person from this set. (assume they don’t lie to themselves).
Prove that it’s possible to find a subset of at least 145 people so that nobody in that subset has lied to nobody in that subset.

Solution follows after a short break:

A loaded die study

I got a set of handcrafted dice for Xmas. They look like this:

They are wooden, the shapes are obviously imperfect, and the dots are made of metal.

I immediately suspected that they can’t be well balanced and decided to conduct a little study, that turned out to be fun and instructive.

The first experiment I did was dropping the die into water. It appeared that the die is lighter than water and it always floats the 1 side up and the 6 side down:

[Side quest: A perfect cube with the density of exactly 1/2 of the density of water floats in water. Will it float side-up, edge-up or vertex-up? This problem is too tough for me, and I don’t have a solution.]

Anyway, after the float test it was evident to me that the die is biased in the 1- 6 direction. But by how much is this imbalance affecting the outcome of rolling the die on the table?

My next test was the Roll Test. I rolled the die 121 times. Why 121? I wanted a number that is close to 100, close to a multiple of 6 and close to a perfect square. That is because I was pretty sure I’d be able to compute the sigma on a napkin and that would be it. Both 120 and 121 are good numbers. But after I did 120 rolls I thought, why don’t I do one more.

Here are the results of my 121 rolls:

1	2	3	4	5	6
27	19	19	20	21	15

Right, 1 and 6 are obvious outliers… ??? … But they are within the 2-sigma range… But I’m more than confident in my alternative hypothesis! Like a true researcher, I’m going to find a way to confirm it!

So, do I do another 100 rolls? No way, that would be no fun! I’m going to pretend that I’m not dealing with a stupid die, but rather with a particle accelerator, and that I’m over the budget, so this sample is all I have. I’ll do various stats tests on my sample, and I’m going to find one that confirms that this stupid die is loaded!

Sadly, both Chi-square and Kolmogorov-Smirnoff yield p-values about 0.5 that is 10 times greater than what I need in order to reject the hypothesis that the die is fair.

But I’m not giving up. Why was I doing all those tests that attempted to refute the null-hypothesis without having any information about my alternative hypothesis: that the die is biased specifically towards 1 and specifically against 6. And why was I doing all those old-fashioned tests at all? It’s not 19th century and I have a very capable computer at my disposal. I can simulate whatever I want.

Results:

Alternative Hypothesis (out of 121 rolls)	p-value
At least 1 number appears more that 26 times	0.37
At least 1 number appears more that 26 times AND at least 1 number appears less that 16 times	0.3
Exactly 1 number appears more that 26 times AND exactly 1 number appears less that 16 times	0.2
The number ONE appears more that 26 times AND the number SIX appears less that 16 times	0.01

 

So I guess I could now conclude that the die is biased specifically towards 1 and specifically against 6. But should I?

The next step should be checking how significant this bias is for some actual game. I’d need to simulate a game with a realistic bet and see how much money can be won using this die within a realistic timeframe.

I used R for the simulations. Below is the piece of code that does that. Happy New Year!

Red vs. Green

This is from Microsoft Excel 2010.

And I have a confession to make: I can hardly tell Good from Bad… like 1% – 6% of all human males I have a slight defect of color vision. We are not a threat to society: we can tell apart the traffic light signals and other color-based discriminators used in machinery, weaponry etc.

So why don’t UI designers take us into consideration? I’m sure there is a ton of research on creating dichromacy-friendly color palettes.

The RGB values for Good are 198, 239, 206. For Bad: 255, 199, 206. Are you kidding? How can anyone tell these apart? Now let’s increase saturation (+40 in Photoshop):

Now I can clearly see the difference. Good RGB: 200, 255, 130. Bad RGB: 255, 199, 206. See, Bad wasn’t affected by the saturation boost. And Good became… greener and lighter.

… Lately I’m sooo disappointed by what Microsoft is doing in UI/UX. It’s cargo cult… Failed attempts to copy Apple… I’m so glad Steve Sinofsky is no longer there… I wanted to write a huge rant about Windows 8, but I don’t even know where to start.

Happy Holidays!

The measure of massiveness

This year’s Nobel Prize has not been awarded for the discovery of the Higgs. It rather celebrates achievements that will undoubtedly have practical applications. In order to compensate for this unfairness I wanted to dedicate a couple of hours of my time recollecting and reminiscing of some fundamental things that are related to the notion of mass. As I’m not formally trained in physics, this is based on what I learned in school and read in popular literature.

Mass in Intuitive mechanics

• Mass measures the amount of stuff
• Mass is conserved
• Mass is additive
• Mass is a measure of inertia

Mass in Newtonian mechanics

• All of the above
• Mass is invariant in all inertial frames of reference
• Mass is the source of gravity
• F=ma

Note that F=ma is nothing more than:

• Definition of force F = dp/dt
• Definition of acceleration a = dv/dt
• Definition of momentum p = mv
• Conservation of momentum (with no F there is no change of p)

Note that it is easy to guess that gravity is no different from inertia. Acceleration does not depend on the mass? Come on, it’s not a real force! It’s the same kind of force that gives the same acceleration to skinny and fat people on a bus that suddenly breaks.
Also note that it’s easy to predict that massless thing are affected by gravity: once you consider F=ma and F~mM, you see that a doesn’t depend on m. Which Laplace did. Laplace was brilliant, as I mentioned here and here, but this simplistic prediction did not match the observation quantitatively (by the factor of 2).

Relativity

• We need to redefine momentum and energy so that they are still conserved
• Mass is still invariant.
• The rest energy is not zero. The mass is the rest energy.
• The definitions of force and acceleration are still the same, but F is not ma.
• Mass is not a measure of inertia. In fact, there is no invariant measure of inertia. Bodies resist forces depending on how they are moving.
• Mass does not define the gravitational force. In the same manner as inertia, gravity depends on how the bodies are moving – it’s defined by the energy and momentum.
• Mass is not additive. If we have a system of moving or interacting bodies, its mass is not the sum of the masses of the constituents.
• Massless things cannot be at rest, in any frame of reference.
• Mass is not the amount of stuff. It is the amount of motion and interaction – just like energy. But motion is relative… Once again, the mass is the rest energy.

The Higgs

• When it seems that there are no interacting parts, but the massiveness is still there – it is due to interaction with the Higgs field.

Non-numbers

Here is how double.IsNaN() implemented, it’s funny:

/// Returns a value indicating whether the specified 

/// number evaluates to a value that is not a number 
public static bool IsNaN(double d)
{
   return d != d;
}

The double type can get you in trouble because it can store things like NaN and Infinity. It will silently divide by zero, take square roots and logarithms of negatives, and keep calculating, and you will have a hard time finding out where exactly your math is failing. It gets particularly funny when your formulas are right, but because of loss of precision your value under Math.Acos() becomes slightly greater than 1…

Sometimes you’d get a number when you would expect a NaN, e.g.

Math.Pow(0, double.PositiveInfinity) //is zero and not NaN
Math.Pow(1, double.PositiveInfinity) //is one and not NaN

 

And there is no such thing as double.IsNumber(), so if you want to check whether your calculation succeeded you need to check .IsNaN() && .IsInfinity()

So it’s a lot of fun…

Closest neighbors

A simple but curious statement:

In any finite set of points on the plane, there are points that have less than 4 closest neighbors.

Not sure if this is a deep or useful observation.

Not sure if I have a rigorous proof. I’ll publish a sketch of a proof later.

And here is how you prove it:

 

Microsoft promoting anti-patterns

Found this today in production code that I needed to modify:

… = ((TextBox)(row.Cells[1].Controls[0])).Text;
… = ((TextBox)(row.Cells[2].Controls[0])).Text;
… = ((CheckBox)(row.Cells[3].Controls[0])).Checked;

This was in a GridView.RowUpdating handler, and the change that I needed to make was adding a couple of columns to that grid.

Of course, I refactored the code in that page, and, of course, I found that all pages in the project are copy-paste-contaminated by that terrible pattern.

I did some lurking on google for grid view “best practices” and found something that is likely the origin of the infection:

http://msdn.microsoft.com/en-us/library/system.web.ui.webcontrols.gridview.rowupdating.aspx