The Two Oracles

The king of Lydia is planning to attack Persia, and wants to know if the war will be successful. So he goes to ask the nearest oracle. The problem with this oracle is that she only answers in probabilities, but on the other hand, she is always correct (and doesn't give stupid ambiguous answers). That is, out of all the times the oracle says "50%", the thing really happens 50% of the times, and so on. He asks if the war will be successful, and she says that the probability of winning the war is 75%.

Not quite content with the risk, the king decides to get a second opinion. He goes to ask another oracle. She works the same way - always giving correct probabilities. This oracle says that the probability is 90%. The king thinks that sounds a lot better, but now he's confused - what probability should he expect after hearing both oracles?

We assume that the second oracle has not heard about the first prophecy (so the order of the oracles is irrelevant), and that the war is somehow already determined (the king can't, for example, lose on purpose just to spite the oracles).

The king goes to ask his advisors. The first one says, "surely now the probability must be somewhere between 75% and 90%".

The second one says: "By Bayesian logic, no answer at all is equivalent to 50%. If we get a 90% answer and a 50% answer, that means the 50% oracle just didn't know, so the resulting probability is still 90%. If we get 90% and 75%, the resulting probability must be higher than 90%."

The third one says: "We must use the naive Bayes assumption, and postulate that the probabilities are independent. Then we can calculate a resulting probability, using Bayes' theorem."

The fourth one says: "We will also need to know the a priori probability, but by the nature of war, that must be 50%."

The fifth says: "I think the oracles both know the outcome of the war, they just speak in probabilities to annoy us. They pick a probability at random, equally distributed, and then randomly chooses, with the appropriate probability, whether to tell the truth or lie."

1. Let's start with advisor four. Will his addition of an a priori probability make any difference?
2. Using the idea of advisor three, what probability do we get?
3. If advisor five is correct, what probability do we get?
4. Without making any such assumptions, what can we say about the probability?

Maths for the Lazy

A long time ago, Bengt was in school, and his teacher taught him some nifty tricks for checking divisibility.
Checking if something is divisible by 10 is obviously easy, as you only need to look at the last digit. This also applies to 2 and 5, being factors of 10.
Checking if something is divisible by 9 can be done by adding up all the digits in the number, and seeing if that number is divisible by 9. This also applies to 3, being a factor of 9.
Checking if something is divisible by 11 can be done by alternatingly adding and subtracting the digits in the number. If you get 0 or a number which is divisible by 11, the original number is also divisible by 11.
That's all good and well, but there are plenty of numbers left. How do you know if something is divisible by 7, for example? Clearly, Bengt reasons, we need to use another number base. But which one?

1. If we have another number base, how will these things generalise? With base b, the first trick should clearly generalise to all factors of b. But can we also check all factors of b-1 and b+1? Or only the prime factors? Or some other restriction?
2. If we can check all prime numbers, the rest shouldn't be much of a problem. What's the lowest possible base, if we want to check divisibility by 2, 3, 5 and 7?
3. ...and 11?
4. ...and 13?
5. Is there a quick way to figure it out for the first n prime numbers?

The Roundest of Numbers

Bengt is planning to build a... patio, I guess? Anyway, he's designing a pattern made of little square stones in a square grid. Some of the stones are in a darker colour, and Bengt wants to make those into a (filled) circle. Clearly, he can only make an approximation of a circle, much like on a computer screen. But how many dark stones should he buy? That depends of course on how big the circle should be, but some numbers are never a good choice, regardless of the size of the circle.

We can think of an imaginary circle laid out on the patio grid. Now we need to decide on a rule for how many stones should be dark. It could be
1. those which have any part inside the circle, with the circle adjusted on the grid to minimise the number of dark stones; that is, the minimum number of square grid cells needed to cover a circle of a given diameter
2. those which are entirely covered by the circle, with the circle adjusted on the grid to maximise this number; that is, the maximum number of square grid cells that can be covered by a cirlce of a given diameter
3. those whose midpoint is inside the circle (or on the periphery), with any grid/circle adjustment possible
 For example, for the first case, a circle of diameter 2 would correspond to 4 stones. But there is no circle corresponding to 5 stones - any circle that can be covered by 5 grid cells can also be covered by 4. 5 is not, as Bengt puts it, a round number, by this definition. For the last case, with diameter 1, we could fit in 0, 1 or 2 midpoints depending on the "phase shift" of the grid and the circle, so those are all round numbers.

1. According to the first definition, which are the round numbers up to, say, 20?
2. And the second definition?
3. And the third?
4. Can you find a good general method for checking if a number is round, according to the different definitions?
5. Hexagonal grid!
6. 3D grid!
7. Higher dimensions!

Two-In-One Encryption

Bengt is working on a little nuclear thing in his basement, and it's making him a bit paranoid. He's sure that shady government agents and whatnot are spying on him. For this reason, he needs a secure way to send messages to his "contacts", as he says. Now, there are various useful methods for encryption, so that should be doable, but Bengt is afraid the "agents" will capture him and force him to give them the key. So, what he needs is a way to encrypt two messages to the same cipher text - one real, and one innocuous, so that if he is questioned, he can give them the second key, and they will find the innocuous message.

We can assume that Bengt and his contact - let's call her Alice, shall we - are able to meet beforehand and exchange keys, if need be. After that, they need to be able to send several messages only using channels where the "enemy" can read. All the data has to be possible to interpret as an innocuous message.

1. What methods can you think of for doing this?
2.  What if they can't meet beforehand, and every message sent has to have this double-encryption quality?

Maximum Enjoyment of the Cinema

Bengt has gone to see a film at the small local cinema. This particular cinema doesn't have seat reservations, so you go inside and pick a seat that's free. Bengt isn't a very sociable person, so he doesn't want to sit next to anyone. If the row is empty, he sits on one end, and if anyone sits in the row already, he sits as far from them as possible. If he ends up sitting next to someone, because there are no empty seats that aren't next to anyone, he will be grumpy and not enjoy the film.

1. Imagine everyone thinks like Bengt. What numbers of seats per row would be the most suitable? We want to avoid people being grumpy, but we also want the density of people to be as high as possible, so as not to waste space. Ideally, thus, we want to make it so that for some number of guests, every second seat will be occupied. This is true for certain numbers of seats - three, for example, but not four. Which are these numbers?
2. What if the seats would be in a circle, like... some sort of circus, or something?
3. If you're up for it, try to extend the problem to two dimensions. Or more, why not.

The Ultimate Board Game

Bengt's friends are playing board games. Bengt, however, is not. He got distracted, as he often does, by trying to improve on what he perceives as flaws in the games. Now he's trying to create a new, better game. As part of that, he needs to design the ultimate board. The board in ths case can be though of as a graph - that is, there are a finite number of "squares", each of which is connected to a finite number of other squares. Connections are symmetric, so if you can go from square P to square Q, you can also go from Q to P. A "region" of the board can be defined as a subset of connected squares, and all the connections between them (a connected induced subgraph, for those into graph theory).

Bengt figures that all regions of at least size k should be different. Otherwise the game gets... repetitive, or something. Given that constraint, he wants to make the board as large as possible.

1. If we know that all regions of size k are unique, does it follow that all larger regions are also unique? Prove / disprove.
2. How many possible size k regions (or boards) are there? Solve for, I don't know, a bunch of different k I guess, maybe find an upper bound of the sequence, or better yet, find the exact function.
3. The real question at hand - how large a board can you make, given that all regions of size k have to be unique? Some k, upper bound, exact function?
4. Boards defined like this can get pretty messy to draw, so we can add an extra rule, that the connections are not allowed to cross - a planar graph, for the graph-theoretically inclined. Again, as in b...
5. ...and as in c.

File Numbering

In some ways, Bengt is an old-fashioned fellow, and he has thus far kept all his "information", as he says, in little notebooks. Let's not even ask what that information is about. The notebooks are very pretty, but now he has started moving things to the computer. That means he has an ever-growing list of files, quite a few of them. Being the rational type, he gives each file a number as filename. The problem is, the computer lists the files alphabetically, not numerically. So 11 comes before 2, etc. Very annoying! One option is of course to use preceding zeros, something like "001", "002", etc. We could easily calculate how many zeros Bengt would need to guarantee the system working for the rest of his life, but we're not going to bother, because we know Bengt would never settle for such a compromise. He wants a system that lasts forever. We could solve that with something as simple as unary numbers - that is, "1", "11", "111"... But that would mean very quickly getting impractically long filenames, so we can't do that.

To summarise, what we need is a method that uses a finite number of symbols, to form an infinite non-repeating list of strings, where the strings are in alphabetical order. But we also need the length of the strings to be logarithmic, just like for ordinary numbers. How can that be done?

Travelling Salesman

The Travelling Salesman is a classic problem. Given n cities, and for each pair of them the time it takes to travel from one to the other, find the fastest way to visit all cities, without visiting any more than once, and then come back to the starting city. This problem is well known to be NP-complete. But there might be ways to simplify it a little. Since Bengt refuses to go on holiday if it can't be done in the most efficient way, and it's clear he needs to get out more, we should try to help him.

1. Suppose the world is flat, cities are pointlike, and the time it takes to travel between them is proportional to the physical distance. Is it still NP-complete? Show that it is, or find a polynomial-time solution.
2. What if the world is spherical? Does that make a difference?
3. What if we have up to k dimensions? Or up to n dimensions?
4. Going back to the flat world, what if some roads are a little bit slower, so that the time to move between two cities is between 1 and k times the distance? What if it's between 1 and n?
5. Suppose we don't need to get back to the starting position. Does that make a difference? If not, why did they bother including that in the problem definition?
6. (hard) Suppose we don't care about finding the quickest route, but we want to avoid being on the road (between two cities) for more than a day at a time. Is there a polynomial-time solution for that?

Bengt, Fermat, and Mersenne

Fermat had a lot of clever ideas in mathematics, but the Fermat primes were maybe not his brightest one. He claimed that any number on the form 2^(2^n)+1 is a prime, and made it plausible by showing it to be true for all n up to 4. Sadly, like so many other beautiful ideas in science, it was ruined by the Germans; Euler showed that it is not true for n = 5. (Actually, Euler was from Switzerland, but never mind that now.) A bunch of other Fermat numbers have been tested, but so far none of them have turned out to be primes. It has been proven that at least up to n = 32, there are no more Fermat primes. What a bust. Another guy who thought about primes was Mersenne, and his idea was 2^n-1, where n is a prime. Those things are not always primes either, but at least it happens fairly often. Bengt has what he thinks sounds like an awesome idea. You might call them the Bengt numbers, but to be honest he's not quite sure enough that they're going to work out that he wants to name them after himself. After all, you don't want to end up looking silly like Fermat. Here's his idea: n! is divisible by all the numbers up to n. Therefore n!+1 can't be divisible by any of them, so it must be a prime. The same is true for n!-1, so you get two primes for the price of one. Bengt is happy having come up with such a brilliant idea, so he goes off to treat himself to some chocolate, and forgets all about the whole thing.

1. First, we'll play around with the Mersenne numbers for a bit. Find the first that isn't a prime.
2. Now let's see if we can help poor Fermat out. So 2^n+1 didn't work, and 2^(2^n)+1 doesn't work. What about 2^(2^(2^n))+1? Actually, never mind that - let's go a little crazy and say 2^(2^(2^(2^(2^(2^n)))))+1. Are those all primes?
3. It's probably a good idea that Bengt didn't name those numbers after himself. Explain where he got it wrong, and find a counterexample.
4. What if n is always prime? Counterexample?
5. Even if it doesn't work for every n, it might still work for infinitely many n. Does it? Are there infinitely many n for which n!+1 and n!-1 are both primes?
6. (hard) Is there any function that does what Bengt want - that is, there are infinitely many n such that f(n)+1 and f(n)-1 are primes?

Fun with the ISO 216 Standard

ISO 216 is a lovely standard. It's the one that defines the A4 paper size, and all its friends. Bengt likes papers, not just for writing on, but also for other things, like making paper airplanes. He claims that the A4 size is particularly good for making paper planes, but that would most likely be a bit of a mess to try to prove, so we'll leave this out of this problem.

One other thing they can be used for is to measure lengths. See, the meter isn't really a very convenient unit of measurement - it's historically based on the circumference of the Earth, which to be honest isn't something most people have an intuitive grasp on. The foot is better in that sense, but since people's feet aren't all the same length, that's also not quite ideal. In fact, there may not be any obvious things in nature to base a length unit on, because most things in everyday life vary in size. But a standardised paper size - well, it may not be "in nature", but papers sure are pretty much everywhere these days, and they're a convenient size too. And we could potentially set the definition of the paper size so that it fits with some scientific constant - say, a nanolightsecond; that way, the definition would be convenient for both scientists and normal people.

But there is a slight problem with the A4 as it stands: It's based on area, not length. A0 has the area 1 m², and each subsequent one has half that area. It would probably be better to define them by saying that, for example, the short side of the first one would be one meter. It's a little known fact that the same ISO standard actually defines that as well - it's called the B series. So, for example, the B4 is a quarter of a meter wide.

Still, there's another slight problem: Every other size will have half the length, but the metric system is based on powers of ten, not two. So once you get down to B10, the width is 31.25 mm - or rather, it's 31 mm, since the standard requires that they be rounded off to the nearest millimeter, which is clearly an abomination.

If you ask Bengt, this is further proof that the decimal system is inherently flawed, and we should use base sixteen instead - in that case, the area of an A4 would be exactly one d(m²), which is admittedly a confusing unit, as it's easily confused with the much smaller (dm)², but anyway. And the B8 would be one dm wide, so we could for example give all children a little notepad in that size, and use that as our unit of measurement, so we would all grow up with a remarkably accurate intuition for length units, and there would be no need to fight over it, which would probably lead to world peace.

Now, just to make fun of the decimal system and all that, let's try to construct a paper size which does the same thing but with each subsequent area being a tenth of the previous area, rather than half. It should have such proportions that if you fold the short side in half, and the long side in fifths, you get the same proportions again. It would be awfully tricky to fold anything like that, but that's sort of the idea.

1. What is the width of an A0?
2. On a side note - how long is a nanolightsecond, in, say, feet?
3. What proportions would the "decimal" system have? Suppose the short side is 1 m, how long would the long one be?
4. Is there a simple similar system where both the areas and lengths have integer ratios?
5. How far does the A series go, before they get rounded off to nothing?

The Problem with Bathtubs

Bengt is in the bath. It's very hot, because Bengt thinks real men bathe in at least 50°C, but that has nothing to do with the problem. Suddenly he notices a little bit of lint in the water. Yuck! He pulls out the plug to let the water out and get rid of the lint. We can assume that the lint is in a random location and has the same density as the water; it behaves essentially like a randomly selected water molecule. But Bengt is annoyed at how slowly the water is flowing, so he considers whether it might possibly help to add more water. That way the pressure and therefore the rate of flow would increase, right?

1. Is there any way adding water could decrease the expected time for the lint to disappear? Assume that the added water appears uniformly; that is, we can think of it in an entirely statistical way, with water molecules being added and removed at random. The only physics involved is the increased rate of flow from the pressure.
2. What if we involve a little more physics? Presumably Bengt has the sense to add the new water at the opposite end of the bathtub from the drain. Could it reasonably be expected to be a good idea?

Bengt vs. Peano, part s(0)

In the last problem, we took arithmetic down to what seems like a very fundamental level, seemingly without any preconceived ideas or assumptions. But Bengt is not satisfied.

Now, you might say, there's that definition symbol that we haven't defined, right? Peano himself famously asked "How do you define a definition?" But Bengt thinks this is a stupid question, because obviously you don't. The definition symbol is not part of the system, it's outside the system, so it's fine.

We've also sort of skipped over the issue of precedence - unless of course you decided to deal with that in your answer to the last problem, in which case, good on you - but that's not a problem either, because we could just express "x+y" as "+(x, y)" instead, that is, use only prefix operators.

No, what Bengt has a problem with is all those variables. What is x? Well, it varies, obviously, that's kind of the point of variables, but Bengt is not happy with that. Also we're assuming that there are functions, which takes arguments, and all that. And what about all those definitions of numbers? That's a great many definitions, isn't it? So either we have to make an infinite number of definitions, or we're stuck writing numbers as s(s(s(s(s(...

Bengt would like to sort out all that stuff and make everything simple. In the new system, every rule has to contain an exact sequence of symbols on each side.

Decimal numbers would be a little cumbersome to define, so we might resort to binary - once we've got that down, it's easy enough to do the same with any other base. Alternatively, we could use unary numbers, which would probably make things even easier to define, but is a pretty messy way of writing numbers. Also, to make sure we know where a number starts and ends, we'll enclose them in brackets. So eleven is written as [1011] in binary, or [•••••••••••] in unary.

Furthermore, it's probably a good idea to write the operators prefix instead of infix, so we don't have to worry about precedence and parentheses and all that. So 1+1=2 could be written (in binary) as =+[1][1][10].

As a warm-up, we could start with logical expressions. We might define true and false as... oh, it doesn't matter, really, let's just say T and F. We can always define those as something else later. If we let for example the & symbol stand for "and" (which makes sense, since that's what it means) we could write

&TT:T
&TF:F
&FT:F
&FF:F

The trickiness appears of course when we want to deal with numbers, since we can't just spell out all possibilities. But that doesn't mean it can't be done. If we take our old pal the successor function, for example, it could be written (for unary) as
s[:[•

Now all that remains is to go from there to a complete arithmetic system, not using any variables or anything else that isn't a literal sequence of symbols.

1. Define the "or" operator.
2. Define addition for unary numbers. There are various ways, with or without using the successor function - feel free to try out more than one. Note that this function (and the others) should be able to handle any natural numbers.
3. And multiplication.
4. Define the successor function for binary numbers.
5. Define addition for binary numbers.
6. And multiplication.
7. Define binary numbers in terms of unary. This obviously solves (e) and (f) automatically, so it's nice if you've got some other solution to those as well.
8. What can't you do in this type of system that you can do in Peano's? You might want to look up "Peano's axioms" if you're not familiar with them.

Bengt vs. Peano, part 0

Bengt likes maths, and he likes starting from the very basics. So that's what we're doing today.

The foundations of arithmetic are often expressed by starting from one number, zero, and one function, the successor function. We denote those by 0 and s. (The successor function of a given number represents the following number, so s(x) is what you would normally call x+1.) From those, we can easily define things like the other natural numbers:
1 : s(0)
2 : s(1)
3 : s(2)
...

We can also define the basic operators. For example, addition can be described like so:
x + 0 : x
x + s(y) : s(x) + y

Just to horrify mathematicians, Bengt decides to include infinity in the natural numbers. Just like 0 and s, it is not defined as anything in particular. Then we need a couple more lines to define addition:
x + ∞ : ∞
∞ + x : ∞

To include things like the equals operator, which is essentially a function from two numbers to a truth value, we also need to define true and false. But Bengt decides to cheat a little by reusing the numbers, like in some programming languages. Let's be a little bit original and say that 0 denotes true, and ∞ denotes false.

1. Define multiplication.
2. Define subtraction. Since we're only dealing with natural numbers, we'll use a slightly unusual definition of subtraction; the smaller number is always subtracted from the larger one. That is, what we want is actually the absolute value of subtraction. Infinity minus infinity should be zero.
3. Define equality. Remember that you can use the things you have defined in (a) and (b) - or haven't, if you skipped those.
4. Define the => operator, that is, equal-or-greater-than.
5. Define the other => operator, that is, logical implication.
6. What about logical negation? Will that be interesting somehow?
7. Finally, put those operators to use by proving that 1+1=2.

The brachistochrone, the catenoid, and a skateboard ramp

Bengt has started a new construction project in his garage. He's been working for weeks, when Alban comes by to see the finished product.
"It's a... skateboarding ramp. Bengt, have you taken up skateboarding?"
"Ha! Hell no. Do I look like a skateboarder?"
"So why do you have a ramp?"
"For experiments, obviously. That's the only reason any sane person would build a skateboard ramp in their garage."
Alban ignores the issue of sanity, and Bengt continues.
"It's not any ordinary ramp, you see. It's a brachistochrone."
"Which means...?"
"It means that if you let something slide down one side - a ball, perhaps, or why not a skateboard, as long as it's infinitesimally small - it will always reach the bottom in the same time, regardless of how high up the ramp it starts."
"How do you know?"
"I can measure the time. I have a clock chain, look."
Bengt holds up a long thin chain. He holds it with both ends at the same height, so the chain forms a U-shaped curve. This curve is called the catenoid. There is no clock on the chain.
"There is no clock on the chain." says Alban.
"No, no. The chain is the clock. Look, you hold it up by one end, and dangle it. It swings with a certain frequency, so it can be used to measure the time. You can use a shorter chain if you want a higher frequency. Since each link has the same mass, you can use it to measure mass as well! It's a multi-purpose chain indeed. Also, it has 60 links, one for each second of a minute."
"That makes no sense."
"That there are sixty seconds to a minute? No, it doesn't. But that's not my fault, you'll have to blame the Babylonians."
"That's not what I meant."
"I know that. Anyway, there should be 16 hours to a day, 16 minutes to an hour, and 16 seconds to a minute."
Alban sighs. "That would make pretty long seconds, tho, wouldn't it?"
"Yes. So we need to add another unit. I think I'll call it a ters. There are 16 terses to a second."
"So if I make a terse statement, will I be able to finish it within one ters?"
"You? I doubt it."

1. What curve is it that Bengt has built?
2. When he holds up his chain, what curve does that form?
3. The word "brachistochrone" means "shortest time". So why is the brachiosaurus not a short lizard?
4. To measure mass with the chain, Bengt wants to take it apart, in such that he can combine any number of links from 1 up to 60. How many links does he need to open to achieve that?
5. Now suppose he wants to be able to form whole chains from the parts, at any length. So the difference is that all combinations have to have enough open links that he can put them back together without opening any more.
6. If a link has mass m and length l, and you hold it so that n links are doing a pendulum motion, what is the frequency? You can assume that the chain is homogeneous.
7. How long is a ters, according to Bengt's definition?

A Childish Problem

Bengt has no children of his own, for various reasons. Mainly because he's such a big baby himself, most likely. He does occasionally enjoy the company of children, though. Particularly the geeks. From them, he has now learned a classic old problem. The task is to continue the sequence:
1
11
21
1112
3112
211213

1. What is the next element in the sequence? It's probably easier if you think like a child.
   
2. We can imagine three possibilities for the long term behaviour of the sequence: either it settles on one element, repeating that, or it goes into a loop, repeating a subsequence, or it continues forever without looping. Which one is it?
   
3. We could start the sequence with some other start value. Which of the three behaviours are possible?

Misunderstanding Maths

Bengt and Alban are doing some calculations. Actually, Alban is doing some sort of homework, and Bengt is playing around with his calculator. Bengt tries to draw a graph, of sin²(x), but he has done something terribly wrong. The curve he gets looks a lot like k*sin(x), where k ≈ 0.841470985.
"This calculator is stupid." says Bengt.
"I think it's probably you who's made a mistake." replies Alban.
"I know that, you silly engineer. But it has a resolution of 96x64 pixels. I'm pretty sure my digital watch from the eighties has a higher resolution."
"Yeah, that is stupid. Anyway, I'm having some problems too."
"Good ones?"
"Maybe to you. It says here that the results are in the interval k ± s. But when I look at them, it seems that only a fraction f of them are."
"Interesting. What's f?"
"It's two thirds, I think… or maybe just a little more."

1. What has Bengt done wrong?
2. Is the curve that Bengt has found actually a constant times sin(x)?
3. What is causing Alban's confusion? And what is f?

Hole Puncher of Horrors

Bengt is building a machine. It is a most unusual kind of hole puncher. It consists of a holder for the papers, and a rather nasty-looking wheel with n sharp spikes pointing outwards at regular intervals. As the machine operates, the holder is pressed against the spike wheel, so that one spike makes a big hole in the paper. (One big hole is more effective than several small, says Bengt.) Occasionally, a spike will break. This is where it gets really clever, or so Bengt thinks. The broken spike falls off completely, making that side of the wheel lighter. If the centre of mass of the wheel is not in the axis, the wheel will spin to orient itself with the centre of mass downwards. That way, Bengt figures, the broken spike will automatically be replaced - at least for a while, until enough of them have been broken.Ideally, we would like to design the device so that this can happen as many times as possible before there is no longer a spike pointing at the paper.

At which angle on the wheel, relative to the downward angle, should the holder be located? Are some choices of n better than others? Obviously more would be better, but aside from that?

Bengt vs. Turing

Bengt's friend Alban is an engineering student, and he's trying to show Bengt that he's not completely ignorant in the more theoretical fields. As we all know, that sort of showing off can be dangerous when Bengt is involved.
"...and so, there is no program which, for any given input program and starting values, determines whether that program stops." says Alban.
"There is too."
"What? No, there really isn't."
"Is too."
"Now you're being silly."
"How much memory does your computer have?"
"16 gig, why?"
"Imagine if you had infinitely big programs. The algorithm itself might be infinitely long, and it might use an infinite amount of memory. Could there be a program which for any such program determines whether it stops?"
"If it's infinite, it doesn't stop, does it?"
"It might. It could stop on the first line, even if it has infinitely many after that."
"Okay, fine. In that case, no, obviously."
"Obviously indeed. Now let's say the programs are not infinite. For example, they might be no bigger than your 16 gig. Or more generally, n bits. Program and variables included. Is it still impossible?"
"I think so... isn't that what the theorem says?"
"I sure hope it doesn't. I can do it in O(2ⁿ) time."
"That's an insanely long time."
"But not infinite."
"Not even a little?"
"Afraid not."

1. It seems unlikely that Bengt has proven Turing wrong. Where is the leap in Bengt's reasoning?
2. Given his somewhat special version of the halting problem, can you find a solution that runs in O(2ⁿ) time?
3. Is there perhaps an even faster way? Can you find one that is faster than O(2ⁿ)? Or prove that there isn't one?
4. Let's ignore Bengt's sneaky redefinitions, and try another modification to the original halting problem. Let A be a program that may or may not stop, and let B be a program trying to check whether A stops. Let f(A,B) be the statement "B can determine whether A stops". The theorem says that "∃B ∀A f(A,B))" (there is a B that works for every A) is false. But what about "∀A ∃B f(A,B)" (for every A there is a B that works)? Can we, for every program, find a testing program that checks if it stops? If A is also allowed to take a number as input, does that make a difference?

Red Light Optimisation

Bengt is cruising around in his car, when suddenly he comes to a red light. The annoys him very much. In order to minimise his annoyance, he would like to make sure he gets through as quickly as possible. The thing is, if he drives all the way up to the light and stops, it will take several seconds to accelerate, and we can't have that, now can we?

We can safely assume that Bengt is driving at the maximum allowed speed, v, when he is not taking the traffic light into account. As a simplification, we'll assume that his maximum acceleration (forward) is a constant m, and that he can break (i.e. accelerate backward) without limit. The question is of course, what speed should he drive at, as a function of something suitable, like perhaps the distance to the traffic light, or some kind of time?

1. First, let's simplify a little further, by assuming that Bengt just wants to maximise his speed at the moment the light turns green. In a sense, we are saying that m is close to zero, which is somewhat insulting to Bengts car, but might make the calculations easier.
   Suppose now that we have no idea when the light will turn green. Can the problem be solved? If so, please do.
2. Suppose instead that the light turns green after an average time T, and the probability that it will happen in the next moment remains constant - that is, the red light has a "half-life".
3. Suppose instead that Bengt sees the light turn red at a particular time (or distance, if you like) and that it will turn green at any time between then and another time, which, for simplicity, we might call "one minute later".
4. Now do a), b) and c) again, but remove that simplification about the acceleration being close to zero.
5. Pick the option that you think is the most realistic, and find how much time he would save by doing all this rather than driving as fast as possible up to the light.

A Simple Board Game

Bengt is in the mood for designing a game. But his imagination is not at its best. He was up late last night, and... well, never mind that. He's making a rather simple board game, one of those where you roll a die and walk along a path. As soon as you reach (or pass) the finish line, you win.
The game is played with a special k-sided die. Just to be completely clear, the die shows each integer from 1 to k inclusively, with equal probability. At the start of the game, you also get a few cards which do various things, but apart from that nothing much happens in the game. There's supposed to be several types of cards, but so far Bengt has only come up with one type. This card can be played right after you've rolled the die, and lets you double the number of steps. Thus, obviously, it should be played when you've rolled a rather high number. Bengt calls this card "the doubling card". He really is unimaginative today.

1. Imagine you are n steps from the finish line, and you want to reach it in as few turns as possible. You have one doubling card. You roll the die. What is the minimum value on the die roll for which it is a good idea to use the card?
   
2. What if you have c cards?
   
3. If there are other players involved, and your goal is not to win as soon as possible but to beat the other players, does that affect the optimal strategy at all? If so, how?

A Cup of Tea

Bengt is back from his winter holiday, and he's exhausted. So he sits down by the fireplace with a nice cup of tea. The cup is cylindrical, at least on the inside, with radius r and height h. He has three footstools; first he had two, because he figured he has two feet, but then he added another to put his cup of tea on. The stool-tops are horizontal - Bengt's woodworking skills are dubious, but he didn't make these. As the tea stands on the stool, the depth of the tea is d. Then he picks up the cup, and tilts it towards him, as people tend to do when drinking.

1. At what angle is the bottom no longer covered by tea?
2. At what angle does the tea reach the top of the mug, and thus Bengt's mouth?
3. Come to think of it, Bengt is curious about how fire works. It emits light, that's plain to see. But is that light just black body radiation, or is it some sort of chemical process that emits light in itself?

Easy Month: Rock Paper Scissors

Bengt and Alban are playing Rock-Paper-Scissors. Unsurprisingly, it soon turns into a discussion of game theory.
"Suppose you get one point for every round you win." says Bengt.
"Sounds reasonable."
"And suppose you play forever."
"Sounds a lot less reasonable."
"Oh, you know what I mean. You play for a really long time so that everything becomes statistical and stuff."
"Okay, sure."
"So, question: What is the optimal strategy?" asks Bengt.
"That depends on what the other guy does."
"Yeah, but assuming you don't know anything about the enemy's strategy."
"Enemy?"
"Or opponent, whatever."
"There isn't one."
"Right. There isn't any strategy that makes sure you win. So we just slightly redefine 'optimal', just for the sake of this problem, to mean the strategy which makes sure you play even. In the long run."
"Actually, it's very unlikely that you'll play even, in a very long game."
"Oh, you know what I mean. You'll sort of play even, almost."
"It's not like you to be so vague."
"All right, how about this: The optimal strategy is the strategy such that regardless of the enemy's strategy the expectation value of one's score minus the enemy's score is zero."
"Sounds good. And that strategy is to pick a sign at random."
"Specifically, with the same probability for each sign. That's important."
"Okay, sure. What's your point?"
"Well, it's boring. It's no fun if you can't win. Maybe we could ban the use of that strategy?"
"I don't think that would work."
"Fine. Let's think of some other games. Here's one: It works the same, except that if you win with a rock, you get two points instead of one."
"Eh, sounds like fun... Here's one I've heard of: Rock-Paper-Scissors-Lizard-Spock. It's like the normal game but with five signs. Lizard beats paper and Spock, Spock beats rock and scissors."
"Oh, I have another one: Rock-Paper-Water-Lichen-God."
"Okay, how does that work?"
"Well, paper beats rock as usual, and it also beats lichen, because, I don't know, you can scrape it up with the paper or something. Lichen beats rock and water, because it grows on the rock and drinks water. Water beats paper, obviously, and it also beats rock, because dripping water can wear down the rock."
"Wait, so they all beat rock?"
"Yup. And God beats all of them. But rock beats God."
"How does rock beat God?"
"It's the rock from the Omnipotence Paradox."
"Oh, that rock. I see."

1. In the original game, the so called optimal strategy is, as Alban said, to pick each sign with equal probability. But what happens when you make the modification that winning with rock gives two points? What distribution should you use to be "optimal"?
   
2. How about the five-sign game, Rock-Paper-Scissors-Lizard-Spock? With equal points, the optimal strategy is again of course to use equal distribution, but what if winning with rock scores double?
   
3. Finally, Bengt's own invention. Now we give one point per win again. What is the optimal distribution?
   
4. Alban is of course right in saying that you are unlikely to play even, after a large number of games. After n games, what is the expectation value of the (absolute) point difference?
   

Easy Month: How to Start a Rebellion

Alban is trying to convince Bengt to play a table-top role-playing game, one of those things with lots of little warlike figurines.

"This guy doesn't like your leadership, he's decided to start a rebellion." says Bengt.
"What? No he hasn't."
"Has too."
"Well, he can't do anything about it, because the other orcs will blow his head off if they find out."
"Aren't the orcs supposed to be some kind of fantasy monster kind of guys? You mean they have guns?"
"They sure do, and they don't like traitors."
"But they're also not happy with the way that guy in black is pushing them around. In fact, out of the n soldiers, I believe a fraction k (so k*n soldiers) would like to join the rebellion."
"Oh really. But in that case, there are also p*n soldiers who would kill those rebels if they knew about it."
"Why p?"
"I don't know, p for… peace? No, I know: Police."
"Haha, yeah, okay."
"What, why did you pick k?"
"K for constant, duh. Anyway, that leaves a fraction 1-p-k, let's call it… r, for remaining. A total of r*n soldiers who couldn't care less."
"Or at least they don't care very much. It might be that they care slightly, but not enough."
"True. So, each of the instigators of the rebellion…"
"…who are infinitesimally few compared to n…"
"…but many compared to 1/k, he asks one other orc at a time whether he would like to join the revolution. If it's a k-type guy, he joins, and goes on to ask other random guys. If it's a p-type, he shoots the guy for asking. If it's an r-type, he just says no."
"And how does it end?"
"Well, the rebels keep track of the opinions of all the guys they have previously asked, so they don't ask them again. When they have asked everyone, they start the rebellion."
"Do you think they can win?"
"That's not part of the question."

1. What conditions must p and k satisfy for the rebellion to spread?
   
2. Suppose the potential rebels (the k-guys) are not so keen on getting shot, so they only agree to asking two other random guys. What are the conditions?
   
3. As in a, but suppose when a rebel asks a p-guy, they both have equal chances of shooting the other guy.
   
4. As in c, but as in b, not as in a.
   
5. As in d, but now suppose if the asking guy gets shot, the rebels don't know who the askee was, so they will eventually ask him again.
   
6. Sort of like in a, but now the rebels are a little more cautious: The instigators all know each other, but each new rebel knows only the identity of his recruiter (and recruitees). Each day, each rebel who has not already asked q people ask one more. They might therefore ask a guy who has actually already joined, in which case that guy thus effectively has another recruiter. If a rebel asks a p-guy, they both get shot. If a rebel has no recruiters still alive, he loses contact with the group and reverts to the same state as before he joined (also resetting his asking quota). When the instigators determine that half the soldiers have been asked, they start the rebellion. What should q be in order to make the rebellion likely to happen?
   (This one might be more difficult. You can solve it next month, if you like.)
   

Easy Month: Jumping in the Lift

Bengt is watching "QI" on BBC. It's the kind of show which really gets Bengt going, because he doesn't want to accept that people know things he doesn't.
The show brings up the old myth of the falling lift - that if you are in a lift, and the cable snaps so that the lift falls, you can save yourself by jumping just before the lift hits the ground. Since you are not standing on the lift floor when it hits the ground, you would supposedly be unaffected by the impact. Bengt doesn't believe in the myth, of course, and has nothing but contempt for anyone who does. But still, it gets him thinking.

By jumping just before impact, you would after all get a certain speed upward, to be added to the speed downward which you already have. How high can a person jump? Bengt looks for the world record for standing high jump; his sources claim that it is 1.914 m. This, incidentally, very closely matches the height of Stephen Fry, the host of the show. Bengt pictures one Stephen Fry jumping over another Stephen Fry, and finds the image very amusing. Now, that record isn't for the center of mass, and we can't expect an average lift jumper to match the world record anyway, so Bengt decides a person can jump 1 m, for physics purposes.

How high would the lift fall? Not every lift goes up hundreds of meters, Bengt reasons. Suppose you fall 4 storeys. How high is a storey? Well, Bengt thinks, it should be high enough that Stephen Fry wouldn't bump his head if he jumped, so that makes 2.914 m. (Bengt is forgetting that floors aren't infinitely thin, but it doesn't matter.) In the lift, hitting your head on the ceiling shouldn't be a problem, if you jump at the right moment.

Bengt realises that this problem would be tricky to solve without a calculator, and therefore gives you the extra clue that (2*√(2.914)-1)^2 / 2 = 2.914.

1. The impact after jumping would be equivalent to falling from a slightly lower height. How many storeys might that be?
2. The show claims that the best thing to do is to lie down on a fat person to cushion your fall. Why might it be tricky to lie down in a falling lift?
3. A lot of people are afraid of lifts, partly because they think that the cable might snap and the lift fall down. In fact, this is extremely unlikely. In the year 2000, modern lifts had been around for about 150 years, and there were 6 milliard people in the world. According to Bengt's mysterious sources, there was one lift per 1000 people, and the average lift made 200 transportations of people per day. By assuming that the lifts were built at constant speed - the number increased linearly from 1850 to 2000 - Bengt is able to calculate the risk of such an accident happening to a given person on a given lift ride; it is 0.000000000003%, making the modern cable lift probably the safest vehicle ever invented.
   How many times had such an accident happened?

Easy Month: A Ton of Feathers

It's time for another of the fabled Theme Months, and this month, despite lack of better judgement, Bengt has decided to do something truly wild and uncharacteristic and give you some problems that are in fact not insanely difficult! Let us savour the moment. The idea is that these problems should be possible to solve not only without a degree in science, but also without a calculator.

There's an old joke which goes: "Which is heavier, a ton of lead or a ton of feathers? Drop it on your toes and you'll see!" Now, for some reason, Bengt has got himself a big cube of some sort of fabric material stuffed with feathers. He's has some vague plans of using it in a giant board game, but for now, he amuses himself by dropping it on his feet. There's no need to worry; it doesn't hurt at all. But having a scientific and somewhat peculiar mind, he wants to find out just how fast the cube is falling when it hits his foot. The cube is 1 m high, and we can ignore air friction and the height of Bengt's toes.

1. Suppose Bengt drops the cube from 1m. What is the speed when it hits his toes?
   
2. Suppose instead that he balances the cube on its edge, and lets it fall. At which speed will the fastest part of the cube move when it hits his toes?
   
3. Suppose he instead balances it on a corner?
   
4. If you put them on a pair of (very large) scales, which would seem to be heavier, a ton of lead or a ton of feathers?
   

Text-Chatting Aliens

The aliens flying above Bengt's house are having some difficulties contacting their home planet. They want a unified protocol for sending information about location from each of their many space ships scattered around the galaxy, and they want to use earthly communication standards, so as not to be detected. They tried using TCP/IP, but found it to be a terrible and outdated standard. For lack of a better alternative, they decided to use SMS.
Each text message can contain either the name of a star (the aliens all know where the stars are), or a number (such as the distance from said star). They want to use as few messages as possible.

Device a system for them to identify a location. The aliens will all be informed of the new standard. How many messages will they need?

Phone Strategy

Bengt is doing his exercise routine. It takes quite a while, mostly because he is too lazy to work very hard, so he doesn't get tired very quickly. In fact, his so called exercises mostly consist of posing, because he has seen that body builders do that a lot. It takes a predetermined time before Bengt gets tired, but there is no way to know in advance how long that is.
For some reason, Bengt has several friends. Now Sture wants to see him, but he knows that he has to wait until Bengt is finished with his exercise routine. It wouldn't do to disturb Bengt in person while he's busy with something so important, so Sture will phone him instead. The more often he calls, the sooner he will find out that Bengt has finished. Unfortunately, whenever he calls, Bengt has to take a break for one minute to answer the phone, so the time until he is finished is delayed by one minute. Sture now has to come up with the best strategy for getting a hold of Bengt as soon as possible.

1. Suppose Sture knows that Bengt always exercises for an hour, but he doesn't know how long it has been since he started. At which times should Sture call?
   
2. Suppose instead that Sture does know when Bengt started, but that the exercise varies. Sture has determined from experience that the exercising takes one hour on average, and that the probability that he will finish in the next short moment remains constant. If he doesn't call, after how long is the probability 1/2 that Bengt has finished?
   
3. With those conditions, at which times should he call?
   
4. Suppose instead that the probability density of finishing decreases, so that after a time t (not including phone pauses) the probability that he is still exercising is 1/2^t. What is then the probability density?
   
5. In that case, when should Sture call?
   
6. Suppose instead that Sture has already determined that the best times to call is once every hour. What is the probability density?
   
7. And suppose it is instead best to call after 2^n minutes, for non-negative integer n. What is the probability density?
   
8. After all, Bengt has more than one friend. With the conditions in question a, suppose Alban is also trying to call Bengt. Neither knows when Bengt started, nor when the other person called. Each wants to reach Bengt as soon as possible. As soon as one of them reaches Bengt, the other person has to wait another time p before Bengt is finished with the first person. What is the optimal phone strategy this time?
   
9. And what if we do the same thing with the conditions from question b?
   

Marble Problem 3

Sture has finally got tired of playing with marbles, but Bengt continues with the fervor of a true scientist. He is still building pyramids, of four marbles each. But the floor can be a little slippery sometimes, and then the pyramids won't stick together. Bengt intends to do something about that. One of his ideas is to give the marbles electrical charge, in order to make them stick to each other.
The marbles have diameter 1 cm and mass 1 g. They are not conductive, so they do not lose their charge when touching each other or the floor.

1. An easier way to get marbles to stick together is to use glue. Suppose each marble exerts a glue-force on each marble that it touches. How big must the glue-force be to hold the pyramids up, if there is no friction at all? (That is, neither between a marble and the floor, nor between a marble and another marble.)
   
2. Forget the glue, and let's investigate the friction a little more. What happens if there is a large friction between a marble and the floor, but no friction between a marble and another marble?
   
3. And what if it's the other way around - large friction between a marble and another marble, but no friction between a marble and the floor?
   
4. Suppose the friction against the floor is very large. How big must the the marble-marble friction coefficient be to keep the pyramid up?
   
5. Suppose both the frictions are the same. How big must the friction coefficient be to keep the pyramid up?
   
6. Bengt also wants to build the ball-shape mentioned in Marble Problem 1: One central marble, surrounded by as many other marbles as possible, all touching the central marble. With no friction, what glue-force is needed to keep this arrangement standing?
   
7. Without glue, could enough friction keep it up? Assume very large friction against the floor. How big must the the marble-marble friction coefficient be?
   
8. Now suppose we want to do something even more extreme: Let there be a force between two marbles, which is just enough to overcome gravity, so that Bengt can hold one marble and let the other hang from it. Clearly this is possible with a glue force. But could this force be described by a friction coefficient, if it is extremely large?
   
9. Let's try with those electric charges. Two marbles have equal and opposite charge, enough to hang one marble from the other. How big must the charge be?
   
10. What if you have three marbles hanging like a chain, the one in the middle being positive, and the others having equal but negative charge?
    
11. What if you have n marbles in a chain, with equal and alternating charges?
    
12. Returning to the case with three marbles - is there a better way to distribute the charges? Find the setup such that the sum of the absolute values of the charges is as small as possible.
    
13. And for n.
    
14. We can also use charges to get the pyramid to stay up. If the top marble has positive charge, and the bottom ones have negative charge of the same magnitude, will that help the pyramid stay together, or will it actually force it apart?
    
15. Suppose instead that the charge of the top one can be larger than the others. What should the charges be to get the pyramid to stay up? Assume there is large floor friction but no marble-marble friction, and minimise the largest charge magnitude.
    
16. Even more freedom: Arrange the charges, magnitude and polarity, any way you like, and again minimise the largest magnitude.
    
17. And what if there is no friction at all?
    
18. What about the ball shape? If there is more than one possible shape, which one is better? Assume that there is large floor friction but no marble-marble friction. Also assume for convenience that the middle marble is positively charged. To get the best result (that is, minimise the largest magnitude), which marbles should be positive and which should be negative?
    
19. And what would those charges be?
    
20. And what if there is no friction at all?
    
21. There is yet another, even more unrealistic way to get the marbles to stick together. What if they were really heavy, so that gravity kept them together? Consider the case of one marble hanging from another. If they have the same mass, how heavy must they be?
    
22. And what about the pyramid? Assuming large floor friction but no marble-marble friction, and same mass for all marbles.
    
23. And what if there is no friction at all?
    
24. For completeness: The ball shape. Large floor friction but no marble-marble friction.
    
25. And what if there is no friction at all?
    
26. Bengt decides to finish off the alphabet by putting u and i together. Take one of the marbles from question u, charge it up, and hang it from a normal 1 g marble like in question i. How big would the charge have to be? And how big, roughly, is the theoretically biggest positive charge 1 g of normal material can have (that is, with every electron removed)?
    

Marble problem 2

When we left them last week, Bengt and Sture were building pyramids out of marbles. Since time in problem-space is independent of time in the real world (and also, I wrote this problem a while ago) they are still working on that, but they are nearly finished. Oh boy, they have built lots of pyramids.

There are twelve marbles left in the bag. Each marble is either black or white. The marbles are otherwise identical. Sture takes four marbles, and then gives the bag to Bengt. Bengt takes three marbles and places them on the ground. They are all white. He reaches in to take one more.

"I wonder what the probability is of the last one being white." says Bengt.
"Well, if those three were white, then there are most likely fewer white left."
"But on the other hand, the fact that these three were white suggests that there were more white ones than black ones when you gave me the bag."
"Hm. Sounds like a good problem."
"I don't know. I think it might be a bad problem, actually."

1. Is it a good problem? Or, more specifically, is it a problem that can be solved? Is it possible to say anything about the probability with the given information, and in that case, what?
   
2. Assume that half of the marbles are white when Bengt gets the bag. Same question.
   
3. Assume instead that half of the marbles are white to begin with, and that Sture takes four at random.
   
4. Assume instead that half of them are white to begin with, but Sture takes four of the same colour.
   
5. Assume instead that half of them are white to begin with, but Sture starts by taking two of the same colour, and then picks the other two at random.
   
6. Assume instead that we don't know the original distribution, but that each marble is originally equally likely to be black or white, and that Sture takes four at random.
   
7. The same, but Sture takes two of each colour.
   
8. The same, but Sture takes four of the most prevalent colour. (If they are equally common he picks a colour at random.)
   

Marble problem 1

Bengt so enjoyed having a themed month, that he insists on doing it again. This time it's Marble Month, so he invites Sture over to play with marbles. Sture says that he has lost his marbles, but that he'd be willing to make trite jokes about balls instead. But Bengt has made up his mind, and we all know how stubborn he can be.

Bengt brings out his bag of marbles. The marbles are physically identical; they have the diameter 1 cm, and mass 1 g. They start building pyramids, by placing three marbles next to each other in a triangle, and one on top.

1. With four marbles you can build a pyramid of 2 levels; how many marbles do you need for n levels?
   
2. And how high is such a pyramid?
   
3. Another shape that one can imagine, altho it's hard to build with marbles, is a shape where a central marble is surrounded by as many other marbles as possible, each touching the central one. How many marbles can you fit in?
   
4. In how many shapes can it be done?
   
5. That arrangement can also be extended. You can add another layer, such that each marble in the new layer has to touch one of the last layer. If you keep going, the shape will look more and more like a regular polyhedron. Which one?
   
6. How many marbles will you have in n layers?
   
7. Imagine that the pyramid is enclosed in a tetrahedron. It is just big enough to contain the whole pyramid. The walls are water- and airtight, but have negligible mass and thickness. Would the contraption float on water?
   
8. They build a number of pyramids - the small kind, just four marbles. If a pyramid "goes off", the middle marble drops down and the other three roll away at the same speed. What speed will they move at?
   
9. In the end, they will have n pyramids. They are randomly distributed in a roughly circular area a of the floor (a really big area), and oriented in random directions. If a marble hits a pyramid, it will go off. It should therefore be possible to set up a chain reaction of the pyramids, with marbles from each busted pyramid setting off other pyramids. How big must n be to achieve "critical mass", so that setting off a few of the pyramids is likely to set off a large part of the others? Assume that there is no friction, and no energy loss in collisions, and that the marbles disappear when they leave the area.
   

Bad Traffic Behaviour

Bengt is walking along an infinite straight road. He has 1000 s left to walk. But he also needs to cross the road. The safest way to cross is of course to go straight across, perpendicular to the road, which would take another 10 s. But Bengt is determined to cross the road the fastest way possible. What makes it more complicated is that there are cars arriving at random. The average frequency of cars is one per 100 s, and he can spot them 10 s in advance. To a good approximation, the cars are moving infinitely fast (so Bengt's movement does not affect the time it takes the car to reach him), they are very wide (so Bengt has to be completely across before any car reaches him) and there is no correlation between their arrivals.
So he wants to figure out the right path to follow in order to minimise the expectation value of the time. As soon as he sees a car, the answer is obviously a straight line from his current location, such that he reaches the other side in 10 s. At the moment he can't see any cars, but they could appear at any time.

Which path should he set out to take across the road?

Ill Logic

Bengt is feeling ill, and is lying in his bed playing around with ternary logic, modal logic, and some other things that he's not sure about the proper terms for.
Given these premises:

• All donks are ganks.
• Every gank was created by another (older) gank.
• Binks are more likely to be donks (in other words, there is a higher fraction of donks among binks than among non-binks).

Evaluate the following statements as definitely true, definitely false, or unknown.

1. Donks are more likely to be binks.
2. Some ganks are donks.
3. Some things are not donks.
4. There was a first gank.
5. There is an oldest gank.
6. If some things, but not all, are binks, and there are no ganks, then some donks are not ganks after all.
7. If all things are binks, then there is at least one donk.
8. If all things are binks, and there are some things that are not ganks, then there is at least one donk.

Chess problem 3

Chess Month continues with another very chaotic chess challenge.

1. What should white do?
   
2. Bengt has come up with another peculiar game. It's rather zen-like, or so Bengt thinks, anyway. Others might say "boring" is a more fitting description. Anyway. There are three pieces, all identical. The board is a chessboard, and it is empty when the game starts. In each turn, the player can add a piece to the board, or remove one, or move one from any square to any other empty square. You are not allowed to make a move so that you get a situation on the board which you have had before. (A different piece in the same square counts as the same situation. You can't add a piece after it has been removed.)
   How many turns can the game last, at the most?
   
3. This game could also be played with two players. If the winner is the first person who is not able to make a move, who wins - the player who starts, or the other one? (Assume that they are using optimal strategies, that they want to win, and so on.)
   
4. How many turns will it last?
   
5. Do questions b, c and d again, but with n pieces instead.
   

Chess problem 2

Bengt doesn't often play chess. It's not that he doesn't like it, but he gets upset when he loses, and people don't like Bengt when he's upset. So most of his friends don't play with him anymore. But he still likes to make up weird chess problems, usually involving completely unrealistic situations, that would never appear in an actual game. Here's another one:

1. What should white do? Bengt can come up with a rather simple solution that leads to mate in four moves, and a more unusual one that leads to mate in only two moves.
   
2. Since Bengt doesn't have anyone to play with, he makes up games and challenges for himself. His latest idea is this: You place a number of white pawns in any of the 16 squares forming one quadrant of the board, let's say the upper left. Then you place a number of black pawns in the quadrant diagonally opposite, in this case the lower right. When you've placed all the pawns, you suspend the board, balancing it on the diagonal between the quadrants, so in this case you lift the lower left and the upper right corner, so the board can pivot around that diagonal. The aim of the game is to get as many more black pawns than white pawns as possible (black pawns minus white pawns should be as big as possible), but so that the board does not tip over to the black side. How many is it possible to get?
   Assume that the pawns are pointlike and stand in the middle of the square. You are allowed to use more than one chess set, that it, more than eight of each type of pawn.
   

Chess problem 1

There are many kinds of good problems, not just ones involving complicated maths and physics calculations. So, this month, it's Chess Month! Here's the first one:

1. What should white do?
   
2. We can't avoid adding a little bit of maths after all. Think of the chessboard as a mathematical pattern. Each point on the board is either black or white. The colours are equivalent; in other words, if you invert the colours and rotate the board, you get the same thing. The length of the side of a square is 1, and there are no points outside the squares. Now, imagine drawing a line so that every point on the line is white. What is the upper limit for the length of such a line?
   
3. Is there any maximum length at all?
   

Too Fast for Physics

Bengt and Sture are cruising down the motorway. Bengt is driving.
"Why are you driving so slowly?" says Sture.
"I'm not driving slowly."
"Oh, I get it. You're going to say that since you're driving east, the rotation of the Earth is added to our velocity, so we're actually going really fast."
"No, that would be silly. Also, in this place at this time of day, the rotation of the Earth around its axis is completely counteracted by the rotation around the sun, so the speedometer shows our actual speed in the inertial reference frame of the sun. No, I'm just saying I'm driving as fast as the speed limits allow."
"Which is really slow. QED. And by QED I mean 'quick easy driving'. I never thought of you as the kind to follow laws."
"I always follow the laws of physics."
"Yeah, and I'm not asking you to drive faster than 3*10^8 m/s. Just a little bit quicker than this."
"Well, I'm just being an environmentalist. Mostly because it contains the word 'mentalist'. You know, like a mind-reader or something."
"What do you do when people find out that you can't read their minds?"
"I just claim that I meant that I'm part of the philosophical school which is also called 'mentalism'. And I look at them as if they were really stupid."
"Ooh, good one."
"Thanks. Anyway, speaking of air friction..."
"We were?"
"Yes: with higher speed, the air friction is higher, which increases the fuel consumption, which is bad for the environment, which is why environmentalists don't drive fast. Try to keep up."
"Right."
"So I was wondering: How much does the air friction increase with the velocity? In first approximation, it's probably a power of the velocity. So is it v, v^2, v^3, or what? If you drive twice as fast, is the air friction twice as big, four times as big, eight times as big?"
"Hm, good question. I think we can solve that with dimension analysis. The force should reasonably be directly proportional to the density of the air, and to the area of the front of the car, right? Then we'll see which power of v fits, to give the dimension of force."
"Sure, but there's a quicker way. You hit twice as many air molecules, and they travel twice as fast, so it should be at least v^2, maybe v^3, but hardly more."
"Slightly vague, but okay. How do you know which one?"
"It has to be v^3. Because v^2 is a scalar. If it was v^2, you would get the same result if the car was going backwards. Replacing v with -v, we get the same force, but it should be negated."
"Good point. But anyway, you drive too slow. Next time I want to drive."
"Then you'll have to stay sober."
"Oh."
Sture looks disappointed. They sit quietly for a while, thinking. It's hard to tell whether they're thinking about air friction or about beer.
"You know, it's probably not good for traffic safety, doing physics while driving. You know what they say, 'don't drink and derive'." says Sture.
"Yeah, but we always do that anyway, don't we? And this would just be a case of drive and derive, except you don't need derivatives to do dimension analysis, so your whole point is moo."
"You mean 'moot'?"
"No, I mean 'moo'. I mean it's really stupid, like something a cow would say."
"Or we can take the train. Trains are good." says Sture.

1. What result does the dimension analysis give?
   
2. If either of the arguments was wrong, where did it go wrong?
   
3. Bengt claims that the rotation of the Earth around its axis is completely counteracted by the rotation around the sun. Ignoring the actual speeds involved, what time of day would it have to be?
   
4. Not ignoring the speeds, is it actually possible?
   
5. If it is: How far from the equator are they? If not: How many times bigger would the planet have to be to make it possible?
   
6. If you are at the equator, how fast would you have to go to stand still in the sun's reference frame?
   

Mystery Wheels

Bengt has made a new invention. It's a randomiser.
It has a number of wheels, wheels which are partially conductive. The wheels spin, and there is a contact brushing against each wheel. All the wheels are connected in one circuit, so each wheel can either let the current pass or break the circuit. It acts as a switch, switching on and off once per turn.
Then there is a little device which sends a short electrical pulse through the circuit and registers whether it makes it through or not. There are n wheels, and the fraction of the wheel which is conductive is 1/(nth root of 2), so the probability of the pulse going through is 1/2.
The wheels all look the same, but they spin at different (constant) speeds. Bengt figures that since the ratios between the speeds are not rational numbers, the same configuration of wheels will never occur twice, making the device a really great randomiser - you will never be able to predict the result of a pulse. That's the idea, anyway.
One way to use the machine is to send pulses periodically, with a certain frequency, to get a randomised bitstring. This frequency can be assumed to be significantly lower than the rotation speed of the wheels.

1. Will you eventually be able to guess the next bit in the bitstring, that is, the outcome of the next pulse? Will you be able to guess it only with a limited degree of certainty, or will you ever be able to predict it with 100% accuracy?
   
2. If it is possible to reach enough predictability to make the randomiser unreliable - that is, the number of correct guesses become significantly larger than the number of false guesses - how does the time it takes to get there depend on the number of wheels?
   
3. How does it depend on the speed of the wheels? Will faster wheels make the randomiser better? How much better?
   
4. Is it possible to calculate an actual upper bound for how long it takes to reach predictability, as a function of the number of wheels, the upper bound of the speeds of the wheels, and the pulse frequency? If it's possible, please do.
   
5. Suppose you are capable of sending pulses at any time, as long as there is a certain minimum delay between each pulse. Sending pulses periodically with exactly that delay will give you a certain bitstring. Now, in order to predict that bitstring, is there any other pattern of pulses that would do it faster? That is, is there any pattern of pulses that would give you the information needed to predict the periodic pulses faster than the periodic pulses themselves?
   
6. Provided you have the added advantage of knowing the outcome of the previous pulses, is there any faster way of "cracking" the machine than sending pulses at a predetermined pattern? (No, you're not allowed to physically crack it open.)
   

Numbers that Grow on Trees

Bengt has come up with a whole new kind of number system, which he has decided to call "Dendriux". Each number is expressed as a full binary tree - that is, a tree diagram where each node has either two child nodes or none. It's also binary in a different sense; each node contains either a 1 or a 0.
The numerical value is calculated as follows:
- A node with a 1 has a value which is 1 less than it otherwise would be.
- A (0) node with no children has the value 2.
- A (0) node with children of value n and m has the value of the sum of the nth and the mth prime number (counting 2 as prime number number one).

1. Some numbers can be written more than one way. Find, for example, all ways of writing 10, 11 and 12.
   
2. Suppose that f(x) is the number of ways in which the number x can be written. Find the asymptotic upper bound (the "ordo") for f(x).
   
3. (hard) Is it really possible to write all positive integers this way? Prove it.
   

Nightly Tag

Alban is visiting Bengt, and after some drinking they start getting childish and decide to play tag. Bengt is surprisingly fast for his size; more specifically, he is k times faster than Alban. They are both moving at constant speed.
Bengt is chasing Alban, and they are a distance d apart. Then suddenly the sun sets, and Bengt can no longer see more than 1 m ahead.

1. Suppose Alban is performing a brownian motion. What curve should Bengt follow in order to catch him as quickly as possible?
   
2. For which values of k and d is it likely that Bengt will catch Alban?
   
3. Now suppose Alban can follow any curve. What curve should Bengt follow to be sure of catching him?
   
4. For which values of k and d can Bengt be sure of catching him?
   
5. Eventually they get tired of the game. They lie down it the grass and start idly chatting about spaceships.
   Repeat all the above questions, but now assuming that Bengt and Alban are in space; that is, they move in three dimensions rather than two, they have a constant (magnitude of) acceleration instead of constant speed, with Bengt accelerating k times faster than Alban, and their initial relative speed is s.
   

More Solid Geometry and Booze

Bengt is having a birthday party and wants to offer his guests something really special. He discusses with Sture what kind of drink you could give the guests to impress everyone.
"It has to be something that no one has experienced before." says Bengt. "Were you at Percy's party last week?"
"No, what drink did he have?" asks Sture.
"A 'Bloody Mormon'; one part vodka, one part juniper berry and one part meerkat blood."
"That's not very imaginative. I had one of those the already in 1963."
"But hey, Gilbert had a really interesting drink at his party last year. A saturated solution of salmiac (NH4Cl) in water, served in half-spherical glasses with radius 5 cm."
"Yeah, it had quite a bite. That won't be easy to beat."
"Ah, don't worry. You don't play in the top league unless you're good. I think I have an idea, actually. What are the two most important properties of a good drink?"
"Strong and cold."
"Exactly. So how does this sound: More than a hundred percent alcohol, and a serving temperature of minus 104 degrees?
"That sounds absolutely marvellous."
"I was planning to use some rather special cups to measure the drinks. I have ten canisters, shaped as each of the platonic bodies, five with the side one dm and five with the side √10 dm. The thickness of the walls of the canisters is negligible. So you use them to measure the drinks, and then you pour them in big glasses."
"And then you pour them in your own non-platonic body."
"Exactly."

1. Bengt would like to be able to measure 1, 1/2, 1/3, 1/4 and 1/5 liters, using only completely filled canisters. Is it possible? Which ones are possible?
   
2. Unfortunately Gilbert had a marble floor at his party. If anyone spilled a drink, what volume of the floor was dissolved? (Assume that the glass was completely filled.)
   
3. Bengt would like to have very long straws to the drinks. How long straws is it theoretically possible to have? (Assume that the drink has the same density as water, and that the drink is on Earth, and that the straws are pointing straight up.)
   
4. Actually, the density of this particular drink is 568 kg/m^3. So how long can the straws be?
   
5. The drink which Bengt has been planning consists of liquid ethene, which reacts with water in the stomach to form ethanol. What volume percentage of ethanol does this drink correspond to?
   

Darts

Bengt and Sture are in the pub. They are drinking beer, obviously, and also playing darts. Bengt has invented a new kind of darts game. It is best played on a different kind of board, but in the pub they have to make do with the normal one.
The game goes like this: First Bengt throws three darts, hitting a certain combination of fields. Then Sture throws three darts, trying to copy Bengt's throw by hitting the same fields (in any order). If he succeeds, the round is over and no one gets any points. If he fails, Bengt gets to try to copy his own combination. If he succeeds in the first attempt, he gets three points. If he fails, he gets a second attempt; if that succeeds, he gets two points, otherwise he gets no points. Then the round is over. In the next round Sture starts by setting the combination, and then they alternate like that until they have played an even number of rounds and someone has achieved a previously agreed upon score.
(There is also a rule that you are not allowed to use the same combination twice, but that has no impact on this question.)

What makes this game different from other darts games is that you not only need to have good throwing skills, but you also need to be able to assess your throwing skills well. If you start by throwing a really easy combination, the opponent will almost certainly copy it in his only attempt, and if you start with a really difficult combination, you are very unlikely to be able to copy it even in two attempts. So the trick is to know the probability that you will be able to pull off a certain combination, and then to choose a combination that will have the right probability.

1. Which probability would be the best to have in your first throw? Assume that both players have the same skill level (and that it remains constant, despite the beer).
   In other words: Provided you have already done a first throw (of three darts), and it is such that each of the following throws has a probability p to copy it, what would you want p to be?
   
2. When you make your first throw, what probability should you aim for? Assume that if you miss the intended target with any of the darts on your first throw, you will not get any points (because you will hit something that is either too hard or too easy to copy).
   
3. What if you make a slightly more complicated assumption - if you miss with a dart, that dart will hit something that is trivial to copy (such as the wall), but you can still hope to make it a challenging throw by hitting something with the other darts. Which probabilities should you aim for with each of the three darts? (It may depend on whether you hit with the previous darts, so there are seven cases in total.)
   

The Paper Dragon

Bengt has a long strip of paper. He puts it on the table, and folds it in half. He lifts up the right hand end, folds it over and puts it on the left hand end. Then he repeats that same procedure several times. When he unfolds the paper, it has a funny curly pattern, which supposedly looks like a dragon. But Bengt is a true scientist and is not content to note that the pattern looks nice. He wants a formula.
If you call a fold in one direction 0 and in the other direction 1, the result is
0010011000110110001001110011011...

1. Find a way to reproduce the sequence mathematically.
   
2. Find a recursive formula that describes it, that is, the folding direction as a function of the direction of one or more previous folds.
   
3. Find a non-recursive formula, that is, the folding direction as a function of only the number of fold.
   

Fireworks

It's New Year's Eve, and Bengt is setting up the fireworks. Usually he's not much for safety regulations, but this day he has all of a sudden decided to be really paranoid about safety. He wants to make absolutely sure no one can be hit by a rocket.
He knows that the rocket burns for a time t, and that it is supposed to reach a height h. But that's assuming that it moves straight upward.
While it burns, the acceleration has a constant size, and after that the rocket is only affected by gravity.
Naturally, Bengt would like to know how far the rocket might reach if it is fired at an angle.

1. Assuming that the rocket doesn't turn, and that there is no air friction, can we safely assume (for the purpose of these calculations) that the rocket has constant mass?
   
2. Come to think of it - assuming that there is no air friction, can we safely assume (for the purpose of these calculations) that the rocket doesn't turn?
   
3. Come to think of it - can we safely assume (for the purpose of these calculations) that there is no air friction? Remember we're trying to determine an upper bound for the distance, so we just want to know if there is any way the rocket could get a longer range due to air friction.
   
4. Assuming all those things, how far could the rocket reach?
   
5. Sture leeringly remarks that Bengt probably has no interest in safety, that he just wants to know how many of his neighbours' houses he could bomb. Naturally we trust Bengt, but if he was trying to reach as far as possible - would it help to attach several rockets to each other? If he uses a bunch of n rockets all attached to each other, how far will the bunch go?
   
6. What if he could change the time the rocket burns? Assume that the rocket gets the same amount of work done on it by the burning. How long should it ideally burn, in order to fly as far as possible?
   
7. And how far would that be?
   
8. If the rocket burns for b times longer, still with the same amount of work, how far will it go?
   

Christmas Equation

It's Christmas Eve, and Bengt is celebrating by dancing around a new equation. It looks like this:
√(x²+y²)=5-z+f(z)-√(5z)
where f the floor function, that is, f(z) is z rounded down to the nearest integer.

What is this the equation for?

Running Aliens

Above Bengt's house floats a spaceship. It's big and round - basically what you would call a "flying saucer". It is held up by a force which exactly matches that of gravity, so that the spaceship stays hovering at the same height.
In the ship is a little green alien, who likes to get his exercise in the morning by running around the perimeter of the spaceship. Around and around in a circle, at an amazing speed. To avoid the spaceship starting to turn the other way, he has an identical friend alien who runs the other way. The other alien thinks this is a bit of a drag, but he still has the same physical properties.
The aliens are running so fast that you have to use relativistic equations to calculate their momentum. There are two ways of doing that; either it's m * v / gamma, or you use speed-dependent mass, which makes it m * v. Either way, the alien can never reach the speed of light, which is all good and well.
But if you use speed-dependent mass, the alien will get heavier. That means gravity on the spaceship as a whole increases, and it falls down. On the other hand, if you don't use speed-dependent mass, he doesn't get heavier, so it doesn't fall down.

Which is it? Does the spaceship fall down, or not?

A Big Cube and a Little Cube

On his desk, Bengt has two cubes. The small cube has the side 2 dm, and the big cube has the side 1 dm. The reason why the 1 dm cube is "big" is that Bengt claims it has more than three dimensions. Now Bengt wants to place the small cube inside the little cube. (The thickness of the walls of the cubes are negligible, so that for example if you had two identical cubes you could place one inside the other.)

1. How many dimensions must the big cube have for the little cube to fit inside it?
   
2. What if they were spheres instead of cubes?
   

A Slowly Growing Number Sequence

Bengt has found a number sequence. It starts like this:
1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 10, 2, 4, 2, 12, 12, 4, 2, 4, 6, 2, 10, 6, 6, 6, 2, 6, 4, 2, 10, 14, 4, 2, 4, 14, 6, 10, 2, 4, 6, 8, 6, 6, 4, 6, 8, 4, 8, 10, 2, 10, 2, 6, 4, 6, 8, 4, 2, 4, 12, 8, 4, 8, 4, 6, 12, 2, 18, 6, 10, 6, 6, 2, 6, 10, 6, 6, 2, 6, 6, 4, 2, 12, 10, 2, 4, 6, 6, 2, 12, 4, 6, 8, 10, 8, 10, 8, 6, 6, 4, 8, 6, 4, 8, 4, 14, 10, 12, 2, 10, 2, 4, 2, 10, 14, 4, 2, 4, 14, 4, 2, 4, 20, 4, 8, 10, 8, 4, 6, 6, 14, 4, 6, 6, 8, 6, 12, 4, 6, 2, 10, 2, 6, 10, 2, 10, 2, 6, 18, 4, 2, 4, 6, 6, 8, 6, 6, 22, 2, 10, 8, 10, 6, 6, 8, 12, 4, 6, 6, 2, 6, 12, 10, 18, 2, 4, 6, 2, 6, 4, 2, 4, 12, 2, 6, 34, 6, 6, 8, 18, 10, 14, 4, 2, 4, 6, 8, 4, 2, 6, 12, 10, 2, 4, 2, 4, 6, 12, 12, 8, 12, 6, 4, 6, 8, 4, 8, 4, 14, 4, 6, 2, 4, 6, 2, 6, 10, 20, 6, 4, 2, 24, 4, 2, 10, 12, 2, 10, 8, 6, 6, 6, 18, 6, 4, 2, 12, 10, 12, 8, 16, 14, 6, 4, 2, 4, 2, 10, 12, 6, 6, 18, 2, 16, 2, 22, 6, 8, 6, 4, 2, 4, 8, 6, 10, 2, 10, 14, 10, 6, 12, 2, 4, 2, 10, 12, 2, 16, 2, 6, 4, 2, 10, 8, 18, 24, 4, 6, 8, 16, 2, 4, 8, 16, 2, 4, 8, 6, 6, 4, 12, 2, 22, 6, 2, 6, 4, 6, 14, 6, 4, 2, 6, 4, 6, 12, 6, 6, 14, 4, 6, 12, 8, 6, 4, 26, 18, 10, 8, 4, 6, 2, 6, 22, 12, 2, 16, 8, 4, 12, 14, 10, 2, 4, 8, 6, 6, 4, 2, 4, 6, 8, 4, 2, 6, 10, 2, 10, 8, 4, 14, 10, 12, 2, 6, 4, 2, 16, 14, 4, 6, 8, 6, 4, 18, 8, 10, 6, 6, 8, 10, 12, 14, 4, 6, 6, 2, 28, 2, 10, 8, 4, 14, 4, 8, 12, 6, 12, 4, 6, 20, 10, 2, 16, 26, 4, 2, 12, 6, 4, 12, 6, 8, 4, 8, 22, 2, 4, 2, 12, 28, 2, 6, 6, 6, 4, 6, 2, 12, 4, 12, 2, 10, 2, 16, 2, 16, 6, 20, 16, 8, 4, 2, 4, 2, 22, 8, 12, 6, 10, 2, 4, 6, 2, 6, 10, 2, 12, 10, 2, 10, 14, 6, 4, 6, 8, 6, 6, 16, 12, 2, 4, 14, 6, 4, 8, 10, 8, 6, 6, 22, 6, 2, 10, 14, 4, 6, 18, 2, 10, 14, 4, 2, 10, 14, 4, 8, 18, 4, 6, 2, 4, 6, 2, 12, 4, 20, 22, 12, 2, 4, 6, 6, 2, 6, 22, 2, 6, 16, 6, 12, 2, 6, 12, 16, 2, 4, 6, 14, 4, 2, 18, 24, 10, 6, 2, 10, 2, 10, 2, 10, 6, 2, 10, 2, 10, 6, 8, 30, 10, 2, 10, 8, 6, 10, 18, 6, 12, 12, 2, 18, 6, 4, 6, 6, 18, 2, 10, 14, 6, 4, 2, 4, 24, 2, 12, 6, 16, 8, 6, 6, 18, 16, 2, 4, 6, 2, 6, 6, 10, 6, 12, 12, 18, 2, 6, 4, 18, 8, 24, 4, 2, 4, 6, 2, 12, 4, 14, 30, 10, 6, 12, 14, 6, 10, 12, 2, 4, 6, 8, 6, 10, 2, 4, 14, 6, 6, 4, 6, 2, 10, 2, 16, 12, 8, 18, 4, 6, 12, 2, 6, 6, 6, 28, 6, 14, 4, 8, 10, 8, 12, 18, 4, 2, 4, 24, 12, 6, 2, 16, 6, 6, 14, 10, 14, 4, 30, 6, 6, 6, 8, 6, 4, 2, 12, 6, 4, 2, 6, 22, 6, 2, 4, 18, 2, 4, 12, 2, 6, 4, 26, 6, 6, 4, 8, 10, 32, 16, 2, 6, 4, 2, 4, 2, 10, 14, 6, 4, 8, 10, 6, 20, 4, 2, 6, 30, 4, 8, 10, 6, 6, 8, 6, 12, 4, 6, 2, 6, 4, 6, 2, 10, 2, 16, 6, 20, 4, 12, 14, 28, 6, 20, 4, 18, 8, 6, 4, 6, 14, 6, 6, 10, 2, 10, 12, 8, 10, 2, 10, 8, 12, 10, 24, 2, 4, 8, 6, 4, 8, 18, 10, 6, 6, 2, 6, 10, 12, 2, 10, 6, 6, 6, 8, 6, 10, 6, 2, 6, 6, 6, 10, 8, 24, 6, 22, 2, 18, 4, 8, 10, 30, 8, 18, 4, 2, 10, 6, 2, 6, 4, 18, 8, 12, 18, 16, 6, 2, 12, 6, 10, 2, 10, 2, 6, 10, 14, 4, 24, 2, 16, 2, 10, 2, 10, 20, 4, 2, 4, 8, 16, 6, 6, 2, 12, 16, 8, 4, 6, 30, 2, 10, 2, 6, 4, 6, 6, 8, 6, 4, 12, 6, 8, 12, 4, 14, 12, 10, 24, 6, 12, 6, 2, 22, 8, 18, 10, 6, 14, 4, 2, 6, 10, 8, 6, 4, 6, 30, 14, 10, 2, 12, 10, 2, 16, 2, 18, 24, 18, 6, 16, 18, 6, 2, 18, 4, 6, 2, 10, 8, 10, 6, 6, 8, 4, 6, 2, 10, 2, 12, 4, 6, 6, 2, 12, 4, 14, 18, 4, 6, 20, 4, 8, 6, 4, 8, 4, 14, 6, 4, 14, 12, 4, 2, 30, 4, 24, 6, 6, 12, 12, 14, 6, 4, 2, 4, 18, 6, 12, 8...

1. What is this number sequence?
   
2. Will it contain arbitrarily large numbers? Prove it.
   
3. Of the 1000 numbers shown here, the biggest number is 34, and it appears quite early. Is there any particular reason for that?
   
4. Why does the sequence 6, 6, 6 appear in so many places? Does it have something to do with the devil?
   
5. Will any other number ever appear three times in a row? Prove it.
   
6. If you have plenty of spare time: Find the next number in the sequence.
   
7. (hard) Near the beginning, there are a lot of twos. Will they eventually run out, or is there an infinite number of them?

Technology Logo

Bengt's friend Alban has started studying at LTH, the Faculty of Engineering at Lund University. He therefore has a sweater with the logo of the student union, TLTH (http://www.tlth.lth.se/). It consists of a square inside an equilateral triangle inside a circle.
Bengt is thinking about whether this is the optimal way to pack these shapes.

1. If the circle has the area 1, what area does the square have? (It is as big as possible.)
   
2. If the shapes contain each other in a different order, one might get a different ratio between the outermost and the innermost. If the outermost shape always has area 1, in which order should they be placed to make the innermost as big as possible, and how big will it be?
   
3. What if they are in three dimensions? A sphere, a regular tetrahedron, and a cube, with the outermost having volume 1 - how big will the innermost be?
   
4. While you're at it: n dimensions?

A Different Kind of Relativity

Bengt is sitting in his hammock, thinking. The hammock is doing a pendulum motion, but that has nothing to do with this problem.
"In classical physics," Bengt thinks, "momentum is always mass times velocity, m * v. In relativistic physics, momentum is usually taken to be m * v / gamma. But if you really want, you can decide that it is m * v after all, and use speed-dependent mass. And since the earth is moving, it gets a higher mass."

1. Assuming that the earth is spinning, but that its centre of mass is at rest, how much does its relativistic mass increase compared to if it was standing still?
   
2. If the earth is also spinning around the sun, how much does that increase its mass?
   
3. Bengt's (rest) mass is 100 kg. If the mass of the earth increases, gravity should get stronger. Also, Bengt moves along with the earth, so his mass should increase too. If Bengt is at the equator, and the earth moves as in b), how much weight does he gain?
   
4. The rotation of the earth also leads to a centrifugal force, so that Bengt seems to get lighter instead. If Bengt is at the equator, how much is his apparent weight loss?
   
5. The rotation of the earth has some other consequences. Normally, the circumference of a circle (or a sphere, in this case) is pi * D, where D is the diameter. But if you try to measure the equator, it is because of length contraction not quite pi * D. But again, if you really want, you can decide that it is pi * D after all, and use speed-dependent pi. In that case, how much does pi change when you measure the equator?
   

Equation with Three Unknowns and One Well Known

Bengt is sitting in the town square eating ice cream. He looks like he is deep in thought. Sture walks by and comes up to him.
"Hi there, Bengt! What are you thinking?" asks Sture.
"Oh, hi. Well, I was just thinking, if x^2 + y^2 + z^2 + 1 = x + (2y + √(23)z) / 3, what is then x, y and z / √(23)? All the numbers are real."
"But that's impossible to solve, isn't it? It's three unknowns but only one equation."
"I'm sure you can do it. You're good with numbers."

Is it possible to solve? What is the answer?

A Different Kind of Boat

Bengt has a thick metal sheet. It is in the shape of a hexagon with the side 1 m. Now he wants to make it float. Here's his idea:
He will drill a lot of holes in the sheet. Then he will put a very thin metal sheet on each side, so that the air can't escape.
He has drill bits in all sizes. The holes can be infinitely close, but must not overlap. The volume of the thin sheets can be neglected.

1. If he chooses the best possible size of the bit (but only one size), which fraction of the mass of the sheet will remain?
   
2. What if he chooses the worst possible?
   
3. What if he uses the best possible combination of two sizes?
   
4. What if he uses the best possible combination of n sizes?
   
5. How many sizes would he need to make the plan work (get the boat to float on water) if the sheet is made of iron? How about lead? Aluminium?
   

The Great Clock

Bengt has a big clock on his wall. It's an old mechanical clock, powered by a spring. The spring keeps a pendulum wheel in motion. The pendulum wheel is spinning back and forth. The torque on the wheel from the spring is constant in magnitude but with alternating direction.
The wheel, which is made of copper, 1 mm thick, and with 1 dm circumference, moves a quarter of a turn from its equilibrium position in each direction. Each time it reaches one side (but not when it reaches the other) a big gear moves one step. On the same axis as this gear is small gear, which meshes with an identical big gear, moving it ahead one step for every turn of the small gear. This second big gear moves the second hand on the clock, moving with the same angular velocity as it. On the same axis as this second big gear is another small gear, which similarly meshes with a gear for the minute hand. And so on.
Apart from the normal hands, this clock also has a hand which completes a turn in one year. It is one meter long.
"Suppose that the gears and the hands have no mass." thinks Bengt. "And suppose that the clock won't break if I hang in it." So he does.
Bengt jumps up and grabs a hold of the tip of the year hand. It is autumn, so it is pointing to the left, moving upwards.

1. How big is the torque on the pendulum wheel from the spring?
   
2. Even though Bengt hangs in the year hand, the clock doesn't stop. How heavy would he have to be to stop the clock?
   
3. Bengt's mass is 100 kg. How much behind would the clock be if he hangs there for 24 hours?
   
4. "When spring comes," thinks Bengt, "I'm going to hang in the year hand again, to see if I can make it go twice as fast." How heavy would Bengt have to be to succeed in this?
   

Espresso Numbers

"The real numbers are not a countable set." says Alban.
"Oh really?" says Bengt, in a somewhat disdainful tone.
"Really."
"So, if I give you a countable set, you can tell me a real number which is not in my set?"
"Yes... I suppose."
"Bet you a beer you can't."
"You're on."
"Okay, listen to this: There is a set S, which contains all the symbols valid for expressing a number. Digits, decimal points, fraction signs, and so on. You can throw in some arithmetic symbols too if you like. The point is, it's a finite number of symbols."
"Uh-huh."
"With those, you can put together expressions of finite length. There is clearly a countable set of such expressions. Now, we define the set U, which is the set of all numbers that can be defined using such expressions. We can call them the expressible numbers."
"Or we can call them the espresso numbers. Because I like espresso."
"No. First, that doesn't sound mathematical. Second, I don't like espresso."
"Oh."
"So, there you go. Find me a real number that is not expressible."
Alban thinks for a while.
"Umm... pi?"
"Well... I could say that the pi symbol is in S, but that would be no fun. Or I could bring up Lebniz' and Gregory's formula. But that's not necessary. Because if pi is not in S, you have to use some other way to express the number you mean. Can you explain what pi is?"
"Hmm. I guess that should be possible somehow... but we know it's irrational, so it has an infinite non-repeating sequence of digits."
"But so does the square root of two. And that's obviously expressible."
"Damn you and your strange problems."
"Yeah yeah. Sore loser."

Is there any such number? Since it's well known that the set of real numbers is not countable, there must be some flaw in Bengt's argument - what is it?