up vote 36 down vote favorite
13

On an internal wiki at work, people sometime post puzzles similar to those found on this website. Most of the questions are formulated as a story or word problems, but can be expressed mathematically and become simple to solve.

I had an idea for a joke, to create a problems which when expressed mathematically is actually an unsolved problems in maths. One idea I had was:

You are a prisoner sentenced to death. You are told by the warden that you can choose any room you would like, and prisoners are moved each day with the prisoner in room 1 being executed, which is the lowest room number. Prisoners in even number rooms are moved to room n/2 and prisoners in odd number rooms are moved to room 3n + 1. To avoid execution you can choose a room which will mean you never get to room 1, or you can prove that no such room exists and be freed.

If you are familiar with number theory, you might reconize that this is actually the Collatz Conjecture.

Does anyone know of any other maths puzzles that are actually unsolved problems (or have any comments on this one)?

share|improve this question
  • 3
    Are there rooms with negative numbers (not explicitly defined here!)? Any negative integer would be a solution, given that it would loop from -1 to -2 once reached and 3n + 1 being the only way to move it from being negative to non-negative. Anyway, this concept sounds interesting, but as far as I can remember such types of problems (in informatics) usually have examples, which are often expressed as something concrete. You could consider that vaguely puzzles. – Battle Aug 21 at 9:34
  • 1
    Good point, I need to specify that the room numbers are positive. – MikeS159 Aug 21 at 9:38
  • 4
    It won't help you get out, but selecting room 2^36500 would ensure you won't get executed for another 100 years :) (It would be a long walk down the hall, though) – jafe Aug 21 at 9:49
  • 1
    The Collatz Conjecture: the simplest mathematical problem to understand, yet one of the hardest to prove :D – user477343 Aug 21 at 11:12
  • 2
    @IanMacDonald I need to word it better to make it fit the conjecture. – MikeS159 Aug 21 at 22:03

10 Answers 10

up vote 29 down vote

I'm not sure if this is the kind of thing you are looking for but this might be an example

Puzzle
You die and the devil says he'll let you go to heaven if you beat him in a game. He gives you a very large flat sheet of paper and a pen and asks you to draw a closed loop, of any shape, which does not intersect itself. He will then look at the curve and try to find four points on it which are the vertices of a square. If he finds a square he wins, otherwise you win. How should you draw your curve to beat the devil?

You are not allowed to fold or otherwise alter the shape of the paper. You may assume the devil is an excellent opponent - if there is a square to find, he will find it.

Related unsolved problem

This is known as the Inscribed Square Problem. Similar to the Collatz Conjecture, it is not known if a solution exists but, in certain cases - for example, if the curve is convex or piecewise smooth - it is known that you can always find a square.

It depends how well-informed your work colleagues are but I suspect that a person who did not know about this conjecture could spend hours trying to draw a really weird curve that works. In that way, it is particularly devious and you may lose some friends.

share|improve this answer
  • 4
    This is exactly the sort of thing! Thanks I had this idea when I read about the 15 puzzle, where 14 and 15 are flipped, which is impossible to solve. – MikeS159 Aug 21 at 11:07
  • 12
    Can you draw a curve on paper that isn't piecewise smooth? – Christopher Aug 21 at 13:22
  • 3
    Tell a Math Daemon to draw it according to your description :) Bonus points for a Daemon in computing being an agent that independently performs a task in the background. – Ruadhan2300 Aug 21 at 14:24
  • 9
    @Ruadhan2300: a Math Daemon — is that something to do with the Bourne identity? – Peter LeFanu Lumsdaine Aug 21 at 18:10
  • 2
    Doesn't this kind of problem trigger the win condition if your closed loop is a function that creates just one solution of a single set of XY coordinates and delivers an out of bounds for any other? Because the very definition of the other object is to contain non-identical points while your loop contains exactly one point. – Trish Aug 21 at 19:53
up vote 24 down vote

Acquaintances and strangers:

How many people must there be at a party, such that there is either a group of 5 people, all of whom already know all of the others in the group of 5, or a group of 5 people, none of whom already know any of the others in the group of 5?

Related unsolved problem:

This is the Ramsey number R(5, 5). All we know is that $43 \leq R(5, 5) \leq 48$.

