38

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)?

Battle
  • 103
  • 2
MikeS159
  • 489
  • 4
  • 6
  • 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 '18 at 09:34
  • 1
    Good point, I need to specify that the room numbers are positive. – MikeS159 Aug 21 '18 at 09:38
  • 5
    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 '18 at 09:49
  • I should probably highlight that you don't want to spend life in prison either – MikeS159 Aug 21 '18 at 09:52
  • 1
    The Collatz Conjecture: the simplest mathematical problem to understand, yet one of the hardest to prove :D – Mr Pie Aug 21 '18 at 11:12
  • How about the number ZERO...? :) – CiaPan Aug 21 '18 at 12:00
  • I will specify the n is a interger > 0 – MikeS159 Aug 21 '18 at 12:01
  • @CiaPan well, $0\div 2$ is just $0$, so that bends the rules slightly :) – Mr Pie Aug 21 '18 at 12:17
  • Room 1 "is the lowest room number" :) just to shoot down the Room Zero suggestion. – Ruadhan2300 Aug 21 '18 at 14:20
  • "is the lowest room number" was a later edit. So people suggesting 0 were actually correct :) – MikeS159 Aug 21 '18 at 14:38
  • 1
    I wonder why people are using spoiler boxes for the problems they submit as answers here ? – Evargalo Aug 21 '18 at 14:47
  • But wait... this doesn't fit the listed conjecture tightly enough because of the external conditions introduced. If the rooms are numbered arbitrarily high, just pick a number at least as large as $2^{1000000}$. Since nobody lives for 1000000 days, you have proven that you will not reach room 1 to be executed, thus you will be sent free. If the numbers are not listed high enough, they are finite, and an answer could be definitively computed. – Ian MacDonald Aug 21 '18 at 20:07
  • 2
    @IanMacDonald I need to word it better to make it fit the conjecture. – MikeS159 Aug 21 '18 at 22:03
  • As interesting as this is, I'm not sure this question is particularly on-topic here as there is no single answer which can be determined to be "most correct", or really a question to be solved. (Perhaps meta, or chat would be better places for this?) –  Aug 22 '18 at 09:59
  • Also, I'm really not sure why people are completely spoilerizing their answers. I can see why people might want to spoiler the mathematical problem but spoilering the puzzle statement seems pointless. – David Richerby Aug 22 '18 at 12:39
  • I really like this idea, but what about posting some of these here as puzzles; who knows, maybe someone will actually solve one of them, which would be really awesome! – bob Aug 22 '18 at 20:13
  • 1
    You might like the Moving Sofa Problem, if you haven't heard of it. The link takes you to an actual page written and explained by a mathematician, Dan Romik, who improved on the problem (in this paper). The "puzzle" side of it can be described here, and if you are interested to learn some more extra detail/history on the subject, you can go here. I like the problem :D – Mr Pie Aug 23 '18 at 00:06
  • This is more of an aside, but I would absolutely hate it if someone did this to me at my work. People are working and spending their own time on these puzzles, partly because they think they're solvable and because it's fun. You're effectively ruining the good faith of putting up solvable puzzles and people trying them by doing this. At least, if it's not immediately apparent that it's unsolvable (which goes against the point of your joke so I doubt it), it would really bum me out. – JGibbers Nov 07 '18 at 15:36
  • 1
    I am considering waiting until April 1st to post it :) – MikeS159 Nov 07 '18 at 22:43
  • 4
    I’m voting to close this question because it's an open-ended list – bobble Jul 28 '21 at 15:51

10 Answers10

30

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.

