Matchbox Maths Games

There is a great article here on Matches on India. No really read it.

In fact, 97% of rural households purchase matches on a monthly basis. Matches are a unique product because of their high, constant demand and low price point.Their ubiquitous presence provides fascinating insights into India's rural distribution networks, and offer potential ways to inform and interact with India's relatively untouched market.

The article then suggests using the matchboxes to spread public health messages

What if that space was used to relay information? Imagine the possibilities of spreading new health/educational information or advertising to 97% of rural families on a monthly basis. Simple pictorial designs would pique interest and accommodate India's vast differences in literacy rates and languages. Awareness of important topics such as the installation of chimneys to reduce smoke inhalation or cleaning and covering water containers to prevent stomach ailments could be spread to households across India, and potentially save lives

I would recommend selling the glamor of flushing toilets and chimneys and such rather than nagging in your images. But i do not know enough about rural Indians and their diseases to advise on what health images to provide them. There are some interesting studies on what does kill these people here.

However what if all you put on the boxes was games? Many people have a ludic philosophy of life. You see a love of games in maths nerds in particular. This love of games I believe adds a cognitive richness that aids intellectual development.

There is a great book called "everything bad is good for you". That claims the increase in IQ in recent decades is due to increased complexity in our culture. I have not studied the Flynn effect enough to be sure it is not caused by nutrition or even to be sure it is important. But I will assume it is and that intellectual challenges improve general cognitive abilities. I will go further out on a limb and claim that such improvements in cognitive abilities would aid rural Indians. Never having been a rural Indian this really is a big assumption.

So what intellectual challenges could fit on a matchbox and be read by an illiterate farmer? How about puzzles and games?

There are some face meltingly brilliant match puzzles here(pdf). Other then puzzles there are games like NIM, dots and boxes, chomp and loads of others you can play with matches. I would imagine if a brand of matches has a game on it that keeps the kids from bothering you this would be a popular feature.

So can you think of some way to explain a puzzle or the rules of a game on a matchbox without using text? Do you think it really could be useful to put mathematical games and puzzles on matchboxes?

A work sceduling problem

I saw this problem recently

A city authority is considering placing a toll booth on its new bridge. The beginning
times for the shifts are 8am, noon, 4pm, 8pm, midnight and 4am. A collector
beginning a shift at one of the above times works for the next 8 hours.
The following staffing levels during each of the 24-hour periods have been estimated

Hour.................... Minimum Collectors Needed
8am - Noon.............. . 5
Noon – 4pm ................6
4pm – 8pm .................10
8pm - Midnight........... .7
Midnight – 4am ...........4
4am – 8am .................6

Find the minimum number of collectors that need to be hired to begin the 8 hour shifts
at each of the six times.

A GLPK program to calculate this is

var x1 >= 0, integer;
var x2 >= 0, integer;
var x3 >= 0, integer;
var x4 >= 0, integer;
var x5 >= 0, integer;
var x6 >= 0, integer;
/* objective function */
minimize z: x1+x2+x3+x4+x5+x6;

/* Constraints */
s.t. ctr1:x1 + x6 >= 5;
s.t. ctr2:x1+x2>= 6;
s.t. ctr3:x2+x3>= 10;
s.t. ctr4:x3+x4>= 7;
s.t. ctr5:x4+x5>= 4;
s.t. ctr6:x5+x6>= 6;
data;
end;

The answer is 19 and no one starts working at 8am.
This is a simplified version of the program described here. Not a major revelation or anything but always find these puzzle solving programs cool.

Prediction with game theory

I am going to this talk on Thursday so I am reading the book Predictioneer by Bruce Bueno De Mesquita. He has a ted talk video on his prediction ideas.


The use of game theory in forecasting seems based on the axiom that people are rational. The problem is they are not, here is a list of the different ways they are not. If you know how they are going to be irrational you can alter your models to take this into account. However if you fail to do this you will end up with less accurate models.

