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

81–90 of 120 posts

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

#81

Post by nedhowley »

mgsouth wrote: 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.

"A collection, or family, of sets is considered “union-closed” if the union of any two sets in the family equals any existing set in the family." Your family isn't union closed because it doesn't include {1, 2}, the union of {1} and {2}.

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

#82

Post by SideQuark »

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…

Just took a stab at recreating my older solution. It goes something like this

Number the balls 7 8 9 10 11 12 14 15 16 17 18 19

Then do three weighings according to rows like this:

     0  1 -1  0  1 -1  1 -1  0  1 -1  0
     1  1 -1 -1 -1  0  0  1  1  1 -1 -1
    -1 -1  0  0  0  0  0  0  0  0  1  1
Where -1 means index on left side of of balance, 0 means not on balance, 1 means on right side of balance. Note each row has the same number of -1 and 1.

If left is heavy, record 0, else if balanced, record 1, else if right heavy, record 2.

Then the base 3 value gives the coin label above (in absolute value) and is >0 if heavier, else is -1 if lighter.

Also note there is no if/then. You simply follow these three and record the numbers which spit out the answer.

The idea is the matrix represents an error correction code in base 3. You need each column distinct, and coin j being out of whack selects column j from the matrix.

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

#83

Post by balsam »

jihadjihad wrote: post #30
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.

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.

The randomized version of nerd-sniping, nerd-bombing.

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

#84

Post by recursive »

geenew wrote: post #53
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…

I'm amazed that there was an episode of a popular TV drama aired that had such a detailed puzzle in it.

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

#85

Post by vgb2k18 »

thaumasiotes wrote: post #51
vgb2k18 wrote: post #49

Earlier quoted context omitted.

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

Sorry, yes I saw your confusion. If you read back to your Huh comment you might forgive me for reading it as that you were unsure of the truth yourself. The one word 'huh?', spoke to me as "which one of these is true?". Whereas a person who was sure of the true answer, I would expect to say "Hey that's incorrect", if they encountered an obviously mistaken quote.

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

#86

Post by 11101010001100 »

SideQuark wrote: post #82
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…

Just took a stab at recreating my older solution. It goes something like this Number the balls 7 8 9 10 11 12 14 15 16 17 18 19 Then do three weighings according to rows like this: 0 1 -1 0 1 -1 1 -1 0 1 -1 0 1 1 -1 -1 -1 0 0 1 1 1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 1 1 Where -1 means index on left side of of balance, 0 means not on balance, 1 means on right side of balance. Note each row has the same number of -1 and 1. If…

Does this still work if I mislabel the balls to begin with?

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

#87

Post by chaps »

moritonal wrote: post #44
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 ).

Oh lordy, same. I personally can't wait for someone else to solve it.

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

#88

Post by bloppe »

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…

I would say that studying history is almost defined by rote memorization. Once a pattern emerges, you're not studying pure history but rather historical economics or sociology or something else. Things don't usually fit neatly into pure categories but I can imagine well written tests for pretty much any subject that require extrapolation or speculation of some kind, except "pure history".

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

#90

Post by expensive_news »

SideQuark wrote: post #82
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…

Just took a stab at recreating my older solution. It goes something like this Number the balls 7 8 9 10 11 12 14 15 16 17 18 19 Then do three weighings according to rows like this: 0 1 -1 0 1 -1 1 -1 0 1 -1 0 1 1 -1 -1 -1 0 0 1 1 1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 1 1 Where -1 means index on left side of of balance, 0 means not on balance, 1 means on right side of balance. Note each row has the same number of -1 and 1. If…

I like how simple the deciding process becomes but I’m afraid there might be a problem. This solution works when the odd ball is always heavier, but it could either be heavier or lighter, and you don’t know which.

For example, say ball 7 is heavier. From top to bottom, the weightings would result in: 120. However, if ball 19 was lighter you would obtain the same weighing sequence 120.

I believe that there is another condition that must be imposed on the matrix - namely, the column must be unique, but also -1*column must not be another column.

I created the following matrix, which can identify the ball and if it is heavier or lighter. However, this does not line up neatly, and would require a table to decode the output of the weighings.

-1 -1 -1 -1 1 1 1 1 0 0 0 0 -1 -1 0 1 0 -1 -1 0 1 1 0 1 0 1 -1 0 -1 1 -1 0 1 0 1 -1

For example, the sequence 001 means the first ball is heavier. The sequence 221 means the first ball is lighter. Etc.

Post reply on HN