# Drawing Blanks

Premature Optimization is a Prerequisite for Success

## 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:

Written by bbzippo

01/27/2013 at 11:47 pm

Posted in fun, math

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!

Written by bbzippo

12/31/2012 at 2:51 am

Posted in fun, math, science

## One point to define them all

A real-valued function f is defined on a set X. There exists an x from X such that IF f(x) = 0 THEN f is a constant 0.

What can we say about f and X in terms of necessary conditions?

Answer: Any function and any set satisfies the above property! And the function doesn’t have to be real-valued too. The statement was designed to confuse the reader.

In any set of cats C there exists a cat c such that IF c is black THEN all cats in C are black.

Written by bbzippo

05/12/2011 at 4:40 am

Posted in fun, math

## The Rule of 72 revised

Wanna double your wealth? Invest it at r% rate and wait for 72/r years.

This is the well-known Rule of 72. Why does it work and what is 72 anyway?

72 because for r =0.08, r*log(2)/log(1+r) = 0.720… And 72 = 2^3*3^2 is a well-divisible number 🙂

And it works for other values of r because x/log(1+x) is almost perfectly linear between 0 and 1: http://www.wolframalpha.com/input/?i=x%2Fln%281%2Bx%29+from+0+to+1

But is r = 0.08 (8% rate) a safe assumption these days? 😉

Short-term treasuries rate is 0.007 today… let’s see 0.007*log(2)/log(1.007) is approximately 0.7 (I love the 3 sevens in this formula), so the revised risk-free rule is the rule of 70:

Wanna double your wealth risk free? Invest it at r% rate and wait for 70/r years.

At the high-risk rate you’ll have to wait for 72/8 = 9 years, and at the low-risk rate: 70/0.7 = 100 years.

And the general rule is: if you want to increase your wealth by the factor f, invest at the rate r and wait for log(f)/log(1+r) years.

Disclaimer: this should not be relied on as investment advice, and I shall not be liable for any direct, indirect, exemplary, compensatory, punitive, special or consequential damages, costs, expenses or losses 🙂 🙂 🙂

Written by bbzippo

01/06/2011 at 3:45 am

Posted in fun, math

## Kinect in infrared

I got Kinect. It’s a lot of fun, although the accuracy of tracking could be better, and the lag is sometimes annoying (I only have the Kinect Adventures game).

I took a few pictures of the infrared pattern projected by the 3D sensor with my Sony F717 camera in the “night shot” mode.

Part of my room illuminated by Kinect. You can see the shape of the “game zone”.

Written by bbzippo

11/28/2010 at 3:33 am

Posted in fun

## Pretty Orbits

I’d like to share some “computer-generated art”. Below are images generated by a program that I wrote in 1997. It was written in Delphi 1 under Windows 3.1 on a 25MHz 386 PC (yes, one with a “turbo” button). The executable still runs just fine (but not much faster than it used to) under Win 7 on a modern PC.

The program is really simple, it just plots a discrete R^2 map (i.e. a sequence of points). The formulas are very simple too. Most of them are based upon the Gingerbreadman map http://en.wikipedia.org/wiki/Gingerbreadman_map (btw, “gingerbreadman” has tons of stupid anagrams)

Written by bbzippo

10/20/2010 at 3:42 am

Posted in fun, math, programming

## Random Shuffle

with one comment

Here is a really funny story

http://techcrunch.com/2010/02/22/microsoft-ballot-screen/

I imagine how that happened:

Dude1: “Dude, how do I randomly shuffle an array?”

Dude2: “Easy: just sort it in a random order.”

Dude1: “Awesome idea! Here I go: array.Sort(randomOrder)”.

Instead of sorting the array in a random order, the dude sorted it using a random comparer. Which resulted in a non-uniform shuffle with distribution that depends on the sorting algorithm.

While this shuffle algorithm http://en.wikipedia.org/wiki/Fisher-Yates_shuffle remains the fastest, simplest and safest, sorting by a random key is not a wrong approach. But if we choose it, we need to be very cautious. We need to make sure the random keys don’t change during sorting, otherwise it may be same as using a random comparer. Check this out:

```var list = Enumerable.Range(1, 10);
Random rand = new Random();
var sorted = list.OrderBy(i => rand.NextDouble()); ```
` `

The code looks suspiciously similar to the wrong implementation. But the parameter of Enumerable.OrderBy() is not a comparer, but rather a key selector. So this code should result in a uniform shuffle (assuming Random.NextDouble() is uniform). But imagine what happens if the OrderedEnumerable enumerator calls the key selector function each time it compares two elements. Then our random key selector becomes equivalent to the random comparer and the result is not uniform. I attempted to figure out how OrderedEnumerable actually works using Reflector, but I gave up. Instead I just ran some tests to check how many times the key selector gets called, and it appeared that it’s called only once for each element. But I would still use the Knuth – Fisher – Yates, of course.

Anagram of the day “uniform shuffle” = “snuff life humor”

Written by bbzippo

02/25/2010 at 6:46 am

Posted in fun, programming