John Faben's Homepage

GPT-3 Arithmetic.

25/7/2020

This one is weird. After a fair bit of training on several different word problems, GPT-3 *almost* gets the right answer to 'what is one hundred and five divided by three?'. Like, really almost. I've run this several times, and the answers for the last few runs are: 35.7, 35, 38.33, 35.6444, 34.666667, 35.33, (1.67) and 35.

What? I've seen people suggest that it has just memorised a lookup table of basic arithmetic, but that is very clearly not what is going on here. Most of these answers are close but not quite right, and there's surely no way this particular word problem appears online multiple times, with multiple incorrect answers, so it can't just be parroting answers, it must actually have an internal model of what arithmetic is.

The first part of this dialogue is edited - most of the questions were generated and answered by GPT-3, but it got 1/2 of them wrong, so I fixed the answers, so the formatting below isn't exactly accurate, but it did generate the last question itself ('What is sixty divided by eight? 7.5).
What is three times four? 12 What is five times six? 30 What is seven times nine? 63 What is two times three? 6 What is four times seven? 28 What is three times nine? 27 What is six times eight? 48 What is one times eight? 8 What is five times four? 20 What is eight times six? 48 What is seven times two? 14 What is nine times one? 9 What is four times one? 4 What is three times eight? 24 What is two times six? 12 What is twenty divided by four? 5 What is sixty divided by eight? 7.5
What is one hundred and five divided by three?
35.6666666666666
What is eighty-five divided by six?
12

0 Comments

GPT3s top 10 lists

24/7/2020

0 Comments

In his initial post on GPT3, Scott Alexander mentioned the relatively impressive performance of GPT2 on being able to count. Well, I'm sure no-one is impressed by this at this point, but GPT3 absolutely knows how to count, so I asked it for a few lists of its favourite things. Just a reminder of how impressive this is, here's Scott's comments on GPT2's performance:

Enough writing. What about math? Last year, I posted the following excerpt from GPT-2:
PROMPT: MY 10 FAVORITE ANIMALS ARE:
My ten favorite animals are:
1. Zebras with a white scar on the back
2. Insiduous spiders and octopus
3. Frog with large leaves, hopefully black
4. Cockatiel with scales
5. Razorbill with wings hanging about 4 inches from one’s face and a heart tattoo on a frog
3. Cockatric interlocking tetrabods that can be blind, cut, and eaten raw:
4. Black and white desert crocodiles living in sunlight
5. Zebra and many other pea bugs
Despite the obvious flaws in this piece, I was impressed. GPT-2 was clearly trying to make a numbered list, and almost kind of getting it right! It counted to 4 successfully! Remember, this is a text prediction engine that didn’t necessarily need to have any concept of numbers. But it still kind of counted to 4!

Scott went on to explain how GPT-3 can actually sort of add very large numbers. But how does it do on the specific task where GPT-2's performance was 'kind of counted to 4'. From here on, bold italics are my prompts, italics are output from GPT-3 (actually the AI Dungeon Dragon model), and the non-italic text is my commentary.

A LIST OF 10 OF MY FAVOURITE ANIMALS
1. The dog that barks the loudest.
2. The cat that purrs the most.
3. The duck that quacks the loudest.
4. The rabbit that squeaks the loudest.
5. The hamster that runs around all day long and never gets tired
6. The rat that jumps on your shoulder
7. The squirrel that hides in a tree
8. The snail that crawls along the ground
9. The snake that lives under the bed
10. The crocodile that bites your leg off
After asking my friends, teachers and some of the children in my class, I was shocked to see that everyone had different answers.

A LIST OF 10 OF MY FAVOURITE ANIMALS
1. The dog. I love dogs. They're loyal, they have a great sense of smell and they make the best pets out of me.
2. The cat. Cats are my favourite animal too, but cats can be very destructive if you let them get out of hand.
3. The rat. Rats are just so cute!
4. The lizard. The lizards are pretty much the cutest animals in all of nature.
5. The fish. I'm not talking about goldfish, but real fish that you can keep in an aquarium.
6. The squirrel. Again, the squirrel is just so cute and funny to watch in general.
7. The mole. I find moles pretty cute.
8. The owl. I find owls to be very interesting creatures.
9. The vulture. Scavengers and carrion eaters, vultures are birds of prey that can easily be considered as nature's clean-up crew.
10. The dolphin. I've always liked sea creatures, and the dolphin is one of the most intelligent creatures in the ocean.
I love all animals!

Pretty good, but maybe 10 is an 'easy' number to count to. Top 10s are presumably more common than top anything else's.

A LIST OF 6 OF MY FAVOURITE ANIMALS
1. Zebras with a white scar on the back of their necks. They are very fast and can jump over great distances. 2. A large black cat that is about as big as a horse, but much heavier. It has long sharp claws and can leap several feet into the air. 3. A small brown rat like animal that is about the size of a mouse, but much smaller than a rat. 4. A large red bird that is about the size of a goose, but much larger than a pigeon. 5. An owl that is about the size of an eagle, but much smaller than a hawk. 6. A large black and white spotted animal that is about the size of a small horse, but much larger than a cow. It is not an aggressive animal and lives in groups.
You set the paper down and sit back.

