Fair cake distribution

To ensure fair distribution of portions of cake (or whatever) between two people, there is a method called "cut and choose". One person cuts the cake, the other person chooses which of the two pieces goes to whom. It's a way of ensuring fairness without the need for a third party or authority figure. The problem is that it only applies to situations involving two people, and quite often there are three or more people involved. I've wondered for a while whether it is possible to extend the method to deal with an arbitrary number of people.

One way might be to have one person cut the first piece of cake, then someone else decides whether to take that piece or to have the cutter take it. Once you take your piece, you're out of the process (to enjoy your cake) and the other person in your cut-and-choose pair continues as cutter for the next piece. The problem is that it's really tricky, for instance, to judge a fair 1/7th of a cake by eye, so the first few cuts are likely to be very inaccurate. It's still as fair as you can get, though, because you either cut a fair piece or you lose. Cut too big and that much cake is gone from the game. Cut too small and you leave with less. The problem would be if 1/6th of the cake looked close enough to be fair, which has a carry-on effect to the rest of the cutting.
I'd love to give this experiment a try with real people, just to see if it works.

Mokalus of Borg

PS - I'm sure "share some cake with me" will be a pretty easy sell for experimental subjects.
PPS - However, "please carefully follow this procedure before eating" might be more difficult.

Logistical problems in the infinite hotel

There's a weird mathematical thought experiment to illustrate the properties of a countable infinity that goes as follows: you are the manager of an infinite hotel. That is, you have rooms numbered from 1, 2, 3 and so on, up and up, never ending, and right now, every room is full. When you get one more guest, even though every room is full, you can make room for them by moving everyone up one room and putting the new guest in room 1. The guest that was in room 1 goes to room 2, room 2's guest goes to room 3 and so on. Nobody has to leave and everyone still gets a room. This keeps working no matter how large a group arrives at once, as long as there's a finite number of them.

If an infinite number of guests arrives at once, you can still make room for them by advising every current guest to double their room number and move in there. The guest in room 1 goes to room 2, room 2 goes to room 4, room 3 to room 6 and so on. The new guests now check into the odd-numbered rooms and there's still enough space for everyone.

What I'd like to talk about, in a silly way, is the logistics of running a hotel like this. When these guests arrive, it's kind of a pain to move people. You could call up each room individually and ask them to move, but you'd never finish. You could just have the first guest relay the message to the next one, so room 1 tells room 2 to move to room 3, room 2 tells room 3 to move to room 4, and so on. Probably the best communication method is an infinite PA system so that you can address all the rooms at once.

The next part is what I always thought would get me down about staying in an infinite hotel. When that infinite group of new guests arrives, it's not so much trouble for the guest in room 1 to move next door to room 2, nor for room 2 to move to room 4. The guest in room 50 might be a bit miffed at having to move all the way up to room 100, but what about the poor saps up at room 1,000,000 and above? You'd probably still be on the move when the next call came over the PA to move up. So you start at room 1,000,000, and the manager calls out "infinite new guests, everyone please double your room number and move up there". You pack up your things and start walking from 1,000,000 to 2,000,000. Before you pass the door for room 1,005,000, the same call comes again, so now your new room is 4,000,000. It just gets further away all the time. Beyond a certain point, you're better off turning back to the check-in desk and announcing yourself as a new guest. In fact, that's probably where all these "new" guests keep coming from.

Lastly, every time you hire a new cleaner, you never see them again. They'd start cleaning at room 1, move on to room 2, then room 3 and so on down the line, never finishing until they just quit. Realistically, you probably need your guests to clean up after themselves.

Mokalus of Borg

PS - Past a certain point, though, it would be impossible to verify.
PPS - Plus, on average, you'd probably spend all your time travelling to evict guests whose credit cards were declined.

Guessing jelly beans in a jar by volume

