Waste less time on Facebook — follow Brilliant.
×

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

Note by Jason Dyer
4 months, 2 weeks ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. 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"
MathAppears 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

Sort by:

Top Newest

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 - 2 months, 3 weeks ago

Log in to reply

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 - 2 months, 3 weeks ago

Log in to reply

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 - 2 weeks, 1 day ago

Log in to reply

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 - 2 months, 2 weeks ago

Log in to reply

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 - 1 month, 2 weeks ago

Log in to reply

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 - 2 months, 2 weeks ago

Log in to reply

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 - 2 months ago

Log in to reply

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 - 1 month, 2 weeks ago

Log in to reply

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 - 1 month ago

Log in to reply

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 - 1 month ago

Log in to reply

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 - 2 months ago

Log in to reply

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 - 1 month, 2 weeks ago

Log in to reply

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 - 2 months ago

Log in to reply

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 - 2 months ago

Log in to reply

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 - 2 months ago

Log in to reply

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 - 2 months, 2 weeks ago

Log in to reply

This is a known result.

Jason Dyer Staff - 2 months, 2 weeks ago

Log in to reply

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 - 2 months, 3 weeks ago

Log in to reply

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 - 2 months, 3 weeks ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...