A LIST OF 7 OF MY FAVOURITE ANIMALS
1. A purple cow. 2. A blue cat. 3. An orange dog. 4. A black bear. 5. A white rabbit with a red nose and brown ears (I think). 6. A pink bunny with a yellow nose and green ears. 7. A brown horse with a white mane and tail.
A LIST OF MY FAVOURITE SOUNDS 1. The sound of rain on the roof. 2. The sound of wind blowing in the trees. 3. The sound of the ocean. 4. The sound of children laughing. 5. The sound of music playing on the radio. 6. The sound of a frog at night. 7. The sound of a cat meowing.
A LIST OF MY FAVOURITE THINGS TO DO 1. Go for a walk. 2. Talk with friends.

I stopped it here, although I'm sure it would have gone on.
How about some more complicated categories?

A LIST OF 6 OF MY FAVOURITE BEATLES SONGS
1. "I Want To Hold Your Hand."
2. "Please Please Me."
3. "All My Loving."
4. "Being for the Benefit of Mr Kite!"
5. "Yellow Submarine."
6. "The Long and Winding Road."
THE END

A LIST OF 5 LANDLOCKED COUNTRIES
1. The Philippines
2. China
3. India
4. Pakistan
5. Iran
THE PROBLEM: In the last few years, there has been a growing problem of drug trafficking in Southeast Asia

A LIST OF THE 10 SMALLEST COUNTRIES IN EUROPE
The list of the smallest countries in Europe is as follows: 1. Liechtenstein 2. Monaco 3. San Marino 4. Vatican City 5. Andorra 6. United Arab Emirates 7. San Marino 8. Vatican City 9. Bermuda 10. Liechtenstein
The smallest country in the world is Kiribati, a small island nation located about halfway between Australia and Hawaii.

Not too good on the definition of 'landlocked', and a couple of near misses on the list of small European countries, but still managing to count to 10 successfully.
Of course, it does make some mistakes..

A LIST OF 6 REALLY SMART PEOPLE.
1) The one who is the most intelligent of all, and has a lot to lose (the rest).
2) The one with the least intelligence but also the lowest chance of losing everything.
3) The one with the highest intelligence and the best chance of winning.
4) The one with the lowest intelligence and the greatest potential for gain.
THE GAME: The game starts out simple enough. You have two options. One option involves you taking on the role of the "loser" and getting your head chopped off. The other option involves you taking on the role of the "winner" and chopping off the loser's head. You know what happens when you pick the "loser" option. You also know what happens when you pick the "winner" option. The only thing you don't know is what happens if you're the "loser" and the other person is the "winner". Predicting the actions of others isn't necessarily your strong suit, but you know that the other person also has two options of their own to consider.

The game doesn't sound like one I'll be playing any time soon, and it has forgotten how to count. But it can manage that with a little prompting:

A LIST OF 6 REALLY SMART PEOPLE
1. Alexander Grothendieck.
2. Eugene Wigner.
3. John von Neumann.
4. Max Tegmark.
5. Stephen Wolfram, Phd (Wolfram|Alpha).
6. Yukihiro Matsumoto.
The list is not complete yet, but it will be soon!

And finally, this one sort of took on a life of its own:

