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

51–60 of 120 posts

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

#51

Post by thaumasiotes »

vgb2k18 wrote: post #49
thaumasiotes wrote: post #42

Earlier quoted context omitted.

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

Of course it can. There are 24 possible states and you get enough information to uniquely identify one of 27 states. This was already stated in the root comment.

I'm confused how the response to "you must identify whether the odd ball is heavier or lighter" can be "the key to this is realizing you don't need to know whether the odd ball is heavier or lighter, which is good because that's impossible anyway".

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

#52

Post by andrewljohnson »

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.

I always thought of bit boards in the same way, wow moment.

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

#53

Post by geenew »

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…

There's an episode of Columbo with a similar problem, expressed as: there are a number of bags. Each bag contains many gold coins. The gold coins weigh 1 ounce each. However, one bag contains fake coins, which appear the same as the real coins, but have a slightly different weight - 1.1 ounces per coin. You have a scale, which you can only use once, and you must find the bag with the fake coins.

The solution is: Take one coin from the first bag, two coins from the second bag, three coins from the third bag, etc. Weigh all of the selected coins at the same time to get a total weight. Subtract from the total weight the triangular number of the number of bags[1], in ounces. The remainder, divided by 0.1, will be the number of the bag with the fake coins.

[1] eg, for three bags, 1 + 2 + 3 = 6

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

#54

Post by TimTheTinker »

anonymousDan wrote: post #50
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…

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.

This was exactly my experience in college. I repeatedly had professors who apologized for making the test "too hard" -- i.e. all but 0-1 students failed because passing the test required a novel approach that no one (or only 1-2 brilliant students) was able to find during the time allotted.

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

#55

Post by SideQuark »

thaumasiotes wrote: post #48
actually_a_dog wrote: post #41

Earlier quoted context omitted.

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.

No, it does three. The "four" is a typing mistake. And it's provably optimal from the theory behind construction of minimal error correcting codes.

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

#56

Post by SideQuark »

polishdude20 wrote: post #47
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…

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

The traditional solutions do things like: 1) split into 4 piles A,B,C. compare A,B on the balance. 2) If they balance, bad coin in 4 in pile C can easily be found. 3) If they don't balance, you know the 4 in C are good. At this point you have to fiddle by mixing coins among piles cleverly to get more weighings. But you can do it in three total. If I recall, seomthing like one from A, three from C, versus three from B, one from C, or something like that, is the next weighing.

This type of solution requires choices and branching. Mine was nicer I think since it requires no branches, and the weighings themselves spit out the bad coin number in base 3.

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

#57

Post by SideQuark »

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'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 items have the same weight.

It's easy for 3 items, A,B,C. Remove C, A balances B, then do A,C, now all equal.

It's easy to check by hand for a few small cases.

I proved it using more advanced stuff from lin alg. But I've never found a simple solution yet.

EDIT: corrected with "equal count piles"

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

#58

Post by tmoertel »

SideQuark wrote: post #55
thaumasiotes wrote: post #48

Earlier quoted context omitted.

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

No, it does three. The "four" is a typing mistake. And it's provably optimal from the theory behind construction of minimal error correcting codes.

Ah, it looks like there's a typo in your earlier post. It currently reads: "My solution numbered the balls in base 3, then did four weighings with no if/thens..." (Emphasis mine.)

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

#59

Post by aliqot »

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.

I have 3, personally. One day.. ONE DAY.. I will make the elusive perfect deep dish crust. One family can only eat so much pizza though, so you just have to let it go. If it's gonna happen then it'll happen.
Post reply on HN