share|improve this answer
  • It seems deceptively simple. Do you know of a source that explains a little bit of the computational difficulty? – hkBst Aug 21 at 15:08
  • +1 This is a good one. – hexomino Aug 21 at 15:10
  • @hkBst math.stackexchange.com/questions/867470/… – Christopher Aug 21 at 15:15
  • @hkBst The difficulty is that the most obvious computational check would be to take every possible pattern of $n$ people knowing/not knowing each other for $n\in\{43, \dots, 48\}$ and check whether it has the required structure. But there are $2^{n(n-1)/2}$ possible patterns for each $n$, which is an infeasibly big number, even if you're a little smarter and factor in permutations of the people. – David Richerby Aug 22 at 12:37
  • @DavidRicherby You wouldn't have to take every n, just go until one doesn't work. – Acccumulation Aug 22 at 21:43
up vote 14 down vote

I decided to rephrase Christopher's answer to make it sound less "mathematical" and more "puzzle-like".

Same exact puzzle, same exact open problem.

I'm throwing a party! But how many people can I invite?

All of the people I'm planning on inviting are currently strangers to each other. However, I can introduce people to each other before the party. (And they're rather lazy and introverted, so they're never going to bother introducing themselves to each other.) This means that by the time the party comes around, I can control exactly which pairs of people are friends, and which pairs are strangers to each other.

But there's a potential problem. If I invite too many people, it will certainly result in disaster!

You see, if there are any 5 people at the party who all know each other, then they will leave and start their own party. I can't let that happen!

Likewise, if there are any 5 people at the party who are all strangers to each other, then those people will all feel isolated and go home. I can't let that happen, either.

What's the greatest number of people I can possibly invite to the party without either of these two disasters occurring?

share|improve this answer
  • 2
    I like it, trying to make sound less mathematical is great! – MikeS159 Aug 22 at 7:25
up vote 6 down vote

Candles at the Church

You go to church every Sunday. Everyone who enters must light up a candle, say a prayer, and then place the candle in a container filled with sand. When nobody watches, you try to sort the candles in $m$ rows of $n$ ($m,n>1$) to make a quadrilateral shape${}^1$.

One day, you enter the church and sort $a$ placed candles in a quadrilateral shape. An old lady then says a prayer and places a candle in the sand container, adding to the total. Now, there are $a+1$ candles. No matter how much you try, you cannot make a quadrilateral with this number of candles. Once church is over, two candles have melted. There now remain $a-1$ candles. You try to sort the number of candles in a quadrilateral shape, but again you do not succeed.

You then wonder: does there always exist a number $b>a$ that would lead to the consequence of not being able to sort $b\pm 1$ candles into quadrilaterals?

${}^1$i.e. a parallelogram, credit to @wizzwizz4 for pointing that out.

Related unsolved problem:

The Twin Prime Conjecture, seldom known as Polignac's Conjecture.

share|improve this answer
  • 2
    I think you need to precise m,n>1 – Evargalo Aug 21 at 14:44
  • @Evargalo oh yes, will do. Thanks for that :) – user477343 Aug 21 at 21:37
  • 2
    Do you mean a rectangle shape? – wizzwizz4 Aug 22 at 18:13
  • 1
    @user477343 Rhombus kite trapezium etc. are quadrilaterals and not rectangles. – wizzwizz4 Aug 22 at 21:50
  • 1
    The trapeziums don't work like that, though; they don't have that area. And though it's a trivial modification, the visual layout is different. Quadrilateral is probably not the word you were looking for. – wizzwizz4 Aug 22 at 21:56
up vote 4 down vote

The Problem of the Four Elementals

There are lots of each type of elemental - Fire, Air, Earth and Water - all gathered together. Each type of elemental detests elementals of the same type.

Your mission is to design a network of corridors in FlatLand, with rooms wherever corridors intersect, and exactly one elemental per room, such that the elementals CANNOT live in without fighting, which happens if they live in adjacent rooms.

a.k.a.

the four colour theorem

share|improve this answer
  • Is this not possible though? – MikeS159 Aug 21 at 11:48
  • @MikeS159; no-one's found a simple proof yet, and the suggested proofs are still being debated : nrich.maths.org/6291 (last chapter) – JonMark Perry Aug 21 at 11:54
  • 2
    I was ready to disagree, then I noticed the word "simple" – George Menoutis Aug 21 at 13:42
  • 1
    The boundary conditions are not very clear. For example, you can just stick each elemental in its own circular corridor, with a self intersection if a room is required for its comfort. Presumably then they do not need to fight, although the conditions for when they would fight are similarly absent. – hkBst Aug 21 at 15:15
  • 2
    A network they cannot live in would be one of those rooms made from a self intersecting corridor (instead of one per elemental, just stick all of them in one). Such a room would be self adjacent (just follow the corridor), so they would fight. – hkBst Aug 21 at 15:41