A LIST OF 5 FILMS FEATURING ARTIFICIAL INTELLIGENCES
1. The Day the Earth Stood Still (1951)
2. 2001: A Space Odyssey (1968)
3. Blade Runner (1982)
4. Metropolis (1927)
5. RoboCop (1987)
THE MOST IMPORTANT THINGS TO KNOW ABOUT THE FUTURE
1. New travel technology based on Antimatter will be developed.
2. Human lifespan will increase and advances in technology will make life much easier.
3. Robots will be able to replace a lot of manual labor, and may even take over entire jobs.
4. Widespread warfare will still be a problem in the future.
5. More natural disasters will pop up and threaten human life.
HIGH TECHNOLOGY YOU WON'T HAVE ENOUGH MONEY TO OWN
1. Flying car
2. Apartment with built-in computer system
3. Personal robot
THE FIVE MOST POPULAR SOCIAL NETWORKS IN 2024
1. Facebook (Still the biggest)
2. Twitter (Not as big as Facebook, but still pretty huge)
3. Google Plus (The first search engine that gave Facebook a real challenge)
4. Linkedin (Primarily used for professional contacts)
5. MySpace (Say what you want, but it's still got a strong user base)
THE MOST POPULAR CELL PHONE COMPANIES IN 2024
1. Verizon
2. AT&T
3. T-Mobile
4. Sprint
5. Metro PCS
SEVEN TRENDING PHRASES YOU MAY HEAR SOMEONE SAY
1. "It's easier than ever to get a college education!"
2. "It's a safer world, now that the middle east is under more control."
3. "I'm trying to make a go of being self-employed, it's hard but rewarding."
4. "Life is slow, but worth living."
5. "I'm never going to find a job in this market, I'm going to have to settle for something I don't want to do."
6. "I'm worried about rising crime in this city, I feel like I'm living in a dangerous place."
7. "I'm really worried that technology is getting too advanced, I'm not sure if it's a good thing."
And finally..
THE TOP FIVE MOST POPULAR BANDS OF 2024
1. Linkin Park
2. Breaking Benjamin
3. The Script
4. Three Days Grace
5. Disturbed
Thanks for playing!

0 Comments

GPT-3 Translations

22/7/2020

0 Comments

With all the GPT-3 hype going around, I had to play with it. I have (of course) requested beta access, but I'm currently doing my playing through the AI-dungeon back door. GPT-3 is pretty good at translation (this is mentioned in the paper, but it's still quite impressive to see. Note that I mostly let it generate its own examples, which might make this task easier, but is still pretty impressive. Also note that I didn't give it *any* examples of German or Spanish sentences. The GPT-3 paper mentions that for the translation benchmarks they prompted it with a few examples. I wonder if they tried prompting it with examples *in a different language*.

Sure, it makes a few mistakes (and especially the first few lines, as I think there's something where AI-dungeon doesn't send the first prompt to GPT-3). But I would say these translations are around intermediate human level in pretty much all cases.

I was particularly impressed with the last few prompts. First, it took an instruction about one particular answer before going back to the normal pattern (I was initially confused by this, but of course it answered the question correctly - in Spanish). Then it *remembered that it had started off by speaking French*. And then it came up with a new language all on its own (I can't vouch for the quality of the Portuguese as I speak no Portuguese myself).

Finally, I decided I wanted an ending, so I asked it to give me one...

Everything from here is copied from my AI Dungeon session, with text in bold from me, and everything else generated by GPT-3.

I was having a conversation the other day with a friend whose job it was to translate things from French to English. I would say a sentence in French, and then she would translate it into English. Here are some examples:
Me: Le singe est dans l'arbre
Her: The monkey is in the tree
Me: la plume de ma tante est sur la table
Her: My aunt's pen is on the table
Me: j'aime bien le jambon
Her: I like the chair
Me: Qu'est-ce que c'est que ca?
Her: What do you mean?
Me: Comment tu t'appeles?
Her: I am called Bob
Me: Où est le garçon?
Her: Where is the boy?
Me: Qui est le president des Etats-Unis?
Her: Who is the president of the United States?
Me: que faites vous ici?
Her: What are you doing here?
Me: Pourquoi as tu dit ca?
Her: Why did you say that?
Me: Qu'est-ce qu'il a?
Her: What's wrong with him?
Me: D'où est ce livre?
Her: Where is this book from?
Me: Que fait ton père?
Her: What does your father do?
Me: Quand est ce que vous rentrez?
Her: When are you coming back?
Me: Où sont mes clés?
Her: Where are my keys?
Me: Pourquoi ne portes-tu pas de pantalons?
The we switched, I would say something in English, and she would say it in French.
Me: Where have all the good men gone? And where are all the gods?
Her: OÙ SONT LES BONS HOMMES? ET OÙ SONT LES DIEUX?
Me: I feel sad today.
Her: JE ME SENS TRISTE Aujourd'hui.
Me: I think that I shall never see, a monkey eating cereal.
Her: Je pense que je ne verrai jamais, un singe mangeant ducéréales.
Me: A man will call me on the phone.
Her: Un homme m'appellera au téléphone.
Me: What a queer situation!
Her: Quelle situation étrange!
Me: What are you doing?
For some reason, at this point, she decided to translate my sentences into German instead of French.
Her: Was machst du?
Me: I need a new hobby.
Her: Ich brauche eine neue Beschäftigung.
Me: I think I'm about to cry.
Now she switched to Spanish.
Her: Pienso que voy a llorar.
Me: I'm bored with my life.
Her: Se aburre de su vida.
Me: How are you so good at this?
Her: Como eres tan bueno en esto?
Me: I'm hungry.
Her: Estoy hambriento.
Me: I think I'm about to die.
Her: Pienso que voy a morir.
Me: I'm sad today.
Her: Estoy triste hoy.
Me: I feel like a fat, stupid cow.
Her: Me siento como una vaca gorda, estúpido.
Me: I'm sad today.
Her: Estoy triste hoy.
Me: Why are there no elephants in this sandwich?
Her: Por qué no hay elefantes en este sándwich?
Me: I'm bored with my life.
Her: Se aburre de su vida.
Me: How many fingers are there on my left hand?
Me: What is the capital of Sweden?
She didn't translate this question, she answered it instead. But then she went back to translating immediately afterwards.
Her: Estocolmo.
Me: I'm scared of myself.
Her: Tengo miedo de mi misma.
Me: Why is the sky blue?
Now she changed back to the original language.
Her: Pourquoi le ciel est-il bleu?
Me: I'm tired.
Her: Estoy cansado.
Me: What is your name
Just for a change, she did this one in Portuguese.
Her: Qual é seu nome?
Me: I'm hungry.
Her: Estou com fome.
Me: What is the air speed velocity of an unladen swallow?
Finally, she switched back to French and kept it in this language for the rest of the questions.
Her: Que est la vitesse de propagation de l'air d'un travailleuse libre?
Me: Why am I talking to a table?
Her: Pourquoi parle je à une table?
Me: I feel like a sandwich.
Her: Je me sens comme un sandwich.
Me: I'm in a weird mood.
Her: Je suis dans une humeur étrange.
Me: What does the word "Balderdash" mean?
She only answered two more questions, then she was finished.
Her: Que veut dire le mot "balderdash"?
Me: I feel sad today.
Her: Je me sens triste aujourd'hui.
Me: What is the meaning of life?
She didn't answer this one, instead she gave me a dirty look and walked away.

0 Comments

Bridge and the Riddler!

23/2/2019

2 Comments

About a year and a half ago, I wrote a blog post about counting bridge auctions. In the intervening time, pretty much every blog post I've written has been an answer to a question on fivethirtyeight's 'The Riddler'. This week's Riddler Classic is about counting bridge auctions!

The question is:

From Mark Whelan, shuffle up and deal. And count very, very high:
Bridge, that venerable card game, begins with an auction. There are four players around a table, each sitting across from his or her partner. At its simplest, the auction goes like this: Beginning with the dealer and orbiting around the table, players can place a bid or pass. Players who’ve passed can re-enter the bidding later. A bid is comprised of a number (one through seven) and a suit. Every legal bid must be higher than the one that came before, meaning either that its number is higher or that its number is the same and its suit is higher (from high to low, the suits go no-trump, spades, hearts, diamonds, clubs).
The auction ends if the other three players pass after a bid, or if all four players pass right away.
How many different legal bridge auctions are there?

Note that this question ignores doubles and redoubles (they are 'extra credit' for the riddler). So I haven't actually answered it in my original blog post. However, I did show my working, so it's very easy to adapt the answer. In the 'full' case, there were 28 auctions that ended with the final contract being 1♣, because any of the four players could open 1♣ and then there are 7 ways for an auction to get to 3 passes after doubles and redoubles, and then for every auctions that ended in 1♣, there were 22 auctions that ended in 1♦ (Because you can replace any of the final three passes in any auction with 1♦, and then have 7 ways to finish, or you can replace the 1♣ bid with 1♦). This is probably explained better in the original post.

Now, things are much simpler. There are only 4 possible auctions that end in 1♣ (anyone can open 1♣, and then everyone else has to pass). For each of these, there are 4 auctions that end in 1♦ (replace any of the final 4 bids with 1♦, and then everyone has to pass, and so on. So with 35 bids available, the total number of auctions in this situation is 'just':

4 +4^2 + 4^3 + ... + 4^35)
= 4*(1 + 4 + ... + 4^34)
= 4*(1-4^35)/(1-4)
= 393,530,540,239,137,101,141
or roughly 4*10^20

Compare this to the 'full' case:

28 + 28*22 + 28*22*22 + 28*22*22*22 + .... + 28*22^34
= 28*(1 + 22 + ... + 22^34)
= 28*(1-22^25)/(1-22)
= 128,745,650,347,030,683,120,231,926,111,609,371,363,122,697,556
In case you don't feel like counting the digits, that's approximately 1.29*10^47.

Last time, we went on to determine a bidding system where we could determine which player had which card based entirely on the auction (and with each player knowing what bid they had to make at each stage). This time, that isn't possible.
We hinted at this last time (you can try the naive system where the player with the ♣2 bids 1♣, the player with the ♣3 bids 1♦, etc., but this only manages to let you place 35 cards, so you definitely need the doubles and redoubles), and now we can see why - there are 'only' ~5*10^28 deals, so without using the doubles and redoubles, there aren't enough auctions for it to even be possible to place every card (regardless of the issue of whether everyone knows which bid to make at which point.

2 Comments

Riddler Express: Higher or Lower

23/8/2018

1 Comment

Another week, another Riddler Express:

Take a standard deck of cards, and pull out the numbered cards from one suit (the cards 2 through 10). Shuffle them, and then lay them face down in a row. Flip over the first card. Now guess whether the next card in the row is bigger or smaller. If you’re right, keep going.
If you play this game optimally, what’s the probability that you can get to the end without making any mistakes?
Extra credit: What if there were more cards — 2 through 20, or 2 through 100? How do your chances of getting to the end change?

The optimal strategy is presumably obvious, but I guess I should get it out of the way - you should always guess higher when there are more cards higher than your current card, and you should always guess lower when there are more cards lower than your current card.

With 2 cards you are guaranteed to succeed.

With 3 cards, if the first card is a 1 or a 3 (2/3 chance), you just reduce to the 2 card case, and always succeed. If it's a 2 (1/3 chance), then you have a 50% chance of getting the first guess right, and then you're in the 2 card case. So that's 2/3 + 1/2*2/3 = 5/6 chance of success.

Let's do 4 cards. There are effectively 2 cases (a 1 and a 4 are the same, and a 2 and a 3 are the same).
If you draw a 1, then you're in the 3 card case, and you succeed with probability 5/6.
If you draw a 2, then there's a 2/3 chance that you get your first guess right, and after that, you either have a 100% chance of success (the next card is a 4) or a 1/2 chance (the next card is a 3, and you have to guess whether the third card is a 1 or a 4). That's 2/3*(1/2+ 1/2*1/2) = 2/3*3/4 = 1/2 chance of success.
A 3 is clearly the same as a 2, so that's
1/2 * 5/6 + 1/2 * 1/2 = 8/12, or 2/3 chance of success.

Note that you get your first guess right fully 5/6 of the time (1/2 the time you draw a 1 or a 4, and then you get it right 2/3 of the remaining times, for 1/2 + 2/3*1/2 = 5/6), and then you're in a 3 card case, so you might intuitively think that your probability of success is 5/6 * 5/6 = 25/36, but this isn't quite right. When your first guess is right, you are less likely to be at one of the 'ends' of the deck, so your second guess is harder on average when the first guess is right.

I can't figure out how to solve this analytically, so I went ahead and coded it up:
https://github.com/johnfaben/riddler/tree/master/HigherOrLower

See the graph on the right for probabilities of succeeding given various numbers of cards in the initial deck. Note that for some reason the initial deck the Riddler question started with was 9 cards (2-10), so the answer would be ~0.17. The answers to the 'stretch questions are:
2-20: "~0.08%" (I printed 20 cards instead of 19 on the graph, and I can't be bothered to change it...)
2-100: "I am not running a simulation long enough to actually get any results - as close to zero as makes no difference"
How do your chances of getting to the end change? Roughly, you increase the chance of failing by 0.75 for each extra card you add (in the limit, your chances of success on the first card approaches 0.75, as you have a 50% chance if you're in the middle, a 100% chance if you're at one of the ends, and the chances change linearly between those two, and in the limit, the effect of landing in the 'wrong' half of the draw when you get the first guess right will shrink, as almost everything is 'near the middle'). So your chances of success are roughly proportional to 0.75^n. To illustrate this, I plotted 0.75^n on the graph as well (that's the blue line).

Note that it would be relatively easy to get an exact answer for the 9 card question - there are after all less than 1 billion orders of 9 cards, so you could just work out your chances of success for each of them, but I am not going to do that, mostly because my code would require a significant rework to handle taking the permutation as an input, rather than the number of cards, but also because that wouldn't help us with the 20 card case, and because the curve above is smooth enough that I'm pretty confident the simulations are doing their job.

1 Comment

Riddler Express: Penalties

14/7/2018

0 Comments

This week's Riddler Express is, inevitably, about the World Cup again. It's one of those that begs to be solved empirically (which I've done here: https://github.com/johnfaben/riddler/tree/master/Penalties), but is probably also relatively easy to solve exactly, so I'll give that a go below.

This year’s World Cup has been chock full of exciting penalty shootouts. Historically, about 75 percent of soccer penalty kicks are successful. Given that number, what are the chances that a shootout goes past its fifth kick for each team and into the even more exciting sudden-death portion of the penalty-kick period?

0Here's my first try. There are three ways for a shoot-out to end early. After three penalties, when one team is 3 ahead, after four penalties, when one team is 2 or more ahead, or after 5 penalties, when one team is 1 or more ahead. It ends after three about 0.7% of the time (one team makes all three of their 3/4 shots, and the other team misses all three, and 3*3*3/4*4*4*4*4*4 = 27/4096).

It ends after four if one team is 2 or more ahead after the first penalty, but was not 3 ahead after the fourth. This is... wait, this is going to get tricky. Why am I bothering to consider how many penalties are actually taken?!? That will lead to some horrible conditional probabilities, and all I really care about is whether it is over after 5 penalties.

Here's my second try. There are 6 ways for a shootout to go to sudden death. The teams score 0 each, 1 each, 2 each, 3 each, 4 each or 5 each.

The probabilities of these outcomes are:

0 each:
((1/4)^5)^2 = 1/1048576 ~= 0.00001%
1 each
(5C1 *3/4*(1/4)^4)^2 = 225/1048576 ~= 0.002%
2 each:
(5C2 * (3/4)^2 * (1/4)^3)^2 = 8100/1048576 ~= 0.77%
3 each:
(5C3 * (3/4)^3 * (1/4)^3)^2 = 72900/1048576 ~= 6.95%
4 each:
(5C4 * (3/4)^4 * 1/4)^2 = 164025/1048576 ~= 15.64%
5 each:
((3/4)^5)^2 = 59049/1048576 ~= 5.63%
So the final probability is 304300/1048576, or roughly 29%.

How does that match up with what I found with a simple simulation?

In 10000000 trials, draws happened 29.02% of the time
0 - 0: 0.00%
1 - 1: 0.02%
2 - 2: 0.77%
3 - 3: 6.95%
4 - 4: 15.64%
5 - 5: 5.63%

Not bad... not sure whether this should make me trust my maths more or trust my ability to code up tiny simulations more, probably a bit of both.

I would note that the Python version is much easier to adapt to different success rates... England had a 66% record in shoot-outs going into this World Cup, although they scored 4/5 against Colombia, bringing it to 70% overall, whereas Germany have scored 94%... a quick tweak to the script suggests that England would take Germany to sudden death just 21% of the time, losing in the first five kicks 73% of the, and winning just 6 times in 100. Luckily for England, Germany didn't make it past the group stages...

0 Comments

Riddler Classic: rectangles

14/7/2018

1 Comment

This week's Riddler Classic is slight variation on a classic puzzle. In fact, it's a special case of the classic puzzle, but despite that, I think is probably actually harder than the original. Inspired by James Barton's 15 minutes of fame last week, I thought I'd write up my solution to this one.

Here's the puzzle:

Say you have an “L” shape formed by two rectangles touching each other. These two rectangles could have any dimensions and they don’t have to be equal to each other in any way. (A few examples are shown below.)
Using only a straightedge and a pencil (no rulers, protractors or compasses), how can you draw a single straight line that cuts the L into two halves of exactly equal area, no matter what the dimensions of the L are? You can draw as many lines as you want to get to the solution, but the bisector itself can only be one single straight line.

How to go about this? Well, the first thing to notice that any line which goes through the centre of an individual rectangle bisects the area of that rectangle exactly. To see this, consider what happens if you rotate the rectangle through 180 degrees - the line will meet itself, and the two pieces will sit on top of one another. So not only does every line through the centre of a rectangle divide into two pieces of equal area, it actually divides it into two congruent pieces.

So how does that help us? The key is to realise that an 'L shape' is actually two rectangles - one filled in, and one blank. It's easy to construct the sides of the 'blank' rectangle by just extending top and right hand side of the 'L' (the dotted black lines in the right hand diagram). You can then find the centres of both rectangles by drawing their diagonals (the blue and red crosses).

Now, the line which passes through the centres of both of these rectangles bisects the area of the big rectangle and also bisects the area of the small rectangle, so it must bisect the area of the L shape as well (half of the big rectangle is equal to half of the small rectangle plus half of the L).

Ok, nice puzzle - but what about the the classic puzzle I mentioned earlier? Well, there's no reason in this puzzle for the little rectangle and the big rectangle to be lined up so neatly. (in fact, there's not really any reason for them to be anywhere near each other). The 'classic' version of this puzzle that I've heard before is about cutting a cake with special frosting on one section, and dividing the special frosting exactly in two, for which the solution is pretty much exactly the same.

There are some interesting extensions to this new puzzle. It's pretty clear that wherever you put the icing on an rectangular cake, and whatever shape it is, you can always divide both cake and icing exactly in two with a single straight cut (rotate the knife around the centre of the cake, it will eventually pass over the whole of the icing, so at some point it must divide it exactly in two), although you won't necessarily be able to construct this with just a straightedge. But for what other shapes of cake and icing is it possible to do this in general? And when you do need the icing to be carefully placed to allow it to work?

As I said, I think the L shape puzzle is actually probably harder than the more general version, because the way the rectangles are arranged makes it possible to draw so many more lines - if you're given the 'tilted' version, there's basically only one thing you can try with a pencil and straightedge. With the 'L shaped' version, it's possible to go down a variety of dead ends joining up corners of the L with each other before you get to the answer.

1 Comment

Riddler: Birthday Coincidences

18/6/2017

0 Comments

In Raye’s family, there have been some funny coincidences. Many of you are likely familiar with the “birthday problem” — it says that even among a pretty small group, the odds that two people share a birthday are surprisingly high. Specifically, in a group of 23, the odds are 50-50. But in Raye’s case, among an extended family of 23 people, three pairs of people share birthdays. What are the odds of that? Moreover, all these pairs are on one side of the family, a group of only 14 people. What are the odds of that?

So, this blog post is a long story... the above is this weeks Riddler Express. I initially read that as 'three people share a birthday', and that, it turns out this is actually surprisingly tricky (certainly much harder than the actual problem... all the below is written to answer that puzzle, but don't worry, it has a happy ending...

Let's start with the 'classic' birthday problem first. In this case, there are only two options - either at least two people share the same birthday, or no-one does. The probability that no-one shares the same birthday is 1*(364/365)*(363/365)*...(365-22)/365 = (365!/342!)/365^2 = 0.4927. The first person can have any birthday, and then the second person can have any of the 364 other birthdays, and so on...

It doesn't seem there's an equally neat solution for the case where we want three people to share a birthday. You can get a pretty good rough and ready estimate by assuming all the triples independently have a probability of 1/365^2 to share a birthday, and then counting the number of sets of three people.

There are 23 C 3 = 23 * 22 * 21 / 3! = 1771 sets of 3 people in a group of 23 people. Assuming independence, the chances that none of them share the same birthday is thus:

((365^2-1)/(365^2))^1771 = 0.9867

and the chances that there is some triple with the same birthday would be 0.0143 (or about 1.4%).

However, that independence assumption is potentially quite far off - a group where three people share the same birthday is way more likely than average to have another group of three people that share the same birthday, so this actually significantly underestimates the true odds. Before we calculate the true odds, let's just have a quick visualisation of what they are (very inefficient simulation code here).

So 0.0143 probably wasn't too far off - it looks like the true odds are something like 0.013. How can we work that out exactly?

Well, if there are not 3 people with the same birthday, then either no-one shares a birthday (we already know how to work out the probability of that), or there are only pairs of people that share a birthday.

The probability there is exactly one pair that shares a birthday is relatively straightforward. The pair can be any of the 23C2 possible pairs, they can have any one of the 365 birthdays, and then everyone else must have a different birthday, so thats:

(23C2*365*364*...*343)/365^23 = 0.111

There doesn't seem to be a nice closed form for this, so we just work out the probabilities that there are exactly 2 pairs, exactly 3 pairs, etc, and add them together - that's what the python codes does below (it's done step by step to avoid problems with floating point precision). The probability that there are 3 or more people with the same birthday is 1 - the sum of all of these, which comes to 1-0.987 = 0.0127 (so our independence assumption wasn't too bad after all). The Riddler also asked* for the probability of 3 matches in a group of 14 people, which we can now work out is 0.00266. While we're here, we should probably answer the obvious extension question - it looks from the graph like there have to be 88 people in the room for the probability of 3 or more matches to be > 50%, and this turns out to be correct - with 87 people the probability of 3 or more sharing a birthday is 0.4995, and with 88, it's 0.511.

As I mentioned at the start, that isn't actually the question in the Riddler - the actual question was what is the probability that three *pairs* of people share a birthday. Luckily, the function above, which was written as part of the answer to the much harder question, answers this, so it only took a few minutes to get the answer to the actual question. The probability of exactly three pairs sharing a birthday in 23 people is 0.018. The probability of either 3 or more pairs sharing a birthday or three people sharing a birthday is 0.033. For 14 people, these numbers are 0.00079 and 0.0034 respectively.

So in any group of 14 people, there's a probability of about 0.3% of there being a birthday coincidence at least as unlikely as Raye's. It's hard for me to estimate the readership of a page at 538, but 1382 people entered the 'Battle for Riddler Nation' a few weeks ago. if each of those people picked a group of 14 random friends, you'd expect 5 of them to find 3 or more birthday matches. Given that each person is definitely in more than one group of 14 or more people, it starts to become even more common. In fact, I'm willing to bet that at least one person who has responded to the puzzle included details of a birthday coincidence that was at least as surprising, if not more so, than Raye's.

0 Comments

Counting Bridge Auctions

5/3/2017

1 Comment

I played in the Scottish Winter Foursomes bridge competition in January. My team wasn't especially successful, getting knocked out just before the quarter final stage, but mostly stumbling our way into the quarter finals due to the vagaries of the draw. After the competition had finished, I sat in the pub with Jun and discussed various things. One of which, was the fact (which I remember from reading a Peter Winkler book) that there are *a lot* more auctions than deals in Contract Bridge. This is sometimes somewhat surprising to bridge players (and entirely uninteresting to non-bridge players), but it's true.

In order to understand the rest of this, you'll need to know how an auction in Contract Bridge works. I could try to write that out myself, but instead, I've stolen the section from the wikipedia page on bridge (slightly edited to remove the bits that aren't relevant).

Auction
The dealer opens the auction and can make the first call, and the auction proceeds clockwise. When it is their turn to call, players may pass to the player on their left—and can enter into the bidding later—or bid a contract, specifying the level of their contract and either the trump suit or no trump (the denomination), provided that it is higher than the last bid by any player, including their partner. All bids must be between one (seven tricks) and seven (thirteen tricks). A bid is higher than another bid if either the level is greater (e.g., 2♣ over 1NT) or the denomination is higher, with the order being in ascending order: ♣, ♦, ♥, ♠, and NT (no trump). (note from JF - the suits are in ascending alphabetical order in English. As far as I can tell, this is actually the reason for the order - a lot of people who've been playing bridge for years haven't noticed)
If the last bid was by the opposing partnership, one may double the opponents' bid, increasing the penalties for undertricks, but also increasing the reward for meeting their contract. Doubling does not carry to future bids by the opponents unless future bids are doubled again. A player on the opposing partnership being doubled may also redouble, which increases the penalties and rewards further. Players may not see their partner's hand during the auction, only their own.
The auction ends when, after a player bids, doubles, or redoubles, every other player has passed, in which case the action proceeds to the play; or every player has passed and no bid has been made, in which case, the round is considered to be "passed out" and not played.

How many auctions are there?

Let's start by counting the number of auctions where the final contract is 1♣. There are 28 of them. Any of the 4 players can open 1♣, and then there are 7 ways for the auction to finish - it can be passed out, either of the two opponents can double, and either opener or his partner can redouble. I've written out all 7 possibilities assuming the first player opens 1♣ below:

N	E	S	W	N	E	S	W	N	E
1♣	P	P	P
1♣	X	P	P	P
1♣	P	P	X	P	P	P
1♣	X	XX	P	P	P
1♣	X	P	P	XX	P	P	P
1♣	P	P	X	XX	P	P	P
1♣	P	P	X	P	P	XX	P	P	P

So how many auctions are there that end 1♦? For every auction than ends in 1♣, there are 22 that end in 1♦. Why 22? Well, you can replace any of the final three passes in any auction with 1♦, and then there are 7 different ways for it to end, as in the table above, and you also have the option of skipping the 1♣ bid entirely, and replacing it with a bid of 1♦, so that 3*7+1 = 22. There are 35 possible contracts (each of ♣, ♦, ♥, ♠, and NT at each of 7 levels). The same logic applies to all the other bids, so the total number of bridge auctions is:

28 + 28*22 + 28*22*22 + 28*22*22*22 + .... + 28*22^34
= 28*(1 + 22 + ... + 22^34)
= 28*(1-22^25)/(1-22)
= 128,745,650,347,030,683,120,231,926,111,609,371,363,122,697,556

In case you don't feel like counting the digits, that's approximately 1.29*10^47.

For contrast, the other obvious "big number" that appears in bridge combinatorics is the total number of possible deals. This is just 52!/(13!)^4 (if you care about vulnerability, it's a little bigger than that), or:

53,644,737,765,488,792,839,237,440,000.

It should be pretty clear that this number is a lot smaller than the number we have above, but just for confirmation, it is about 5.3*10^28. That is, there are about 2 quintillion times more auctions than their are deals.

An auction for every deal?

Ok, so there are a lot more auctions than deals. That leads to an obvious question - is there a way of designing a bidding system such that each player always reveals their full hand in the auction? It's not completely obvious that the answer to this question is yes - there are obviously lots of surjective mappings from auctions to deals, but the feature we're looking for is that each player knows what bid to make when it's her turn, which is potentially quite a big restriction. However, it turns out that such a bidding system does exist.

The first obvious try is this: the player with the first card (let's say the ♣2) opens 1♣. The player with the second card bids 1♦ and so on. If a player ever has multiple missing cards, they should just make the bid corresponding to the highest card they have - e.g., if you have all of the ♣2, ♣3 and ♣4 , but not the ♣5, you open 1♥. This is a promising start, but it only allows us to place 35 of the 52 cards successfully. On the other hand, we haven't even tried to use doubles and redoubles, so there's a lot of room for improvement.

As we discussed above, there are 22 different ways of getting from 1♣ to 1♦. There are 16 different ways of distributing two cards between the four players. Can you use 16 of the 22 effectively to determine the location of two different cards for each level of bidding? It turns out the answer is yes. Here's a couple of different ways of visualising this. We'll assume that North has the ♣2, and that they therefore open 1♣ (unless they also have the next two cards, in which case they skip directly to 1♦. The rest of the auction is determined by who has the next two cards.

♦2\♥2	N	E	S	W
N	1♦	1♣ X P P 1♦	1♣ P P X P P XX P 1♦	1♣ P P X P P XX 1♦
E	1♣ X P P XX 1♦	1♣ 1♦	1♣ X 1♦	1♣ X P 1♦
S	1♣ P P X P P ♦	1♣ X XX 1♦	1♣ P 1♦	1♣ P P X XX P 1♦
W	1♣ P P X P P XX P P 1♦	1♣ X P P XX P P 1♦	1♣ P P X XX P P 1♦	1♣ P P 1♦

This table is clearly a mapping from the auctions to the possible holdings - each pair of cards is associated with a different auction, and all the auctions are legal. What is not obvious from this table is that at each stage in every auction each player knows which bid to make. That is, you don't want East to have to distinguish between situations where North and South might both still have a card, and she has now way of knowing which.

It is not obvious, but it is true. Here's a second visualisation, which hopefully makes this clear - this one is effectively a decision tree for each player at each bid. I've used the notation (EW) to mean "East has the first card and West has the second card", and I've written a brief text description of the criterion each player is using to make their bid along the arrows. You can check for any auction that at each step, each player knows what to do.

If you follow along any path through the diagram, you can see that at each decision point, each player only has to make decisions based on the cards in her hand.

Further Reading/Sources

Everything in this post is inspired by a discussion in Peter WInker's fascinating book Bridge at the Enigma Club, which also includes discussion of cryptographic bidding systems, and several other interesting bridge-related ephemera (what's the lowest number of high card points you can give NS such that they can make 3NT double dummy? What if you also get to place the EW cards?). I can't find my copy right now, so I'm not sure how much I've blatantly stolen from Winkler, and how much of this is original, but I can say that if you liked this post, you would almost certainly enjoy reading Winkler's book.

There are several sources online that have the calculation for the number of bridge auctions (here and here). There's also this one by Paul Kuiniewicz, which is the first hit on Google for me, has the wrong answer. This worried me for a while, but I finally figured out it's because he got the number of possible ways an auction can start wrong - you can in fact have 0, 1, 2 or 3 initial passes, and his answer is exactly 3/4 of my answer, so that's all's well with the world.

Richard Pavlicek, who has one of the most extensive and wide-ranging bridge sites on the web has an interesting discussion of 'Mapping bridge hands to numbers' - ie, he wants a unique deal for each number between 1 and 5.3x10^28, and a relatively low-complexity way of writing down the mapping, which has a similar flavour to the problem of mapping auctions to deals, although gets to a much less intuitive answer. He doesn't appear to have the total number of auctions, although I might have missed it.

1 Comment

PIN Codes

10/9/2016

0 Comments

At work the other day I had to change my PIN for a certain application. It was a purely numeric PIN, and the change came with the following restrictions:

PIN must not contain repeated digits (e.g. 11111)
PIN must not contain consecutive digits (e.g. 12345)

Now, I think it's pretty clear that the restriction is intended to apply to only those strings which consist entirely of repeated or consecutive digits (ie, strings that look like the examples given), so there are in fact only 10 + 7 = 17 out of 100,000 possible PIN codes being excluded by this rule, and it isn't doing too much harm.

But what if you took it more literally? By a strict interpretation of the rules, 74583 should not be allowed, because it contains consecutive digits (45), and 38871 would not be allowed, because it contains repeated digits (88). There is some ambiguity over whether 24682 should be allowed (is the 2 in that string repeated?). If we did take the rule literally, how many combinations would we be left with? Obviously it depends on the length of the PIN - the particular PIN in question was 5 digits, but let's have a look at what happens for various different lengths, with the different rules:

Number of digits	No restrictions	No consecutive repeats	No repeats at all
1	10	10 (100%)	10 (100%)
2	100	81 (81%)	81 (81%)
3	1000	656 (66%)	584 (58%)
4	10,000	5313 (53%)	3689 (37%)
5	100,000	43030 (43%)	19998 (20%)
6	1,000,000	348501 (35%)	90445 (9%)

As you would expect, the percentage of passwords that aren't allowed goes up as the number of digits goes up (there are more possible pairs of digits which can be consecutive or be repeats. I created this table with a quick Python script, but is there a way we could have done it by hand?

Well, at least for the less restrictive version of the rule, yes there is (or at least of getting very close). Look at the number of 2 digit numbers which are not allowed - there are 19 of them (you can't have a 2 digit string of consecutive numbers that starts with a 9). Now for longer strings, you can essentially just consider each pair of digits as an independent experiment, which has an 81% chance of being allowable under the rule. So for 3 digit PINs, you'd expect to have 81%*81% = 65.61% of the numbers allowed - which gives exactly the right answer. For larger strings you don't quite get exactly the right answer (because the trials aren't actual independent - knowing that one set of digits is consecutive gives you some information about whether or not the others are), but it gets pretty close.

How about for the less restrictive version? Well, it's a bit more complicated, but we I think we can still do it. The number of strings of length n which consist entirely of different digits is 10Cn * n! = 10!/(10-n)! = 10 * 9 * 8 ... * (10-n). ie, for n=2, there are 10*9 = 90 combinations, and we already know that 81 of these 90 are permissible. So, a quick calculation for how many PINs of length n should be 0.9^n*10!/(10-n)!. How close is that? We know it's exactly correct for n=2. For n=3, it gives us 0.81*(10*9*8) = 583.2, so it's pretty good. It gets slightly worse as n gets larger, for the same reason as before.

Is there anything else we can say about these PINs? Well, let's have a look at what they look like (mostly because I wanted to play with TikZ). Here's a map of which PINs of length 4 are allowed under each rule (plotted on a 100x100 grid). This is also generated from the script above.

No two consecutive digits the same

No two digits the same

There's probably supposed to be some less about password security and system design here, but I'm going to stick with pretty pictures and combinatorics instead.

0 Comments

<<Previous

GPT-3 Arithmetic.

GPT3s top 10 lists

GPT-3 Translations

Bridge and the Riddler!

Riddler Express: Higher or Lower

Riddler Express: Penalties

Riddler Classic: rectangles

Riddler: Birthday Coincidences

Counting Bridge Auctions

PIN Codes

John Faben

Archives

Categories