Mathematician claims breakthrough in Sudoku puzzle

nature.com: Via: Mathematician claims breakthrough in Sudoku puzzle. Puzzles must have at least 17 clues to have a valid solution.

slashdot.org: Lower Limit Found For Sudoku Puzzle Clues

An Irish mathematician has used a complex algorithm and millions of hours of supercomputing time to solve an important open problem in the mathematics of Sudoku, the game popularized in Japan that involves filling in a 9X9 grid of squares with the numbers 1–9 according to certain rules.

Gary McGuire of University College Dublin shows in a proof posted online on 1 January1 that the minimum number of clues — or starting digits — needed to complete a puzzle is 17; puzzles with 16 or fewer clues do not have a unique solution. Most newspaper puzzles have around 25 clues, with the difficulty of the puzzle decreasing as more clues are given.

“The approach is reasonable and it’s plausible. I’d say the attitude is one of cautious optimism,” says Jason Rosenhouse, a mathematician at James Madison University in Harrisonburg, Virginia, and the co-author of a newly released book on the maths of Sudoku.

Having spent two years testing the algorithm, McGuire and his team used about 700 million CPU hours at the Irish Centre for High-End Computing in Dublin, searching through possible grids with the hitting-set algorithm. “The only realistic way to do it was the brute force approach,” says Gordon Royle, a mathematician at the University of Western Australian in Perth who had been working on the problem of counting 17 clue puzzles using different algorithms.

Papier en format PDF

Wolfram: Computable Document Format (CDF)

Wolfram: Computable Document Format (CDF)

Launched by the Wolfram Group, the CDF standard is a computation-powered knowledge container—as everyday as a document, but as interactive as an app.

Adopting CDF gives ideas a broad communication pipeline—accelerating research, education, technical development, and progress.

Le “viewer” demande 684MB d’espace! On est loin d’adobe flash quand meme, ce qui explique qu’il est plus gourmand. Le rendu 3D me semble un peu ordinaire, mais l’idee pourrait interesser les matheux qui veulent partager des documents.

Yet Another Cantor Crank

Good Math, Bad Math: Yet Another Cantor Crank

The problem with the run-of-the-mill Cantor crank is that they never even try to actually address Cantor’s proof. They just say “look, here’s a mapping that works!”

So the entire disproof of their “refutation” of Cantor’s proof is… Cantor’s proof. They completely ignore the thing that they’re claiming to disprove.

Pas mal, n’est-ce pas? LOL 😉

Indian Mathematician Takes Shot At Proving Riemann Hypothesis

Kali & the Kaleidoscope: KNK103: The Crystals of Mt. Zeta

Via: slashdot.org: Indian Mathematician Takes Shot At Proving Riemann Hypothesis

The protagonist of this expedition is a creature called the Zeta function which, under certain conditions, squeezes the prime numbers scattered over an imaginary rubber sheet into a straight line. In highly technical language, the hypothesis is very brief: “The non-trivial zeroes of the Riemann-zeta function have real part equal to 1/2” which may take a couple of months for a non-mathematician to fully grasp. This is why during the online workshop we will start with the very basics – what is a prime number?

Start with the basic…. On est loin du but….<sarcasme> bonne chance! </sarcasme>

J’aime bien l’idee d’un workshop en ligne et d’exposer le probleme au plus de monde possible. Malheureusement, c’est plus une facon de faire de l’argent (il faut payer pour participer et/ou suivre l’atelier) qu’un exercice dans le but de resoudre le probleme.

Belief in God Boils Down to a Gut Feeling

Via: Belief in God Boils Down to a Gut Feeling

Ce que j’aime particulierement, c’est la question posee:

Shenhav and his colleagues investigated that question in a series of studies. In the first, 882 American adults answered online surveys about their belief in God. Next, the participants took a three-question math test with questions such as, “A bat and a ball cost $1.10 in total. The bat costs $1 more than the ball. How much does the ball cost?”

The intuitive answer to that question is 10 cents, since most people’s first impulse is to knock $1 off the total. But people who use “reflective” reasoning to question their first impulse are more likely to get the correct answer: 5 cents.

Donc, si je comprends bien, repondre 10 cents est “intuitif” et le monde “intuitif” tend a croire a des conneries? ROTFLMAO.

A game with a windfall for a knowing few

