Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Google researcher, long out of math, cracks devilish problem about sets

quantamagazine.org

Post reply on HN
Print view View original

61–70 of 120 posts

Re: Google researcher, long out of math, cracks devilish problem about sets

#61

Post by weakfortress »

jobs_throwaway wrote: post #7
acctant wrote: post #2

> He also worked with a textbook by his side so he could look up formulas he’d forgotten. “You’d think someone who comes up with a great result shouldn’t have to consult Chapter 2 of Elements of Information Theory, but I did,” Gilmer said. Always enjoy seeing this sentiment reaffirmed. Funny that Gilmer states it in a somewhat self surprised tone. Rings of the Einstein quote: “[I do not] carry such information in my…

"The value of a … education is not the learning of many facts but the training of the mind to think." While anyone with a (good) STEM education knows this to be obviously true, its frightening how many people go through 16+ years of formal schooling where they mostly do rote memorization and regurgitation.

[dead]

Re: Google researcher, long out of math, cracks devilish problem about sets

#62

Post by dekhn »

tpurves wrote: post #36
chris_overseas wrote: post #29

Earlier quoted context omitted.

The obligatory XKCD https://xkcd.com/356/

Damn you! Now all I can think about is that xkcd problem.

That's taken from the Google Labs Aptitude test, IIRC it's a simplification of https://arxiv.org/abs/cond-mat/9909120 with solution here https://mathworld.wolfram.com/news/2004-10-13/google/

Re: Google researcher, long out of math, cracks devilish problem about sets

#63

Post by tester457 »

bobkazamakis wrote: post #21
tester457 wrote: post #14

Earlier quoted context omitted.

We can thank the academic system and Goodhart's Law for that. We measure students with tests, but all we get are people good at taking tests and rote memorization. Maybe if we had a better way to access actual learning but are teachers even paid enough to truly care?

>Maybe if we had a better way to access actual learning but are teachers even paid enough to truly care? There's no incentive to pay teachers more; system is working as designed. Those students aren't giving short-term quarterly gains.

Tis a shame the system doesn't account for the massive, long-term returns quality education provides, both to student and society.

Re: Google researcher, long out of math, cracks devilish problem about sets

#64

Post by SideQuark »

actually_a_dog wrote: post #41
jacquesm wrote: post #37

Earlier quoted context omitted.

That is a beautiful solution, wow. I'm just floored by you coming up with that, it is so utterly out of the box.

It is a beautiful solution, but it's not terribly out of the box. It's similar to generating all subsets of a set of N items by iterating through the integers 0..2^N - 1 and checking to see which bits are set.

All subsets requires 2^12 weighings. The beautiful thing about error correcting codes is finding a minimal set of spanning items. And in this case, binary will not suffice, since you can only distinguish 2^3 = 8 items. The third position, one most people don't think if, is the "off balance" set, which gives three choies.

Then 3 weighings, 3 choices per, gives 27 possible outcomes, which is enough to distinguish which of 12 items is off, as well as whether or not it's higher or lower in weight (another factor of 2), for 24 choices. So there is a little extra in the 3=27-24 information theoretical bounds.

Using this idea, you can generate all sorts of hard coin problems, vastly harder than this one :), by mining error correction tables like http://www.codetables.de/ and converting to word problems.

Re: Google researcher, long out of math, cracks devilish problem about sets

#65

Post by Fetiorin »

SideQuark wrote: post #57
jacquesm wrote: post #37

Earlier quoted context omitted.

That is a beautiful solution, wow. I'm just floored by you coming up with that, it is so utterly out of the box.

It's not out of the box when I apply error correcting codes to a massive range of problems ;) If you like cool problems, here is one I have not found a simple solution for, but I once saw it in a place where a simple solution should exist. You have an odd number >=3 of items with the property that any time you remove one, there is a way to split the remaining items into two equal count piles of equal weight. Show all…

I'm not sure I get the problem.

For number 5, I can use items of weights 3 1 1 1 1 and they are not equal. If you remove 3, you get 1+1=1+1 and in case you remove only of 1s, you can split 3 = 1+1+1.

