Live data from Hacker News

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

quantamagazine.org

71–80 of 120 posts

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

#71

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'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.

And this generalizes - if n = 2k + 1, 2k times x and once (2k - 1)x can be split into twice kx after removing the single (2k - 1)x or twice (2k - 1)x after removing one x. For k = 1, i.e. n = 3, (2k - 1)x = x. So there is an infinite family of counter examples for all odd n > 3.

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

#72
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…

carry such information in my mind since it is readily available in books.

It depends...good luck doing math if you don't have a good grasp of arithmetic . Having to look up everything would be a major chore.

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

#73
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…

[deleted]

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

#74

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'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.

Ah, problem is in memory. Probably also needs two piles of equal number of items :)

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

#75
post #67

Earlier quoted context omitted.

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.

I was pulling the problem from memory. Add the requirement boths sides are same number of items.

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

#76

> “Mike said, ‘Justin, you’re going to get me thinking about this problem again and I don’t want to do that,’” said Gilmer. This is a very relatable feeling. I often find myself getting trapped into thinking about problems I am unlikely to solve.

Reminds me of the multi-armed bandit problem, where Allied scientists considered it to be so intractable that they proposed dropping it over Germany so their scientists would waste their time on it.

[deleted]

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

#77
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…

It's just coy self-deprecation. A smart guy who's spent a few years in a corporate environment probably knows when to deploy it.

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

#78
What am I not getting? Isn't family {1}, {2}, {3}, {4}, {1, 2, 3, 4} union-closed? Each element appears in only 2/5 of the sets, so ???

Edit: From the paper, the family F is defined as "F ⊆ (subset or equal) 2^n". I think that means for n elements there are at most 2^n subsets? In other words, no duplicated subsets. Which still doesn't clear up my confusion--5 subsets is Edit: Duh, thanks for correcting my thinko.

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

#79
post #78

What am I not getting? Isn't family {1}, {2}, {3}, {4}, {1, 2, 3, 4} union-closed? Each element appears in only 2/5 of the sets, so ??? Edit: From the paper, the family F is defined as "F ⊆ (subset or equal) 2^n". I think that means for n elements there are at most 2^n subsets? In other words, no duplicated subsets. Which still doesn't clear up my confusion--5 subsets is Edit: Duh, thanks for correcting my thinko.

{1} U {2} = {1,2} and is not in the family.

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

#80
post #78

What am I not getting? Isn't family {1}, {2}, {3}, {4}, {1, 2, 3, 4} union-closed? Each element appears in only 2/5 of the sets, so ??? Edit: From the paper, the family F is defined as "F ⊆ (subset or equal) 2^n". I think that means for n elements there are at most 2^n subsets? In other words, no duplicated subsets. Which still doesn't clear up my confusion--5 subsets is Edit: Duh, thanks for correcting my thinko.

[deleted]
Post reply on HN