Thread for Suggesting Open Problems

This thread is for suggesting open problem to solve. Some general guidelines:

a) The problem should be understandable by a wide audience, ideally at a pre-calculus level. (Note calculus is still fine as a solving approach, if that becomes important.)

b) Very famous problems are not recommended -- pick something that is simpler that we have a chance at approaching. If you are interested in a famous problem, pick an open problem that is related.

c) The open problem can be along the lines of "categorize everything of type X" or "a proof is known for Y, but can we find a better one?"

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

I've been trying to find a general solution to the "battery" problem.

i.e. If you have $x$ batteries, and $y$ of them are good, and you have a flashlight that contains $z$ batteries, ( $x>y>z$ ) what is the minimum number of times you need to load up the flashlight in order to light it up?

Assumption: The flashlight only lights up if all the batteries in it are good, otherwise it doesn't light up, or give any other indication that any of the batteries might be either good or bad. i.e. The flashlight has only two states: on (all batteries are good) or off (at least one is bad)

Any thoughts?

Geoff Pilling - 3 years, 7 months ago

This one sounds perfect! I would need to do a little research first to make sure it's definitely open (it sounds like one that might be solved but isn't a well-advertised result).

Jason Dyer Staff - 3 years, 7 months ago

A similar problem would be the diarrhea problem. Given $x$ plates of food of which $y$ of them are poisoned, what is the minimum number of people needed to find which plates are the poisoned ones?

Assumption: A person would diarrhea if he has eaten from poisoned plate, so he can eat from a number of other plates but as long as 1 is poisoned, he would diarrhea. Additionally, there is only 1 testing session, so a person cannot test the plates, diarrhea, and then continue testing.

The only non-trivial case I've solved is when $y=1$ , where the minimum number of people is $\left \lceil{\log_{2}x}\right \rceil$

Julian Poon - 3 years, 5 months ago

This problem may have a solution, I'm not sure.

Consider an $n \times n$ grid. Each square can either be open or closed, except for the top left and bottom right squares, which are always open. How many arrangements exist such that there exists a path from the top left to the bottom right square (moving only up/down/left/right)?

Andrew Hayes Staff - 3 years, 7 months ago

On a specific grid, this is related to the "Rat in a Maze" problem usually given as a CS exercise (find all the paths out of a set maze). I've never heard this type of variation before.

Jason Dyer Staff - 3 years, 7 months ago

I've been working on this for a few hours now. I tried the following approaches: 1) Generalizing it to an mxn grid, to facilitate recursive definitions. 2) Examining a jagged mxn grid, where the bottom right half has been cut off. 3) Looking at the independence between paths to understand what would happen if two boards with one path each were combined by adding up their open squares. 4) Looking at the question in terms of "cuts" of be board instead, since if a grid does not have a path, then it must have some place where there is a path of closed squares that separates the starting square from the ending square, and this "path" of closed squares can include diagonals.

None of these resulted in an answer, yet. I think the most promising of them is option 4, since it will generalize better to higher size grids. The thinking here is that up to grids of size 4x4, any shortest path from the top left to bottom right is going to include only down and right movements. From 5x5 and up, it is possible for it to snake through, instead. Any counting of the paths might use the assumption that the movements can only be down and right when working on smaller cases, but if we are looking at cuts instead, then that kind of assumption won't hinder us.

Nathan Oshlag - 3 years, 6 months ago

Can you always make a Knight's Tour if you remove any two squares that are different colors?

Definition: A Knight's Tour is defined as path that a Knight uses to go to all squares on the board exactly once. Removing a square from the board means that the square is not going to be visited on the tour.

Mike Harding - 3 years, 7 months ago

I need to do some more research to make sure the state is unknown, but I'm fairly sure something like this would work. (I would save for a later month, though - I'm guessing we need something other than chess coming up.)

Jason Dyer Staff - 3 years, 6 months ago

If you only remove one square, then if there is a re-entrant knight's tour on the board, then there is still a path with the square before the removed one being the end and the square after the removed one being the beginning. A similar train of thought may be useful for this problem.

Nathan Oshlag - 3 years, 1 month ago

I believe this paper may have a solution in it somewhere. https://digitalcommons.kennesaw.edu/cgi/viewcontent.cgi?article=2152&context=facpubs

Nathan Oshlag - 3 years, 1 month ago

Here's a nice open problem I found:

For each integer $n \geq 2$ , consider a regular polygon with $2n$ sides, all of length $1$ . Let $C(n)$ denote the number of ways to tile this polygon using quadrilaterals whose sides all have length $1$ .

Determine the limit inferior and the limit superior of the sequence defined by $\frac{1}{n^2} \log_2 C(n).$

Note that the sequence $C(n)$ is $A006245$ on OEIS.

Sharky Kesa - 3 years, 7 months ago

I found the paper related to this.

I'm not sure there's "more to do" here though - is there something specific that makes you think the bounds could be tighter?

Jason Dyer Staff - 3 years, 6 months ago

I am curious about generalizations for the problems I posted "Hexagonal Checkers" and "Hexagonal Checkers 2." Generalizations might include different end goals, different board dimensions or type of board, or different moves. One such generalization that has already been proven would be Conway's Soldiers. Any interesting generalizations would be helpful.

John Ross - 3 years, 2 months ago

I've been thinking about "distributions into bins" types of problems, particularly ones with restrictions on them. For example, I was thinking of distributions of $n$ identical objects into $r$ distinct bins which each have capacity $c.$ It turns out there's a solution to that. I'm wondering if we can put it into more explicit terms, though.

Are there any other "distributions into bins with restrictions" problems that don't have a solution?

Andrew Hayes Staff - 3 years, 7 months ago