Ever since reading an article about the packing density of M&Ms and how to calculate very closely how many fit into a given volume, I've been excited to give the technique a try on a real contest. There have been two contests I've encountered since then, but in both cases the jar was filled with jelly beans, not M&Ms. The technique still stands, but I have always found myself trying to look up the packing factor of jelly beans rather than referencing the M&Ms paper. The best answers I can find online don't state the actual packing factor, but give advice on how to calculate it. You would think, at some point, someone would have figured this out, but apparently not. Perhaps, then, I can be the first to publish a jelly bean packing factor calculation.

In the most recent competition, I was off by 4 beans. I guessed at 2cm^3 per bean and 80% packing efficiency. This means you just have to multiply the volume of the container (in cubic centimetres or millilitres) by 0.4 and you'll get a pretty good estimate. The container in the last contest I encountered was 2 litres, so I guessed 800 beans. The answer was 796 and, unfortunately, someone else had guessed 795, so they won.

Mokalus of Borg

PS - Note that these are "standard" jelly beans, about 2cm long.
PPS - The much smaller "Jelly Belly" brand or any other size won't work with this calculation.

Faith in large primes

I saw Adam Spencer give basically this same talk at Tech Ed 2011 in Queensland. He talks about prime numbers, the ongoing search for larger primes, the discovery of Mersenne primes and one particular number, known as M48, that is simply too large to show on a slide, let alone to comprehend its massiveness.
Because it has been proven prime, and it being the largest known prime so far discovered, Adam says that he knows, with the same deep-down certainty as he knows anything else, that this number is prime - it has no factors but 1 and itself.

The thing is, what he's talking about isn't knowledge as such. Rather, he has faith that this number is prime. He has faith in the computers and software that performed the proof. He has faith in the people who created that hardware and that software - that they did not make mistakes in creating them, nor in running them. That no unforseen errors occurred and were accidentally buried. That no deliberate fraud was committed in order to claim the title of the discoverer of M48 (though I'm also pretty sure that's not the case). Because unless he performed these calculations himself, Adam cannot really know that M48 is prime. He is trusting that judgment to others. Trust and faith in maths too big to do for himself. That's what Adam has. It might not seem like a significant distinction, but it makes a significant difference when discussing science.

I don't, personally, know any forensic science, archaeology, anthropology or molecular biology. I trust my understanding of those topics to trained people or, more accurately, to popular journalism of those topics, filtered through all the news channels and brains that stand between me and the scientists doing that work. There are a lot of layers to trust there - a lot of translation and assumptions of honesty or even just accuracy. The point is, a lot of what you "know" about science is based on faith in a lot of people doing their jobs honestly and accurately. That is trust or faith, but it is not knowledge.

Mokalus of Borg

PS - Faith that computer hardware works as designed is pretty well-founded these days.
PPS - There are plenty of places where the story could go wrong, though.

Vanishing area and infinite chocolate

There is a paradox or puzzle in mathematics sometimes known as the vanishing area paradox. There are several variations, but they all share the same principle, so I'll just talk about the one in the example video below:



You take a rectangle (in this case, made of chocolate), 4x6 units, and cut it diagonally between 2 and 3 units from the bottom. Make a couple more cuts, swap two of the pieces and suddenly you have a piece left over. You've created extra chocolate out of nowhere!

But you haven't, actually. It's a rounding error and sloppy measurement. The main rectangle is now actually only 5.75 units high, and I can prove it. Think about the right-hand edge. When you make that second cut, 1 unit in from the left, the cut goes partway through that first piece on its right-hand edge. The piece that moves from the top is only 0.75 units tall at that point, but the cut on the original right-hand edge takes the full piece away. You're replacing a full piece with a 3/4 piece, making the whole block of chocolate shorter. Because it's a fairly small difference, you don't notice.

If you're still not convinced, do it for yourself, but do it four times and count the resulting rectangle. You'll probably notice it getting shorter long before you get through all four times. After the second time, one of the rows will be suspiciously half-sized. After the third time, it will be a ridiculously stubby little quarter-size row.

Mokalus of Borg

PS - It's a neat trick, though.
PPS - The shorter row gets less noticeable the wider the block.