In chapter 2 the book claims people are rational and particularly that we are transitive in our preferences. "to be rational.. their preferences must not go in circles. For instance if I like chocolate ice cream better then vanilla and vanilla better then strawberry i presumably like chocolate ice cream better than strawberry." So no rock paper scissors can exist in human preferences.

The problem is they do. There is loads of evidence that people can have intransitive preferences. For example May showed in 1952 that people can have intransitive preferences for wealth, looks and intelligence in a partner. So how can you have a mathematical system modeling the world where one of your axioms is false?

While on the subject of intransitive never play dice with Warren Buffet. There are loads of stories of how he tries to con people with a set of intransitive dice. Edward Thorpe for example. Or Bill Gates as described in Bill Gates Speaks: Insight from the World's Greatest Entrepreneur By Janet Lowe

Buffet once attempted to win a game of dice with Bill Gates using intransitive dice. "Buffet suggested each would choose one dice and discard the other two. They would bet on who would roll the highest number most often. Buffet offered to let Gates pick first. This suggestion instantly aroused Gates curiosity. He asked to examine the dice after which he demanded buffet choose first."

Boy in Balloon, did the balloon have enough lift?

I love this story, it reminds me of the time myself and my dad nearly burned down the house. We made a tinfoil hot air balloon with a gas camping cooker to power it. The cooker was tipped onto the lino and the melting began. It was my mums fault for leaving us alone in the house together. In general I love these homemade balloon stories, like Larry Walters across California.

Could we have told in advance it was a haox? "Few had raised the issue of whether such a balloon could even lift off with a 50-pound kid inside, and then float the way it did"

So how big was the balloon? "Authorities said the silver balloon, 20-feet long and 5-feet high, at times reached 7,000 feet above the ground while adrift. It was found more than 90 minutes later in a field near Colorado Springs."


Then it would have a diameter of 6 meters and a height of 1.5m high. Taking the balloon as a cylinder then according to here would give it a volume of 42.5 cubic meters.



Gross Lift (Helium) = Volume (cubic meters)*1.05kg
So 42.5 * 1.05=44.625 kg lift.

Now that seems just within the bounds of possibility as the kid weights about 20 kilos and the balloon itself should be light. But could the balloon have gotten to a height of 2000 meters? There are all sorts of tables for these I might work it out later

Another site gives "Helium provides about 9.8 newtons of lift per cubic meter, at sea level and room temperature. That's enough to lift 1kg". So 20 kilos would require 20 meters squared to lift it. Same result as before.

Thanks to the best program on Television we know how many balloons it takes to lift a small child.
"It would require such a large number of balloons (3,500) to lift an average four-year-old girl of 44 pounds (20 kg) just a few feet off the ground that there is no way the myth could have happened unintentionally."

Update: Wired have an article here about how people should have realised the balloon was empty. Their estimation of the carrying capacity of the balloon is similar to mine. they point out that the balloon does not move like it has a heavy weight hanging from the bottom of it.

NAMA, how much is 54 billion euro?

Nama, the Irish governemts agency to take on bad loans, is paying 54 billion euro to buy property. How much money is that? There is a great visualisation here about how much is a trillion.

So lets picture Croke Park. Its pitch is 144.5 m x 88m. That is much bigger then a soccer or rugby pitch. A 20 euro note is 133 × 72 milimiters. So to pave Croke Park pitch with 20 euro notes requires. So that is 1087 notes long 1223 wide or 1,329,401 notes are needed to pave croke park pitch in 20 euro notes. So that is roughly 2 layers of 20 euro notes being 54 million and paving it two notes deep. A billion is a thousand million so 54 billion is 1000 times this. So 54 billion is paving Croke Park in 20 euro notes 2000 deep.

So if your looking at the game on Sunday imagine there is a 20,000 euro pile of cash on the pitch that you now owe. That is 54 billion divided among the people who pay tax. So you and the person sitting next to you owe a 2000 deep 20 euro sized chunk of the Croke Park pitch.

A comment vaguely asked how much euro coin is this? "Did you know its also enough Euros placed end to end to reach the moon". According to here a 2 euro coin has
Thickness (mm): 2.20
Weight (g): 8.50

