$1,000,000 question (1 Viewer)

[buchanan]

Let n be a positive integer > 1
and σ(n)=sum of positive divisors of n
and h(n)=n-th harmonic number=1/1+1/2+...+1/n
and f(n)=h(n)+e^h(n)ln(h(n)).
Then f(n)>σ(n)

This is equivalent to the Riemann Hypothesis and is easy to verify on the calculator for small values of n.

For example, f(4)=7.97...>σ(4)=7

If you can show it is true for all n>1, you win $1,000,000: www.claymath.org

 

[Sober]

Given a random minesweeper board, determine whether or not it is possible to solve it without trial and error and you'll have another $1,000,00 as that is equivalent to the P=NP problem.

 

[icycloud]

Given a random minesweeper board, determine whether or not it is possible to solve it without trial and error and you'll have another $1,000,00 as that is equivalent to the P=NP problem.

The first move is always a guess...

 

[Sober]

The problem is not to solve minesweeper but to create an algorithm which determines whether or not a random board has any possible solution or if it has logical inconsistances like for instance an 8 next to a 1. Ian Stewart goes into more depth: http://www.claymath.org/Popular_Lectures/Minesweeper/

 

[icycloud]

Yes I've read that before actually. What you said isn't what the problem really is. A "random minesweeper board" (as you say) includes a board with all blanks, in which case the first move would have to be a guess.

Here is what the problem is as stated in the article:
"The link to the computer game comes when we introduce the Minesweeper Consistency Problem. This is not to find the mines, but to determine whether a given state of what purports to be a Minesweeper game is or is not logically consistent."

 

[Sober]

Yes I've read that before actually. What you said isn't what the problem really is. A "random minesweeper board" (as you say) includes a board with all blanks, in which case the first move would have to be a guess.

Here is what the problem is as stated in the article:
"The link to the computer game comes when we introduce the Minesweeper Consistency Problem. This is not to find the mines, but to determine whether a given state of what purports to be a Minesweeper game is or is not logically consistent."

Well yes that is what I meant, I do not consider a completely blank board to be random, how could it be? It changes depending on where you click. The mines are planted afterwards making sure you do not lose on your first click.

 

[icycloud]

Well yes that is what I meant, I do not consider a completely blank board to be random, how could it be? It changes depending on where you click. The mines are planted afterwards making sure you do not lose on your first click.

OK very well, not a blank board then, but a board with all blanks except one square which contains a "1" (a random board according to your definition). How can you solve that without using trial and error? You can't. That's not what the problem is asking for anyway.

 

[Sober]

I don't know what you are picking up on but I believe that there is nothing incorrect about what I have said.
A problem consisting of a blank board with one square uncovered would be completed by determining that it does not self contradict, the puzzle itself does not need to be solved. Even a blank board would make a valid problem.
Trial and error is analogous to a non-P algorithm where every solution would have to be tested until one is found that works.

Here is what I posted before:

The problem is not to solve minesweeper but to create an algorithm which determines whether or not a random board has any possible solution or if it has logical inconsistances

Then you rebutted with:

This is not to find the mines, but to determine whether a given state of what purports to be a Minesweeper game is or is not logically consistent.

I agree that at first I was ambiguous, but now that you understand my definition of a random board, what exactily is the difference between these two phrases?

 

[wanton-wonton]

Maths is interesting, but you two are just sad.

Pardon my lack of intellect.

 

[icycloud]

Well firstly you did say "solve it without trial and error" which implies uncovering all the squares without getting a mine. Then you changed your definition of "random" to "a non-blank game grid", so by your definition, the problem is "solving without trial and error any random non-blank grid", which includes a grid with only 1 square uncovered. (I'm still talking about your first post, before you 'corrected' it)

That is what I understood of what you said. If it's not right, I apologise. Let's not take this up any further , and just go by the definition on the website.

 

[buchanan]

Maths mystery 'almost solved'
Leigh Dayton

The Australian

February 20, 2006


RUSSIAN mathematician Grisha Perelman is on the verge of collecting $US1 million ($1.35 million) for solving one of the seven greatest mathematical problems of all time, the Poincare Conjecture.

"The word is he's got it," said mathematician Thomas Hales of the University of Pittsburgh. "But no one wants to say so in case they're wrong," he told The Australian yesterday at the annual American Association for the Advancement of Science meeting in St Louis, Missouri.

The Poincare Conjecture is about the "mathematics of smooth behaviour", said Keith Devlin, a mathematician at Stanford University in California and author of the 2002 book The Millennium Problems: the seven greatest unsolved mathematical puzzles of all time.

According to Professor Devlin, the conjecture proposes a way to tell if a bizarre-looking object is an ordinary three-dimensional object in disguise.

The Millennium Prizes were established in 2002 by the Clay Mathematics Institute in Cambridge, Massachusetts, as a challenge to mathematicians.

Four years ago, Perelman thought he had cracked the problem -- first posed by French mathematician Henri Poincare in 1904.

But the CMI did not accept his solution, or proof. It did not meet the institute's strict requirements: a peer-reviewed publication of the work, as well as a two-year waiting period to see if the solution stood up to scrutiny.

However, CMI president James Carlson added weight to the scuttlebutt at yesterday's meeting. "Hopes are high that a peer-reviewed version of the proof will appear soon," he said.

Still, not everyone is convinced. Professor Devlin, for one, predicts that the CMI is more likely to pay out for the solution of another millennium problem, the so-called Reimann Hypothesis.

It looks at how randomly prime numbers -- divisible only by themselves or 1 -- are sprinkled along a line of numbers. Together with three other millennium problems, the hypothesis is key to internet security.

When will it be cracked? "Oh, in about a decade," suggested Professor Devlin.

http://www.theaustralian.news.com.au/common/story_page/0,5744,18204052%255E30417,00.html

http://www.aaas.org/meetings/Annual_Meeting/