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

41–50 of 120 posts

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

#41

Post by actually_a_dog »

jacquesm wrote: post #37
SideQuark wrote: post #26

Earlier quoted context omitted.

I once made a cool solution to this problem using information theory, in particular coding theory. The usual solution uses the fact there are 3 places to put items: left scale, off scale, and right scale. Then those solutions do if/then cases to juggle items around to find the mis-weighted ball. My solution numbered the balls in base 3, then did four weighings with no if/thens,. The weightings each gave a base 3 resu…

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.

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

#42

Post by thaumasiotes »

koolba wrote: post #18
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…

The 12-ball problem is a fun one and IMO the key revelation is that you do not need to determine whether the ball is lighter or heavier (which isn’t possible anyway). Just which ball is different than the rest. It’s a great exercise in decision trees as you change your strategy based on total information, not just the most recent step. It’s also fun to scale the problem from 3 balls up to see how the solution evolves…

>> 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 maximum of three times

> The 12-ball problem is a fun one and IMO the key revelation is that you do not need to determine whether the ball is lighter or heavier (which isn’t possible anyway).

Huh?

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

#43

Post by jobs_throwaway »

Someone wrote: post #33
jobs_throwaway wrote: post #17

Earlier quoted context omitted.

Tests have their place though. The more rigorous maths exams I took in school were some of the most intellectually challenging things I did in school. If written correctly, they require you to apply the things you've learned in novel ways, or to combine the topics you've studied in new ways. Problem is, IME there's very few professors/teachers qualified and devoted enough to develop those sorts of exams, and as soon…

I think math is somewhat special in that it isn’t about solving specific problems, but about learning to recognize patterns, and that the tests don’t check whether they know the patterns, but whether they can apply those patterns to problems that they need not even have ever seen. In many other disciplines applying what students learned to things they’ve never seen before isn’t really possible. For example, you can t…

You make a good point. I believe that there are ways to get students outside of maths to apply what they've learned to things they haven't seen before, though it won't be as novel or challenging as a maths exam. In history for example, you could have students analyze primary sources they've never encountered, which would require them to apply their knowledge of the context to something novel. Definitely more challenging than in STEM though.

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

#44

Post by moritonal »

thethirdone wrote: post #13

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

Yep, same. About once a year I get sucked for a day or so into the Noita Eye Messages puzzle (https://noita.fandom.com/wiki/Eye_Messages).

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

#45

Post by mkoubaa »

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…

I do not carry such information in my mind since it is readily available on stack overflow

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

#46

Post by LAC-Tech »

thethirdone wrote: post #13

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

Just do what I do, focus on easy problems! Doesn't take that long but you feel great anyway.

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

#47

Post by polishdude20 »

SideQuark wrote: post #26
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 once made a cool solution to this problem using information theory, in particular coding theory. The usual solution uses the fact there are 3 places to put items: left scale, off scale, and right scale. Then those solutions do if/then cases to juggle items around to find the mis-weighted ball. My solution numbered the balls in base 3, then did four weighings with no if/thens,. The weightings each gave a base 3 resu…

Can you explain how you weigh the balls? How many do you weigh at a time and how do you decide which ones to weigh? I'm trying to follow your solution but I'm confused about this one thingn

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

#48

Post by thaumasiotes »

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.

As stated, it's not a solution at all - it uses four out of three possible weighings.

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

#49

Post by vgb2k18 »

thaumasiotes wrote: post #42
koolba wrote: post #18

Earlier quoted context omitted.

The 12-ball problem is a fun one and IMO the key revelation is that you do not need to determine whether the ball is lighter or heavier (which isn’t possible anyway). Just which ball is different than the rest. It’s a great exercise in decision trees as you change your strategy based on total information, not just the most recent step. It’s also fun to scale the problem from 3 balls up to see how the solution evolves…

>> 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 maximum of three times > The 12-ball problem is a fun one and IMO the key revelation is that you do not need to determine whether the ball is lighter or heavier (which isn’t p…

If I'm reading this [0] right, the heavier/lighter factor can be determined within 3 weightings... [0] https://suresolv.com/brain-teaser/find-fake-ball-among-12-id...

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

#50

Post by anonymousDan »

jobs_throwaway wrote: post #17
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?

Tests have their place though. The more rigorous maths exams I took in school were some of the most intellectually challenging things I did in school. If written correctly, they require you to apply the things you've learned in novel ways, or to combine the topics you've studied in new ways. Problem is, IME there's very few professors/teachers qualified and devoted enough to develop those sorts of exams, and as soon…

Writing a hard/challenging exam is not difficult. The problem is most bad or even average students will fail. The tricky part is striking a balance such that the good students feel pushed, and the weaker students still have a chance to demonstrate they at least engaged and understand the basics.
Post reply on HN