So 27 billion 2 euro coins are needed. So in weight that is 229.5 million kilos.
"The maximum gross mass for a 20 ft (6.1 m) dry cargo container is 30,480 kg" so that is 7540 containers full of 2 euro coins.

How long would the stack be? 2.2 * 27 billion millimeters = 59 400 kilometers. Or enough to go around the earth one and a half times. But less than a fifth the distance to the moon.

Ask the waiter

If you want to know what someone is like ask their waiter. Because as a waiter you are far down the social rung anyone who is just a poseur treats you like dirt. Keith Floyd who died yesterday used to come into an Indian restaurant I worked in. He was much quieter then his media image and a complete gent. As was Liam Neeson BTW. I am not claiming to have known him just that he always treated the waiters well, which I believe is a good sign about someone.

Belinda Carlisle owes me a set of cutlery, she may think I have forgotten but I haven't. She promised she would bring them back and didn't. Try saying "if you cannot trust the singer of the Go-Go's, who can you trust?" to a middle aged Bangladeshi and see if your wages don't get docked.

Apart from an unfortunately forgetful singer I have a long list of who is a complete wanker. I'll post that again.

Prediction Market In Adwords?

Can we predict how much an adword word will cost in the future? I find prediction markets fascinating but have not talked about them for a while. Here is an interesting game for predicting the popularity of words.

If this prediction market can accurately predict what words people will in the future find interesting and will discuss then you could buy up these adwords in advance and watch their market value (well cost in google) rise. So anyone want to buy a futures contract in the word "Cromulent"?

Fair division in googledocs using Ruby

I figured out how to access google docs spreadsheets using Ruby's roo library.

So for the spreadsheet
https://spreadsheets.google.co/ccc?key=0AifEYKk1FmScdDUwcTE1c2c4aFF6Wl93cENkWVF1Smc&hl=en
#you can create a object for this document by

        
oo=Google.new("0AoBJp9mMcWUrdDZUY1diRm5KOTd4ZWtKWUpib2V3ZHc"
,user="stuffsplitter",password="thepassword")  

where user and password are the username and its password for the account that has the document. 0AoBJp9mMcWUrdDZUY1diRm5KOTd4ZWtKWUpib2V3ZHc is the key
no http, no google.com, no key= and no &hl=en at the end. Good thing I am not an idiot who would take hours to figure this last one out...

Then this data is sent off to the GLPK program described ad nauseum previously.
Then using ruby's standard regular expression methods the solution file fair.sol can be easily parsed. This can be easily written to the googles doc using roo.

o2.default_sheet ='Sheet3'
#match fair.sol output file of glpk. 
  if line=~/^\s+\d+ y\[(\d+).(\d+)\]\s+\*\s+(\d+)/
#   2 x[1,1]       *              0             0             1
   if $3=='1'
   o2.set_value(row, col, $1)
   o2.set_value(row, col+1, $2)
   o2.set_value(row, col+2, $3) 

Next thing is to get a web interface for people to add their own fair division problems. There are some guides for doing that here and here. So automated processing is the next task.

By the way if you do have a fair division problem you can mail it to stuffsplitter[at]gmail.com and I will run the processing for you.

Fair division using a spreadsheet and Ruby

It has taken me a month to get over the idea that someone expected this blog not to be the ranting of an inane balding drunk but actually good. Still it is time to get back to the drunken inane rambling.

There is no point having all these cool algorithms unless people can actually use them. So what is a good way to actually get the data into the program? We'll spreadsheets are used for this sort of thing all the time. Unfortunately I cannot figure out how to get openoffice, excel or gnumeric's solver to carry out this minimax fair division program.

Ruby has a cool library called roo for interacting with spreadsheets. So heres a program to get the data out of a spreadsheet and send it off to GLPK

  require 'rubygems'
  require 'roo'
  
  #open office version
 # oo = Openoffice.new("spreadsheetOO.ods")
 #  o2 = Openoffice.new("spreadsheetOO.ods")
 
 #excell version
   oo = Excel.new("spreadsheetOO.xls")
   o2 = Excel.new("spreadsheetOO.xls")
  oo.default_sheet = oo.sheets.first

 o2.default_sheet ="Sheet2"