Re: Google researcher, long out of math, cracks devilish problem about sets

#66

Post by fizzynut »

rkp8000 wrote: post #9

Always cool to see unexpected applications of information theory, especially outside of probabilistic contexts. A related toy example that comes to mind is the puzzle where you're given 12 metal balls and told that one of them is either heavier or lighter than the rest. You're then given a balance/scale and instructed to figure out which ball is different and whether it is heavier or lighter using the balance a maxim…

I'm not sure why you say it won't work with 14 balls, this is solvable with up to 27 balls in 3 weighs.

Weigh 1: 9 vs 9 (18 on balance), 9 off

Weigh 2: 3 vs 3 (6 on balance ), 3 off

Weigh 3: 1 vs 1 (2 on balance ), 1 off

Re: Google researcher, long out of math, cracks devilish problem about sets

#67

Post by zem »

SideQuark wrote: post #57
jacquesm wrote: post #37

Earlier quoted context omitted.

That is a beautiful solution, wow. I'm just floored by you coming up with that, it is so utterly out of the box.

It's not out of the box when I apply error correcting codes to a massive range of problems ;) If you like cool problems, here is one I have not found a simple solution for, but I once saw it in a place where a simple solution should exist. You have an odd number >=3 of items with the property that any time you remove one, there is a way to split the remaining items into two equal count piles of equal weight. Show all…

I remember that problem from my college linear algebra course! I found a nice simple proof for integers (which was very satisfying!) but afaik you do need heavy linear algebra machinery to generalise it to the reals.

Re: Google researcher, long out of math, cracks devilish problem about sets

#68

Post by hello_hny »

fizzynut wrote: post #66
rkp8000 wrote: post #9

Always cool to see unexpected applications of information theory, especially outside of probabilistic contexts. A related toy example that comes to mind is the puzzle where you're given 12 metal balls and told that one of them is either heavier or lighter than the rest. You're then given a balance/scale and instructed to figure out which ball is different and whether it is heavier or lighter using the balance a maxim…

I'm not sure why you say it won't work with 14 balls, this is solvable with up to 27 balls in 3 weighs. Weigh 1: 9 vs 9 (18 on balance), 9 off Weigh 2: 3 vs 3 (6 on balance ), 3 off Weigh 3: 1 vs 1 (2 on balance ), 1 off

You don't know if the unique ball is heavier or lighter, how would this work?

Re: Google researcher, long out of math, cracks devilish problem about sets

#69

Post by fizzynut »

hello_hny wrote: post #68
fizzynut wrote: post #66

Earlier quoted context omitted.

I'm not sure why you say it won't work with 14 balls, this is solvable with up to 27 balls in 3 weighs. Weigh 1: 9 vs 9 (18 on balance), 9 off Weigh 2: 3 vs 3 (6 on balance ), 3 off Weigh 3: 1 vs 1 (2 on balance ), 1 off

You don't know if the unique ball is heavier or lighter, how would this work?

Ah, if you need to know that for certain then you'd be restricted to 18 balls (6,6,6), (2,2,2), (1,1). Otherwise I guess you would "only" know in 26/27 cases if it was heavier or lighter (off the balance in all 3 conditions).

....and now I understand, you would only initially know there is a difference in weight, not which side had the heavier or lighter ball.

Re: Google researcher, long out of math, cracks devilish problem about sets

#70

Post by thaumasiotes »

zem wrote: post #67
SideQuark wrote: post #57

Earlier quoted context omitted.

It's not out of the box when I apply error correcting codes to a massive range of problems ;) If you like cool problems, here is one I have not found a simple solution for, but I once saw it in a place where a simple solution should exist. You have an odd number >=3 of items with the property that any time you remove one, there is a way to split the remaining items into two equal count piles of equal weight. Show all…

I remember that problem from my college linear algebra course! I found a nice simple proof for integers (which was very satisfying!) but afaik you do need heavy linear algebra machinery to generalise it to the reals.

> I found a nice simple proof for integers (which was very satisfying!)

But no such proof can exist because the claim is not true. When you posted your comment, Fetiorin had already given a counterexample.

Post reply on HN