hexomino
  • 135,910
  • 10
  • 384
  • 563
  • 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 '18 at 11:07
  • Ahhh, I know of this problem! There are many "deal with the devil" sorts of puzzles, but I quite like this one. $(+1)$ :) Edit: Oh jeez, that was my last upvote; I can't upvote the question :\ – Mr Pie Aug 21 '18 at 11:14
  • 13
    Can you draw a curve on paper that isn't piecewise smooth? – Christopher Aug 21 '18 at 13:22
  • @Christopher That is a very good point which I completely overlooked. Maybe we should add in the caveat that you are an excellent drawer, in that anything you can mathematically describe you can draw? – hexomino Aug 21 '18 at 13:35
  • 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 '18 at 14:24
  • 10
    @Ruadhan2300: a Math Daemon — is that something to do with the Bourne identity? – Peter LeFanu Lumsdaine Aug 21 '18 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 '18 at 19:53
  • 1
    @Trish Interesting. I guess the question does sort of assume a notion of what a "closed loop" is. Although I have to admit, I haven't come across a definition which includes a single point. – hexomino Aug 21 '18 at 21:47
  • 1
    hmmmm, could you just draw an infinite line and procede to demand proof for the curvature of the universe? – tox123 Aug 21 '18 at 22:53
  • @hexomino the problem is defined on a "closed Jordan loop" which demands a length > 0, the question not. Closed loop means simply "start and end point are the same", but demands not "passes more than 1 point" – Trish Aug 22 '18 at 04:07
  • @tox123 an infinite loop is not a closed loop and for certainly not a closed jordan loop. Also, curvature of the universe only exists in 3D, not in 2D as the problem demands. – Trish Aug 22 '18 at 04:08
  • @PeterLeFanuLumsdaine I really really hope Matt Damon was in his school Math Club... – Ruadhan2300 Aug 22 '18 at 08:09
  • @Trish It's an interesting argument and I've spent the last while trying to pick apart the definitions - it seems not to be really clarified anywhere. As an aside, I also stipulated in the question that the loop be non-self-intersecting. Would you consider a point as self-intersecting? If not, does there exist a loop with no points? – hexomino Aug 22 '18 at 10:55
  • @tox123 If I have to do an infinite amount of drawing, I'll never get to heaven anyway. Though I guess it stops me going to hell, at least. – David Richerby Aug 22 '18 at 12:41
  • @hexomino I am actually oddly not sure... So... I asked on mathematics if a point is a Jordan Loop... https://math.stackexchange.com/questions/2891329/is-a-point-a-jordan-curve – Trish Aug 22 '18 at 18:46
  • @Christopher If its a real drawing, the ‘curve’ wouldn’t even be closed at a high enough magnification. – Lawrence Aug 23 '18 at 00:57
27

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$.

Christopher
  • 725
  • 4
  • 7
  • It seems deceptively simple. Do you know of a source that explains a little bit of the computational difficulty? – hkBst Aug 21 '18 at 15:08
  • +1 This is a good one. – hexomino Aug 21 '18 at 15:10
  • @hkBst https://math.stackexchange.com/questions/867470/why-are-there-only-a-few-known-ramsey-numbers – Christopher Aug 21 '18 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 '18 at 12:37
  • @DavidRicherby You wouldn't have to take every n, just go until one doesn't work. – Acccumulation Aug 22 '18 at 21:43
  • @Acccumulation Obviously. But even checking one exhaustively is an infeasibly huge computation. $2^{43\times42/2}$ is many orders of magniture larger than the number of atoms in the universe, or the age of the universe in nanoseconds or... – David Richerby Aug 22 '18 at 21:49
  • I think this problem is in Matt Parker's, Things to Make and Do in the Fourth Dimension (2014) :P – Mr Pie Aug 22 '18 at 21:56
15

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?

Tanner Swett
  • 2,319
  • 14
  • 23
6

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.

Mr Pie
  • 6,682
  • 1
  • 25
  • 88
  • 2
    I think you need to precise m,n>1 – Evargalo Aug 21 '18 at 14:44
  • @Evargalo oh yes, will do. Thanks for that :) – Mr Pie Aug 21 '18 at 21:37
  • 2
    Do you mean a rectangle shape? – wizzwizz4 Aug 22 '18 at 18:13
  • @wizzwizz4 yes, precisely. That defines the term, "quadrilateral". So $m$ rows of $n$ would be a rectangle-shape with area $m\times n$. You can choose which value represents length and which one represents width, but either way, there would be $m\times n$ candles since they make up the entire area... but some numbers (or prime numbers) don't necessarily obey the rules... :) – Mr Pie Aug 22 '18 at 21:43
  • 1
    @user477343 Rhombus kite trapezium etc. are quadrilaterals and not rectangles. – wizzwizz4 Aug 22 '18 at 21:50
  • @wizzwizz4 but they still have area $m\times n$ with (say) length $m$ and width $n$. From the property of prime numbers, it doesn't matter in this puzzle if the candles are specifically ordered in a rectangle-shape. A quadrilateral is literally just a (convex) shape with four sides with the same area I just mentioned. – Mr Pie Aug 22 '18 at 21:53
  • @user477343 Arrowhead. – wizzwizz4 Aug 22 '18 at 21:53
  • @wizzwizz4 $\uparrow$ $\uparrow$ :D – Mr Pie Aug 22 '18 at 21:54
  • 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 '18 at 21:56
  • @wizzwizz4 well trapeziums have other components, say $m, n, h$ with area $h(m+n)\div 2$ so if $h$ is odd and/or $m+n$ is odd, we won't be able to order the number of candles in a trapezium. Apologies for that exclusion :\ – Mr Pie Aug 22 '18 at 21:58
  • @user477343 Arrowheads? Completely irregular quadrilaterals where you know the side lengths and angles? It makes sense to limit it to at least parallelograms. – wizzwizz4 Aug 22 '18 at 22:00
  • @wizzwizz4 I thought you meant something else. :\ besides, I said in the beginning I meant $m$ rows of $n$, so the quadrilaterals just fall under that. But I guess, on the technical side of things, I can call it parallelograms :P – Mr Pie Aug 22 '18 at 22:24
  • @wizzwizz4 I have credited you in my answer above :) – Mr Pie Aug 22 '18 at 23:46