st="" #data being written toa file
div= o2.last_column


#start writing data to model file
st<< "data;\n"
st<< "param m := #{oo.last_row-1};\n"

   st<< "param n := #{div};\n"
 #the non divisible is whatever is left
    st<< "param o := #{oo.last_column};\n"
 
st<< "param c :"
 i=1
 (oo.last_column).times{st<< "#{i} " 
 i=i+1}
 st<< ":=\n"
 
# number of people
  i=1

 2.upto(oo.last_row) do |line|  
 st<< "#{i} "
 1.upto(oo.last_column) do |col|
    st<< "#{Integer oo.cell(line,col)} "#Integer
    
   end
   st<< "\n";
   i=i+1
 end
 st<< ";\n"
  st<< "param d :"
 i=1
 (o2.last_column).times{st<< "#{i} " 
 i=i+1}
  i=1
 st<< ":=\n"
  2.upto(o2.last_row) do |line|  
 st<< "#{i} "
 1.upto(o2.last_column) do |col|
    st<<"#{Integer o2.cell(line,col)} "
 end
   st<< "\n";
   i=i+1
 end
 
 
 st<< ";\nend;"

#write data to a file
File.open("data","w")do |file|
file.write(st)
end

#call glpk program on the data
system('./glpsol -m fair.mod -d data -o fair.sol');

The input spreadsheets are openoffice and excelin the first row is the list of items.
Every other row is each persons valuation for each item. The first sheet is the indivisible items and the second sheet are the divisible ones. Unfortunately roo does not allow you write to these spreadsheets so I cannot print out the answer to a spreadsheet.

The roo interface to the google docs spreadsheet does allow cells to be written to. So getting that version up and running is the next task.

Filling knapsacks with candies

This paper by Marco Dall’Aglio and Raffaele Mosca on using linear programming (and dynamic programming)
it gives two examples of dividing non divisible goods between two people. The paper uses hard candies as a metaphor for any indivisible item.

The valuations are not based out of 100% but just plain numerical values.

candy 1 2 3 4 5 6 7 8 
Alice 12 18 50 40 20 20 10 5 
Bob 5 10 35 30 15 22 30 28 

Which as data for glpk looks like this

data;
param m := 2;
param n := 0;
param o := 8;

param d : :=
1      
2      
;
param c : 1 2 3 4 5 6 7 8 :=
1 12 18 50 40 20 20 10 5
2 5 10 35 30 15 22 30 28
;end;

the worst person got 102 of what they wanted

Person alice gets item number 1 3 and 4
Person bob gets item number 2 5 6 7 8
This is the same allocation as the paper come up with.

The next example given is

candy 1 2 3 4 
Alice 32 28 22 18 
Bob 25 25 25 25

which is the data file

data;
param m := 2;
param n := 0;
param o := 4;

param d : :=
1      
2      
;

param c : 1 2 3 4 :=
1 32 28 22 18
2 25 25 25 25
;end;

Alice gets item 1 and 2
Bob gets item 3,4
The worst performing person gets 50.

To use these data files with the fair divider for two people (the code of which is here)
./glpsol -m fair2.mod -d data -o fair.sol

As pointed out in the comments this isn't earth shaking or anything it just shows another use of fair division which can be used when items cannot be divided.

Fair Division of an estate

This page describes a fair division of an estate between 5 people. The process is described in the "method of Sealed Bids" section. It that requires each participant has money they can use to pay off the others. I think this is a fairly serious drawback as not everyone has loads of money. Also in the case of an estate division it seems slightly galling that the person with more money gets more things, possibly of only sentimental value, then others.

The division works by
"# Step 1. Bidding. Each player produces a sealed bid in which he or she attaches a dollar value to each item in S. A player's fair share is 1/N of his total assessment.

# Step 2. Allocation. Each item in S goes to the highest bidder for that item. If her/his assessed value of the items received exceeds her/his fair share, she/he must pay the difference. If the assessed value of the items received falls short of a fair share, then she/he is paid out of money that others have had to pay.

