$50,000 To Solve the Most Complicated Puzzle Ever

An anonymous reader writes "A team from UC San Diego is using crowd-sourcing as a tool to solve the most complicated puzzle ever attempted, which involves piecing together roughly 10,000 pieces of different documents that have been shredded. (The challenge is designed to reveal new techniques for reconstructing destroyed documents, which are often confiscated by troops in war zones). The prize for solving this jigsaw puzzle is $50,000, which the UCSD team has decided to share among the people who participate. If they win, you would also receive cash for every person you recruit to the effort! The professor leading the team, Manuel Cebrian, won the challenge two years ago, so his odds of winning again are great"

Comments

only 50k for a problem that complex?

[Anonymous Coward]

only 50k for a problem that complex? If you could solve this problem, I say copyright and make millions off of the algorithm.

Re:only 50k for a problem that complex?

[Yaur]

It is exactly the same. This is just a team attempting to solve that challenge by crowd sourcing document assembly.

Doesn't scale

[Anonymous Coward]

The rules should require that the same method that solved the initial puzzle be successfully applied to 10 more shredded documents, to weed out methods that don't scale.

Re:Doesn't scale

[Surt]

Why 10 and not 4?

(I ask, because the contest requires 4 progressively harder documents be solved, with a declaration attached that says this is explicitly to filter out any methods that won't scale).

10,000 documents for $50,000 reward?

[GoodNewsJimDotCom]

If there is an offline version of this, it involves a garbage bag full of shredded 5$ bills and some scotch tape.

Re:10,000 documents for $50,000 reward?

[zill]

For those who didn't get the reference.

Shredding vs. burning

[Anonymous Coward]

I never really understood the purpose of shredding documents. If your documents are that sensitive, why not just burn them, leaving no trace of legible text? It seems like it would be cheaper, easier and faster too. Just throw them in a barrel outside, put a little lighter fluid in, and drop a match. Why is this not common?

Re:Shredding vs. burning

[arth1]

I never really understood the purpose of shredding documents. If your documents are that sensitive, why not just burn them, leaving no trace of legible text? It seems like it would be cheaper, easier and faster too.

What happens is that the top and botom pages and edges get scorched, but the middle part with the print remains largely intact.

Just throw them in a barrel outside, put a little lighter fluid in, and drop a match. Why is this not common?

Thus speaks someone who hasn't tried to burn more than a couple of sheets of paper.
It takes time to burn more than a few pages at a time. Or an extremely hot fire. Sorry, Mr Bradbury, 451 F won't do it, unless you can wait for weeks.

Re:Shredding vs. burning

[GumphMaster]

Indeed that is what became of classified material I have dealt with. Shredded using a military cross-cut shedder (output pieces smaller than 1x10mm), mixed thoroughly, and then incinerated using a purpose built belt-fed, gas fired machine.

Re:Shredding vs. burning

[DRJlaw]

I never really understood the purpose of shredding documents. If your documents are that sensitive, why not just burn them, leaving no trace of legible text? It seems like it would be cheaper, easier and faster too. Just throw them in a barrel outside, put a little lighter fluid in, and drop a match. Why is this not common?

1. Burning is inconvenient for small volumes of paper.
2. Burning is essentially illegal for large volumes of paper (business scale; Clean Air Act permits).
3. Fireplaces are not as common as they used to be; outdoor burning is illegal in most cities.
4. People can be idiots when using fire outside of a fireplace or permanent fire pit.
5. DIOXIN!

Shredding is like a residential door lock -- good enough to discourage a casual person who is too curious for their own good. Secure commercial shredders rely upon sheer volume and decent mixing (300 "particles" per page x 3 tons of paper dumped at a recycler is a decent level of obscurity) or "hydro-pulping" for the demanding (shred then pulp at paper mill -- good luck reassembling the fibers even if you get to them before bleaching).

Why are the documents shredded to begin with?

[damn_registrars]

Don't the warlords have access to fire? I'm pretty sure that brings about a thoroughly unrecoverable destruction of the documents...

Re:Why are the documents shredded to begin with?

[mollymoo]

I burn my old bank statements etc. and it's actually pretty time consuming and labour intensive to completely burn anything more than a few sheets. Just throwing a stack of papers on a fire doesn't work - the middle pages don't burn and are completely legible. Even when burnt, undisturbed paper ash still has legible text on it. You need to do a lot of stirring and separating of sheets to ensure complete destruction. It's much more time consuming than shredding.

Re:Why are the documents shredded to begin with?

[ShakaUVM]

>>Don't worry, the next contest will involve a $75,000 prize to reverse entropy

I hear students from UCSD have already summoned a demon to solve this puzzle.

Name's Maxwell, something like that...

Re:Why are the documents shredded to begin with?

[Trevorm7]

Or just run it through an HP printer, the process of trying to rip it out after it jams should do the trick.

Fifty cents a person

[tomhudson]

To complete this new challenge, it could take as many as 100,000 people

So, it's essentially worth less than a pack of gum.

Re:Fifty cents a person

[cowboy76Spain]

Hey, it's a month's wage in some poor countries, start building a document rebuilding plant somewhere in backwater Africa.

Sorry to mix actual data in your First World prejudices, but the GDP per capita of the poorest country is over $300, so monthly it would be around US 18$.

There are only 15 countries with a GDP per capita inferior to 100$ month

Re:Fifty cents a person

[Anonymous Coward]

Hey, it's a month's wage in some poor countries, start building a document rebuilding plant somewhere in backwater Africa.

Sorry to mix actual data in your First World prejudices, but the GDP per capita of the poorest country is over $300, so monthly it would be around US 18$.

There are only 15 countries with a GDP per capita inferior to 100$ month

Right, because income is evenly distributed there, and there aren't dirt poor people living off almost nothing. Plus, you're using PPP GDP per capita, rather than GDP per capita at nominal exchange rates. If I pay someone in another country $1, they get to buy what $1 buys in their country, not what $1 buys in the USA.

Sorry to mix actual facts into your misrepresented data.

SHHH!!

[jensend]

Everyone in the civilized world is worried about what will happen if terrorists gain access to this technology. That's why most nations have signed the Fire Non-Proliferation Treaty, and it's why the International Combustive Energy Agency is working round-the-clock to keep this technology from falling into the wrong hands (while somehow also promoting civilian use of combustive energy).

You've got to be a lot more careful about talking about such restricted technology and its possible uses.

Re:SHHH!!

[jensend]

See also United States v. Prometheus for more about the penalties for divulging such classified information.

Confused?

[wisnoskij]

Is it just me or does this make little to no sense.
You cannot scale putting together puzzle pieces because the same person needs to both see two pieces that go together and recognize that they match.
So yes more people help, but if there are 10 million pieces then the average person would have to look at over 1 million pieces before they have even seen two that go together.

And this seems like a very easy thing to computise.
You digitize the shredded documents.
You run a program that looks for similarities around the edges.
You stick likely candidates together and either ask for human confirmation or run a text recognition algorithm to see if the result makes sense.

Now this becomes harder if the direct edge of many of the shredded parts are blank, but still more then doable if you use spacing recognition(calc how big a space is in this document and look for the correspond amount of missing space on the other side), line up the text rows, and some basic word statistic (if you see "he ...", for example you are likely looking for a "T" on the right side of another strip).

Re:Confused?

[Intropy]

For N items, there are N! ways to arrange them. That doesn't make sorting an N! problem.

Huh... complex problem!?

[c0lo]

What about 600 million shreds from 45 million documents?

Problem already solved

[zazzel]

As far as I know, German Fraunhofer Institute has a solution for this kind of problem: http://www.ipk.fraunhofer.de/component/content/category/167-autsicherheitstechnikstasischnipsel (p.8ff, German language).

Looks like they have few problems assembling torn pages, and geometrically correct results for shredded paper (yet not necessarily correct content).