up vote 4 down vote

Puzzle:

List the integers from 1 to 15 so that the sum of any two adjacent integers is a perfect square. For example, 1, 3, 13, 12, etc. 1+3=4, a square. 3+13=16, a square, etc. If you find a way to do that, do the same for the integers from 1 to 14.

Math connection:

The puzzle is equivalent to finding a Hamiltonian path in a graph with n vertices, labeled 1 through n, in which two vertices are joined by an edge only if the sum of their labels is a square. Such a path exists for such graphs of 15, 16, 17 or 23 vertices. No such path exists for any other such graphs with fewer than 25 vertices. It is conjectured that a path exists for all such graphs with more than 24 vertices.

share|improve this answer
  • 1
    This one's just a trick question, not actually an unsolved problem. Also, it's quite easy to do 1-15 by hand (9-7-2-14-11-5-4-12-13-3-6-10-15-1-8), and in the process of solving that it's easy to see why 14 doesn't work. Although, ... duuuuude look at the sums! 16,9,16,25,16,9,16,25,16,9,16,25,16,9 – Rob Watts Aug 22 at 21:16
  • This is known as the Square-Sum Problem which already has a solution... but still very interesting, so $(+1)$ :D – user477343 Aug 22 at 23:50
  • I thought it was fair game, because other puzzles in this thread are based on solved problems that had been unsolved for a long time. I chose n = 15 and 14 because actually finding a Hamiltonian path gets very hard for large values of n. I think a puzzle should be solvable by a human being unless the puzzle is specifically intended to be solved via computer. In the latter case, the real puzzle is to create an algorithm and implement it. I reserve committing myself as to whether or not the square sum problem has been solved. – Steve B Aug 23 at 1:59
up vote 2 down vote

I think every conjecture can be formulated to puzzle. Erdős formulated something like

An evil one will destroy humans if they would not find the Ramsey numbers R(5,5) and R(6,6). What should one answer?

In a similar way, you can replace determining the Ramsey numbers by your favorite conjecture.

share|improve this answer
  • 1
    Welcome to Puzzling.SE! If possible, try to use the spoiler markup >!. – u_ndefined Aug 22 at 14:09
  • 7
    I think the idea is that the unsolved problem be obfuscated such that even someone familiar with the problem might not recognise the puzzle for what it is. – EightAndAHalfTails Aug 22 at 14:09
up vote 1 down vote

If you want to be devious, you could ask something like the following:

My uncle wants to take a group picture of me and my 15 cousins. He likes a good and colorful picture, so he has given us all hats in one of four colors (e.g. red, yellow, green, blue) and shirts of one of four different colors. Since he's a little forgetful, I and my cousins made sure that everyone is wearing a unique combination of shirt and hat color.

For the picture, my uncle would like to arrange us in a 4x4 grid so that nobody in the same row or the same column has the same hat color or the same shirt color. How can this be done?

Now suppose that I had 35 cousins, and there were six colors of hats and shirts. How could my uncle arrange us all into a 6x6 grid so that nobody in the same row or column shared the same hat or shirt color?

This is the problem of

Graeco-Latin squares. It's perfectly possible to do this for the 4x4 case, but the 6x6 case is impossible.

share|improve this answer
  • 3
    This is not an unsolved problem, merely an impossible one. – Jaap Scherphuis Aug 22 at 19:56
  • What would be the problem of just assigning everyone the color corresponding with their matrix coordinates? – hkBst Aug 23 at 8:25
  • @hkBst: Then all the people in a given row would have the shirt of the same color, not different colors. Same with the columns. – Michael Seifert Aug 23 at 13:13
  • Ah okay, no two people in the same row or column can have the same hat color or the same shirt color. – hkBst Aug 23 at 15:40
up vote 0 down vote

I actually posted this question: Simple solution for a scheduling puzzle in an attempt to get a simple mathematical proof (a proof is known but relatively involved). So far, it did not work...

share|improve this answer
up vote 0 down vote

One of the questions I posted here is exactly that, you can click on my profile to find it, but because of that pesky 'linked'/'related' sidebar, please do not link it!

share|improve this answer

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.