# Step 3. Dividing the Surplus There is almost always a surplus of cash that is divided equally among the players. "
given results in people getting

Al  BMW, Saab, Miro 
Ben  House  
Cal  Cottage 
Don  Klee
Ed  Yacht

And the minimum receive is $62,500 + $52,100+$18,340=132 940 out of a possible $679,000 or 19% of their desire.

If instead of assuming each player has money to buy stuff off the others I assumed each layer had equal claim to happiness. So I give each persons 100% desire is worth $679000 and those who claimed less then that use the remainder of their allocation as cash.

So this gives a table of desire of this

data;
param m := 5;
param n := 1;
 param o := 7;
 
 /* n divisible items, o non divisible items*/

/*Divorce between Donald and Ivana Trump described in Win-Win solution.
Items to be divided are 
4 divisible items:cash
2 non divisible items: House cottage, bmw,saab,yacht,miro, klee
Item   Al   Ben   Cal   Don   Ed
House  29.46 31.66 28.71 25.77 30.19
Cottage  8.84 7.22 9.2 8.76 8.1
BMW  4.27 3.6 3.68 4.06 4.06
Saab  3.68 2.8 3.33 3.6 2.87
Yacht  17.67 18.4 17.53 19 19.51
Miro  13.99 13.13 7.36 11.05 9.57
Klee  22.09 19.88 14.58 26.36 21.94
cash 0 3.31 15.61 1.4 3.76
*/

param d :  1  2  3  4 5 6 7 :=
      1   29.46 8.84 4.27 3.68 17.67 13.99 22.09
      2   31.66 7.22 3.6 2.8 18.4 13.13 19.88
      3   28.71 9.2 3.68 3.33 17.53 7.36 14.58
      4  25.77 8.76 4.06 3.6 19 11.05 26.36
      5   30.19 8.1 4.06 2.87 19.51 9.57 21.94; 
      
param c :  1 :=
      1   0
      2   3.31
      3   15.61
      4   1.4
      5   3.76; 
      
end;

Running this on the linear programming fair division calculator program(you need to add s.t. wor5{i in I}: ((sum{j in J} c[5,j] * x[5,j])+(sum{k in K} d[5,k] * y[5,k])) >= worst;). gives a the person who gets least 20.5388%

Al BMW Saab Miro 
Ben House 
Cal  0.726381 of the cash  Cottage  
Don Klee
Ed Yacht 0.273619 of the cash

which is an slight improvement of over on the initial allocation. Everyone gets the same items as in the initial allocation but the money is divided amongst those who receive the least rather then everyone.

Fair Division in Treaty Negotiations

Raiffa in "the art and science of negotiation" describes the Panama Canal treaty negotiations in 1974. He got the value each country attached to each issue from the US negotiating team. In the fair division book chapter 5 describes this negotiation using their Adjusted winner algorithm. One weakness with this algorithm is that all items must be divisible.
There is no way to fix issues as non divisible as there is in my program (you will need to remove s.t. wor3 and s.t. wor4).
So if you take the data as

data;
param m := 2;
param n := 9;
param o := 1;
 
 /*m people,  n divisible items, o non divisible items*/
/*
1 non divisible items expansion routes
                  US Panama
US defense rights  22 9
use rights        22 15
Land and water   15 15
expansion rights  14 3
duration         11 15
expansion routes  6 5
compensation     4 11
jurisdiction      2 7
US military rights  2 7
defense role of Panama   2 13
*/

param c :  1  2  3  4 5 6 7 8 9 :=
      1  22 22 15 14 11 4 2 2 2
      2  9 15 15 3 15 11 7 7 13; 
      
param d :  1 :=
      1   6
      2   5; 
end;

where expansion routes is not divisible.

US gets item number us defense rights, use rights, expansion rights,expansion routes
Panama gets duration, expansion routes, compensation, jurisdiction and us military rights. For Land and water the US gets .1333 of this and Panama get 0.86667 which is ok as land and water are the sorts of things that can be divided up. Each country got 66% of what they wanted, In this case my program gets the same results as the Adjusted winner program.