boston.com: A game with a windfall for a knowing few

Via: canadiancapitalist.com: This and That: Stock Markets, Lotteries and more…

Over the next three days, Selbee bought $307,000 worth of $2 tickets for a relatively obscure game called Cash WinFall, tying up the machine that spits out the pink tickets for hours at a time. Down the road at Jerry’s Place, a coffee shop in South Deerfield, Selbee’s husband, Gerald, was also spending $307,000 on Cash WinFall. Together, the couple bought more than 300,000 tickets for a game whose biggest prize – about $2 million – has been claimed exactly once in the game’s seven-year history.

Mark Kon, a professor of math and statistics at Boston University, calculated that a bettor buying even $10,000 worth of tickets would run a significant risk of losing more than they won during the July rolldown week. But someone who invested $100,000 in Cash WinFall tickets had a 72 percent chance of winning. Bettors like the Selbees, who spent at least $500,000 on the game, had almost no risk of losing money, Kon said.

Champernowne constant

Je ne connaissais pas cette constante qui semble beaucoup trop simple pour avoir dejouee des algorithmes verifiant si un nombre est alleatoire. Et pourtant, c’est le cas. Il semble que ce soit la normalite du nombre qui ait dejoue les tests.

Wikipedia: Champernowne constant

Via: digg.com: An easy-to-make sequence that fooled random number checkers

0.1234567891011121314151617181920212223…

L’article de wikipedia pointe vers deux autres constantes interessantes:
Copeland–Erdős constant
Liouville number

Supercolony trails follow mathematical Steiner tree.

itnews.com.au: Supercolony trails follow mathematical Steiner tree.

Via: slashdot.org: Ants Build Cheapest Networks

“We found that ants almost always made networks that minimised the total amount of trail, consistent with optimisation at a colony level, rather than at an individual level,” Latty told iTnews. “In many cases, they did a remarkable job of making networks that looked almost exactly like the mathematical shortest path, called a ‘Steiner tree’.”

wikipedia.org: Steiner tree problem

The Steiner tree problem is superficially similar to the minimum spanning tree problem: given a set V of points (vertices), interconnect them by a network (graph) of shortest length, where the length is the sum of the lengths of all edges. The difference between the Steiner tree problem and the minimum spanning tree problem is that, in the Steiner tree problem, extra intermediate vertices and edges may be added to the graph in order to reduce the length of the spanning tree.

Euler’s Partition Function Theory Finished

The Language of Bad Physics: Finite formula found for partition numbers

Via: slashdot.org: Euler’s Partition Function Theory Finished

In this setting, a partition is a way of representing a natural number n as the sum of natural numbers (ie. for n = 3, we have three partitions, 3, 2 + 1, and 1 + 1 + 1, independent of order). Thus, the partition function, p(n), represents the number of possible partitions of n. So, p(3) = 3, p(4) = 5 (for n = 4, we have: 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1) , etc..

A partition of a non-negative integer n is a non-increasing sequence of positive integers whose sum is n.

It seems that since Euler initially came up with his generating function, there haven’t been major leaps in our understanding of partition numbers.

Apparently that all changes tomorrow. Ken Ono and colleagues, Jan Bruinier, Amanda Folsom and Zach Kent, will be announcing results that include a finite, algebraic formula for partition numbers thanks to the discovering that partitions are fractal. Well, so what does this mean, for partition numbers to be fractal?

Ken Ono, in the press release:

The sequences are all eventually periodic, and they repeat themselves over and over at precise intervals.

Voici le lien vers le papier en format PDF.

Polynomial Time Code For 3-SAT Released, P==NP

slashdot.org: Polynomial Time Code For 3-SAT Released, P==NP

“Vladimir Romanov has released what he claims is a polynomial-time algorithm for solving 3-SAT. Because 3-SAT is NP-complete, this would imply that P==NP. While there’s still good reason to be skeptical that this is, in fact, true, he’s made source code available and appears decidedly more serious than most of the people attempting to prove that P==NP or P!=NP. Even though this is probably wrong, just based on the sheer number of prior failures, it seems more likely to lead to new discoveries than most.

Beaucoup de commentaires sur slashdot semblent indiquer que le probleme a ete simplifie et que meme si le code fonctionnait en P, ceci n’impliquerait pas que P==NP.