4

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

JMP
  • 35,612
  • 7
  • 78
  • 151
  • Is this not possible though? – MikeS159 Aug 21 '18 at 11:48
  • @MikeS159; no-one's found a simple proof yet, and the suggested proofs are still being debated : https://nrich.maths.org/6291 (last chapter) – JMP Aug 21 '18 at 11:54
  • 2
    I was ready to disagree, then I noticed the word "simple" – George Menoutis Aug 21 '18 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 '18 at 15:15
  • @hkBst; but they can live in a network like that. your task is to find a network they can't live in. – JMP Aug 21 '18 at 15:28
  • 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 '18 at 15:41
  • 5 rooms all connected by corridors to each other room? – hkBst Aug 21 '18 at 16:37
  • @hkBst; two corridors would intersect - https://www.youtube.com/watch?v=YqEeaudxghE – JMP Aug 21 '18 at 16:50
  • Indeed this would be a non-planar graph, which your problem description does not rule out (yet). Imagine a network of corridors in the shape of a pyramid with a room at each vertex and corridors along all the edges and two additional diagonal corridors crossing over each other in the bottom of the pyramid. – hkBst Aug 21 '18 at 17:42
  • @JonMark Perry. I just re-read the puzzle. I had initially misread it. – Steve B Aug 22 '18 at 14:06
  • The puzzle is not equivalent to the 4 color map theorem. In the puzzle, the number of each type of elemental is set. Four coloring some maps requires limiting the number of vertices of some colors. Suppose there are 8 elementals, 2 of each type. Have your network consist of a central room connected by corridor to each of the other 7 rooms. Any elemental in the central room will be adjacent to a room with an elemental of the same color. – Steve B Aug 22 '18 at 14:14
  • @SteveB; you are not forced into a specific set of elementals, just as long as the network is safe for some of them. – JMP Aug 22 '18 at 14:22
  • @JonMark Perry. 1) If I'm not forced into a specific set of elementals, then I'm free to choose a set of 8, 2 of each kind. Which I did. I'm not sure what your point is. 2) I have no idea what the network being safe for some of them has to do with the puzzle. – Steve B Aug 23 '18 at 01:47
  • @JonMarkPerry saying the proof is being "debated" is a massive over-statement, and implies that its correctness is disputed: as far as it goes nobody has managed to refute the proof. It's just that some people don't like computer-assisted proofs, which are opinions on techniques being used and has nothing to do with the proof itself. – Voile Aug 23 '18 at 01:53
  • @SteveB; a network is safe if some selection of elementals (you don't even have to use all 4 types) can live in it. if you insist on a particular selection, just choose all fire types, then no network is safe, except for those with only singletons. – JMP Aug 23 '18 at 02:30
  • @Voile; no-one has overwhelming accepted them either. "Some said that proofs should only be 'proved' by people, not machines, while others, of a more practical mind questioned the reliability of both the algorithms and the ability of the machines to carry them out without error." - a debate n'est-ce pas? – JMP Aug 23 '18 at 02:35
  • @JonMarkPerry ...which all boils down to arguments on the methodology. None of the "debates" being raise there are actual refutations about the proof, which would have to be based on something concrete and reasonable (e.g there is a missed case); they're arguments on whether computer-assisted proof feels good to them, which has nothing to do with the proof itself, and are merely opinions. If you can't actually refute a proof, and yet insisting it's "wrong" because you don't like how it's proven, then... okay? But the proof is by no means less valid due to your feelings. – Voile Aug 23 '18 at 03:10
4

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.

Steve B
  • 340
  • 1
  • 9
  • 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 '18 at 21:16
  • This is known as the Square-Sum Problem which already has a solution... but still very interesting, so $(+1)$ :D – Mr Pie Aug 22 '18 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 '18 at 01:59
3

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.

u-ndefined
  • 5,181
  • 1
  • 12
  • 49
trivialsolution
  • 31
  • 1
1

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.

JMP
  • 35,612
  • 7
  • 78
  • 151
Michael Seifert
  • 1,619
  • 10
  • 16
1

One of the questions I posted here is exactly that. Its question ID is #74037, or you can click on my profile to find it.

But please do not link it, because then when someone looks at the puzzle, "Unsolved maths problems as puzzles" would show up in that pesky 'linked'/'related' sidebar ... which would be sort of a spoiler!

deep thought
  • 5,158
  • 1
  • 17
  • 48
0

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...

Falk Hüffner
  • 201
  • 1
  • 6