A better fair division program

One problem with the wildly unpopular fair division programs discussed previously is that they assume either everything can be cut into pieces or nothing can.
In the real world as Solomon noticed some items cannot be divided up. But some items are easily splittable . So I have improved the fair division program to deal with combined divisible and indivisible items.

Another problem is that the code only dealt with the two person case. I have fixed this by adding a new constraint for each extra person.

The code for this Mathprog program fair.mod is here. I am providing the source code in case anyone can suggest improvements. Also the world is full of decisions that get made for us that we have no way to challenge or understand. So I would like people to be able to see why the reasoning in and results of an arbitration,

The program (glpk) is run by

Put this data in a data file. Call glpk on it.
./glpsol -m fair.mod -d data -o fair.sol
So the data file could be

data;
param m := 4;
param n := 4;
param o := 2;
/*m people, n divisible items, o non divisible items*/

/*
Items to be divided are
4 divisible items: cash, land, cake, gold
2 non divisible items: dog, table
*/

param c : 1 2 3 4 :=
1 20 30 0 20
2 30 20 0 20
3 20 30 0 20
4 0 10 40 40;

param d : 1 2 :=
1 10 20
2 20 10
3 20 10
4 10 0;
end;

Which means person 1 thinks 20% of the value to them in the estate is in the cash, 10% is in the dog etc.

So now you can divide up goods fairly between m people. I have never seen a program that does this before. Using this program the that parties in a will, divorce, international dispute, merger and all sorts of other areas can achieve optimal solutions. The solutions will be proportional, envy-free (in the two person case) and Pareto optimal.

Now to make the dispute resolution program more usable.

Fair Division of Advertising

Wired today had a really interesting article on how Google uses auctions to sell advertisements here.

it has spawned—dozens of millionaire geeks, billions of auctions, and new ground rules for businesses in a data-driven society.

There is a great paper here(pdf) on the game theory of these online auctions.

But what other mechanisms are there to distribute out advertisements? One way is to use voting which I will describe again. Another method is the algorithmic fair division explained in my last post.

The glpk program given can be used to divide desired ad words between two bidders. You can add more bidders by adding constraints and people. There is an advantage to using this linear programming system of adword selling. It is not designed to maximise earnings but fairness. The procedure guarantees certain criteria described here. One advantage of these criteria is that the least unhappy buyer will be as happy as possible. As Amarillo Slim said "You can shear a sheep many times, but you can skin him only once." If you can keep each party as happy as possible you might maximise revenue over time rather then just for each particular auction. In the given program each party is assumed to have the same resources, 100, a fair division linear program for most applications would give each party a different level of resources.

Dinosaurs are interested in fair division


The book on fair division is this one

So using the previous code but with different data.

/*
Coke and Pepsi want to buy advertisements. They each have 100 dollars to spend.
The adwords they desire are 
1. Refreshing drink 2. Black Fizzy water 
3. cola 4. pop
param c gives how much each company desires an ad on 
each  of these words. Minimax guarantees that
 the company that does worst gets 
the most ads on the topics they want possible.
*/
param c :  1  2  3  4 :=
      1   10 40 10 40
      2   40 20 30 10 ;
end;

Fair Division

"The only way to rectify our reasonings is to make them as tangible as those of the Mathematicians, so that we can find our error at a glance, and when there are disputes among persons, we can simply say: Let us calculate [calculemus], without further ado, to see who is right" Leibniz

If you want to divide items between two people you want to make sure that the person who gets least gets as much as possible.

This Maximin algorithm where you maximise what the person who gets least gets. To do this each person should put a valuation on each item. You can then use linear programming to divide items fairly between people. This program is written for the GLPK(there is a tutorial on it here)

This program is a modified version of this one

param m, integer,:= 2;
/* number of people dividing stuff */

param n, integer, > 0;
/* number of items to be divided */

set I := 1..m;
/* set of people */

set J := 1..n;
/* set of items */

param b{i in I},:= 100; 
/* resource capacity of person i. 
How much each person can want */