Yes, if there's weighting. See the Bin Packing Problem and other related ones from computer science - I don't know of a good variant to zero in on, but there's probably a good candidate or two for algorithm improvement.

Jason Dyer Staff - 3 years, 7 months ago

I've also been considering a general solution for how many different ways you can arrange the letters in a word such as BRILLIANT such that no letter in the rearrangement ends up in the same spot. For a word with all unique letters, it is simply done with derangements; however, for a word with repeated letters, I haven't found a general solution. i.e. For a word with $n$ letters, there are $!n$ ways to rearrange them all into different spots; however, what if there are $n$ letters and one is repeated twice and two are repeated three times?

Geoff Pilling - 3 years, 7 months ago

This is a known result.

Jason Dyer Staff - 3 years, 7 months ago

This one has stumped me for years. Hoping for a solution. I have solved it iteratively, but not by true arithmatic. I believe this discussion is the place to be.

A horse is tied to a post with a 10 foot rope. On day 1, he eats all the grass he can reach, creating a circle of bare ground. On day 2, the rancher moves the post to the perimeter of the circle, but he wants the horse to eat the same amount as he did on day 1. How long should the rope be on day 2? Assume the grass didn’t grow appreciably overnight.

Mike Perry - 3 years, 7 months ago

You can use the formula at http://mathworld.wolfram.com/Circle-CircleIntersection.html (this is area of intersection of arbitrary circles) with R as the unknown, r as 10, d as 10, and the formula piR^2 - (AREA OF THE INTERSECTION) = pi(10^2).

Assuming I didn't make a typo (it's a nasty formula and I made a typo the first time) it comes out to approximately 12.512125.

Jason Dyer Staff - 3 years, 7 months ago

That is the correct answer I got by iteration after reducing to 6 equations and 6 unknowns. Thanks for the link. I’ll take a look. Mike

Mike Perry - 3 years, 7 months ago

One possible problem is the Gilbreath Conjecture.

Gilbreath observed a pattern while playing with the ordered sequence of prime numbers

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ... Computing the absolute value of the difference between term n+1 and term n in this sequence yields the sequence

1, 2, 2, 4, 2, 4, 2, 4, 6, 2, ... If the same calculation is done for the terms in this new sequence, and the sequence that is the outcome of this process, and again ad infinitum for each sequence that is the output of such a calculation, the following five sequences in this list are

1, 0, 2, 2, 2, 2, 2, 2, 4, ... 1, 2, 0, 0, 0, 0, 0, 2, ... 1, 2, 0, 0, 0, 0, 2, ... 1, 2, 0, 0, 0, 2, ... 1, 2, 0, 0, 2, ... What Gilbreath noticed is that the first term in each series of differences appears to be 1.

No one has been able to prove Gilbreath's observation ad infinitum.

Siva Budaraju - 3 years, 6 months ago

This is a relatively "famous" problem so is probably too difficult to approach "straight". I do like this though, I'm curious if there's a good sub-problem that might be more tractable.

Jason Dyer Staff - 3 years, 6 months ago

I saw a problem on the Numberphile YouTube channel, which may give the germ of an idea for a problem suitable for this forum. As stated it falls into the category of a famous problem - the Erdos-Szekeres convex polygon conjecture- , but is the kind of problem that you seem to be looking for. Given a set of n points on the plane, (no three of which are colinear), what is the largest n for which it can be that there is not a subset of r points which would form the the vertices of a convex r-sided polygon. The answer is known for small n, and this leads to an obvious conjecture that the general rule is n = 2^(r-2). [With a PLUS ONE, you ensure that there is a subset giving a convex r-sided polygon]. I couldn't find the youtube video I saw before, but https://www.youtube.com/watch?v=j7SCSGjGxk4 gives longer talk on the subject. Actually, many of the Numberphile videos might give ideas of problems to explore

Kenneth Evans - 3 years, 3 months ago

Greedy Spiders

This problem is based on the video game Greedy Spiders. You may consider downloading the app to get a feel of the problem.

We define the combinatorial game Greedy Spiders as follows:

The game involves a (finite) undirected graph $G$ .
A vertex $b$ is marked as bug.
Initially, on a specific vertex of the graph, a token called spider is placed.
The game is being played between two players: Player S and Player B. S stands for spider and B stands for bug.
In each turn of Player S, Player S must move the token spider to an adjacent vertex on the graph.
In each turn of Player B, Player B must delete an edge of the graph.
If at any point of the game play, the spider token is situated on the bug vertex, Player S has won.
If at any point of the game play, the spider token is in a seperate connected component than the bug vertex, Player B has won.

Intuitively, a bug is stuck in a web and a spider situated at some point on the web is crawling towards it. Can you help the bug escape by cutting the fabric of the web appropriately?

Now, here is our algorithmic problem:

Input: An initial configuration of a Greedy Spiders game
Problem: Decide who has a winning strategy.

Possible Directions to proceed in:

Give an efficient solution to the problem.
Failing 1, show some hardness result for this problem.
Give some heuristics that might solve the problem.
Study generalizations of the problem: What if there were multiple spiders and/or bugs? What if the graph was directed?

Agnishom Chattopadhyay - 3 years, 1 month ago

Is there anyway of seeing the posts ordered by the time/date in which they were posted? The default order of seeing those with the most votes first might be helpful in some circumstances (just possibly, for new comers wanting to see the important posts ), but it makes it very difficult for those wanting to keep up to date with the discussion. This is particularly important for the discussion pages related to the problems themselves.

Kenneth Evans - 3 years, 1 month ago

Yes. Check the top right corner where the comments start.

Jason Dyer Staff - 3 years, 1 month ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$