Maths

From Graham, Knuth and Patashnik, "Concrete Mathematics" (2nd Ed.), page 17:

Some of the regions defined by n lines in the plane are infinite, while others are bounded. What's the maximum possible number of bounded regions?

I counted things I thought may be relevant for the first few cases and put them in a table:

Lines	Vertices	Angles	Line Sections	Regions	Bounded Regions
3	3	12	9	7	1
4	6	24	16	11	3
5	10	40	25	16	6

(I did not think the cases Lines=1,2 were interesting).

Number of Regions is from a formula from the same book on page 7.

I am assuming we can place the Lines such that any new Vertex does not coincide with another Vertex.

Lines are cut into "Line Sections" by Vertices.

It occurs to me that every Line has two Line Sections which touch only one Vertex, the Line Sections which start at one Vertex and continue "into infinity". These cannot form part of a Bounded Region. Each of these Line Sections touches two Regions, but shares each Region with one other single-Vertex Line Section.

Therefore, the minimum number of non-Bounded Regions is twice the number of Lines, and the upper-bound on the number of Bounded Regions is this number subtracted from the total number of Regions.

In fact, because all the remaining Regions do not touch a single-Vertex Line Section they must all be Bounded.

If n is the number of Lines, the final formula is:

(n * (n + 1) / 2) + 1 - (2 * n)

Where the first part of the formula is the total number of Regions, from page 7 of the book.

Other possibilities: put this in terms of graph theory using isomorphism.

Inspired by http://phrogz.net/lazy-cartesian-product.

An algorithm implemented in Lua which can, for any list of sets and index i, can return the ith element of the cartesian product of the sets, without calculating any of the other elements of the cartesian product.

The idea goes something like this. Given a set s on its own, to find the ith element of the cartesian product of s you just return the ith element of s.

Say you have a cartesian product X from which you can get the ith element.

If you have a set s, you can return any of the elements of the cartesian product formed of s and the sets which formed X by assigning to each number between 0 and | s | * | X | - 1 (our sets and cartesian products must be zero-indexed) a unique combination of s and X.

Given an i, choose the element of s equal to the remainder of i divided by | s |. This will be between 0 and | s | - 1. We choose the element of X equal to the dividend (which we know how to get).

When i is 0, the first element of s is combined with the first element of X. When i is 1, the second element of s is combined with the first of X, and so on. When i is equal to | s |, the first element of s is combined with the second element of X, and so on.

No pair of dividend and remainder will appear more than once and, once i is equal to | s | * | X | - 1, each pair of dividend and remainder will have appeared.

Therefore, each element of s will be assigned to each element of X.

Lua

My solution to the puzzle:

• You are imprisoned in a pitch black, mostly featureless phonebox with a solid roof and floor
• There are four walls, with a waist-height hole in each with a button at the back; walls, holes and buttons are identical
• Each button starts randomly in one of two states and can be toggled by pressing the button; you do not know nor are you able to determine a button's state
• As an "action" you may insert your arm(s) into any of the holes and (simultaneously) press the button(s), then remove your arm(s)
• If all the buttons are now all in the same state, you escape
• If not, the phonebox spins around, eventually stopping but leaving you disorientated and with no indication as to which button(s) you just pressed
• There are no trick solutions accepted for the puzzle e.g. you can't mark walls, use your feet, etc.
• Can you guarantee your escape?

I think you can get away with just pressing buttons randomly, here's why:

PDF | HTML | Org | Source tarball

My solution to the second problem from the excellent https://projecteuler.net/

PDF | HTML | Org | Scheme code

This is my attempt to solve a problem set for me by James Bach in the style of conjectures and refutations as described by Popper and Lakatos.

PDF | Org | R code for solution | R code for checking