param c{i in I, j in J}, >= 0;
/* amount received if item j 
is given to agent i */

var worst;
/*how is the worst person doing?*/

var x{i in I, j in J},>=0;
/*
here ,>=0; 
   means that the items can be subdivided.
here , binary;
  means that items cannot be subdivided 
x[i,j] = 1 means job j is assigned to agent i */

s.t. one{j in J}: sum{i in I} x[i,j] = 1;
/* item j must be assigned. 
An item can be split due to >=0
 being used instead of binary;*/

s.t. lim{i in I}: sum{j in J} c[i,j] * x[i,j] <= b[i];
/* total amount received by all items
 to person i must not exceed the person's capacity */

s.t. wor{i in I}: sum{j in J} c[1,j] * x[1,j] >= worst;
s.t. wor2{i in I}: sum{j in J} c[2,j] * x[2,j] >= worst;
/*constraint on who gets worst deal*/
maximize obj: worst;

data;

param n := 4;
      
/*Divorce between Donald and Ivana Trump 
described in Win-Win solution.
Items to be divided are Conneticut estate, Palm beach mansion,
 Trump plaza apartment, Trump Tower Triplex
param n := 4;
*/
param c :  1  2  3  4 :=
      1   10 40 10 40
      2   40 20 30 10 ;
end;

This last data part param c is important. The first line the columns are the items to be divided. The rows are the valuations placed on them. So c[i,j] is the value person i places on item j.
With splitting items allowed this results in

        No. Column name  St   Activity     
------ ------------ -- ------------- 
     1 worst        B        73.3333                             
     2 x[1,1]       NL             0            
     3 x[2,1]       B              1                          
     4 x[1,2]       B       0.833333                            
     5 x[2,2]       B       0.166667                            
     6 x[1,3]       NL             0            
     7 x[2,3]       B              1                            
     8 x[1,4]       B              1               
     9 x[2,4]       NL             0 

With splitting items not allowed the answer comes out as

  No. Column name       Activity    
------ ------------    ------------- 
     1 worst                      70
     2 x[1,1]       *              0 
     3 x[2,1]       *              1            
     4 x[1,2]       *              1
     5 x[2,2]       *              0
     6 x[1,3]       *              0
     7 x[2,3]       *              1
     8 x[1,4]       *              1 

This algorithm can be used to divide up items in a divorce, resources between countries and loads of other areas.
I will try make this easier for people to use. Any suggestions/comments are welcome.

Blind Rubik's Cube 2

I decided after getting slagged for my incredibly girly last cube to do something a bit less pink. So I went to the craft shop. Where I did not look in anyway out of place amongst all the girls buying glitter and sparkles.

The materials I had to choose from were clockwise from top left
Tire Rubber, paper, foam, felt,velcro hooks, velcro, canvas, ribbon and mesh. I also got black sandpaper later.



I removed the stickers. I then washed off the residual stickiness with glue. I sandpapered 5 of the faces. After some thought I went for foam, velcro hooks, canvas, sandpaper, mesh and clear.

Swine Flu

There has been a worrying outbreak of swine flu. there is a good description of it here. The new scientist has another article on the issue here.

The pandemic ventilator project here says

So what do we know? First the people that are dying are not the typical elderly and very young. They are mainly healthy young and middle aged adults. The death rate seems fairly high, perhaps as great as 10%. Death rates early on in a pandemic however are very difficult to pin down, as we really do not know how many people were infected but in fact had very mild symptoms and were not counted. The virus is spreading to many geographical locations quickly. The WHO has already stated that it’s first line defense against pandemic outbreaks, which is containment, is no longer possible. The reason that there are no major travel restrictions imposed by governments is not that they think the threat is too minor, but that it is past the point where travel restrictions will help. What is still unknown is how severe it will eventually be, and how readily it will spread.

There is not much information in this post. All I am trying to do is point out some sources of useful information on this new flu outbreak.

Blind Rubik's Cube

I saw this and thought a tactile rubik's cube was a good idea.

So I made one. Anyone need a cube they won't look at? Id love to send one to Bernard Morin the blind topologist.

1. Peel off the stickers
2. Get rid of crud left using white spirit
3. Scour the cube and the buttons with a stanley knife
4. Glue buttons onto cube
5. Wait


The result looks a bit like the Borg assimilated hello kitty.

I am going to do up another but this time with different textures instead of shapes. This gets over the symmetry problems. What substances should I use? I want to use felt and thinking of it reminded me of fuzzy felt

I dont want to get all Angela's Ashes here but really was fuzzy felt the best toy ever?

Shannon limit progress

Shannon was the guy who came up with much of the theory of digital computers but is mostly famous for creating information theory. I found out today invented the worlds first wearable computer to cheat at roullette in Vegas here. This is pretty similar to finding out Einstein invented a time machine to grift rubes in three card monte.

He also developed a motorised pogo-stick and flame throwing trumpet. A picture of Shannon using these or even just juggling on his unicycle would finally prove the internet was useful.

So how has attempts to get a code that approaches the Shannon limit progressed? "The Shannon limit or Shannon capacity of a communications channel is the theoretical maximum information transfer rate of the channel, for a particular noise level."

It is really important because it controls how much information a device can transmit. Which is important if you make phone calls or communicate with a satellite.
So in 1948 Shannon put a limit on how much information can be transferred. Mathematicians (and engineers) devise ways to encode information to make communications close to this limit. As maths progresses you would expect the codes to get closer to this limit.

I have taken this first picture from this very good article. You can see how codes improve over time


In this picture you can see new codes moving closer to 0 on the y-axis showing improvements in the coding schemes. I'm having trouble getting the world record closeness to the Shannon limit for particular dates. When I do I'll add them.
What I have so far is
Year Power Who
1977 2.1 dB Reed–Solomon code(now 1–1.5db)
1997 .27 db hamming code
2009 0.0045 dB LDPC codes

Sometimes codes have been invented before they were practical, but even then people tend not to have known how good they were.
"LDPC codes were invented by Robert Gallager in 1962! However, LDPC codes were largely forgotten until their rediscovery by David Mackay in 1998, who not only rediscovered them but used powerful modern computers (which were not available to
Gallager) to simulate their performance and thereby demonstrate their astonishing power"

The importance of this progress has been summed up by suggesting future historians will write
"Claude Shannon formulated the notion of channel capacity in 1948 A.D. Within several decades, mathematicians and engineers had devised practical ways to communicate reliably at data rates within 1 percent of the Shannon limit...."
Coding theory is one where we can see practical applied progress in mathematics over the last 60 years.

Rubik's Progress

How quickly is maths improving? Say you look at how good your best solution to certain problems is over time. You can estimate how much improvement there is in maths over this time. Most of maths is based around proofs which are pretty hard to measure the quality of. But by looking at applied results you might get evidence to how much the pure maths knowledge has improved also.
So take the example of optimal algorithms for Rubik's cubes (most of this data taken from here).

Start 1974 until now how many face turns are needed to solve the Rubik's cube in the worst case?

52 moves 1981 using Thistlethwaite's Algorithm
42 moves 1990 Kloosterman (doc)
39 moves Mike Reid (i'm trying to get a date for this)
29 moves 1995."In 1995 Michael Reid proved that using these two groups every position can be solved in at most 29 face turns"
27 moves 2006, Silviu Radu
26 moves August 2007, Daniel Kunkle and Gene Cooperman
25 Moves Mar 2008 Tomas Rokicki
23 moves Jun 2008 Tomas Rokicki
22 moves August 2008 Tomas Rokicki

This implies 20 moves are enough using the given algorithm but it has not been proved

Now the best possible solution is at least 20 moves (known as gods algorithm). This number used to be 18 but was improved in 1995 by Michael Reid. The bounds on solutions to the Rubik's cube is improving from two sides. The ability to solve a Rubiks cube going from 52 to 22 moves does not seem earth shattering. There are probably more important maths calculations that have improved over time though. Can you think of any? As usual if you have any more information or corrections I will add them.