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

111–120 of 120 posts

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

#111

Post by SideQuark »

garfieldnate wrote: post #99
SideQuark wrote: post #82

Earlier quoted context omitted.

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…

Why do the balls have to be numbered starting at 7?

There's a few hundred sets of numbers that work, but none are the sequence 1,2,..,12 or so, due to needing balanced left and right weighings. To see this, write the base 3 values for 1,2,..,12 as columns, and count the number of each digit in each row - you need equal numbers of 0 and 2 per row to make a valid weighing.

Here I picked the above since it is a valid sequence, but fails for the reason elsewhere on this page - you also need to not have negative paired columns. And that too turns out to not be enough, so write a simple program and crunch to check each case that does work, and there's (I think) 304. I should stop poking at this as I have real work I should be doing :)

If you really want to clean it up, you could then map the answer 3-vector of scrambled -1,0,1 values into another decoder matrix to map into values you like. Or use a look up table.

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

#112

Post by SideQuark »

thaumasiotes wrote: post #101
garfieldnate wrote: post #99

Earlier quoted context omitted.

Why do the balls have to be numbered starting at 7?

I'm a different person, but I can provide some commentary about that. A. There are many ways to identify the misweighted ball in three deterministic weighings. The simple approach is to label the possible states 1 to 24, or alpha to omega, or what have you, and then to assign an outcome code to each state. SideQuark wants to entwine the outcome codes with the state labels, so that the label for each state is the valu…

>It is not clear to me how we would get a negative number.

Use base 3 with 'digits' -1,0,1.

It's useful and interesting to note you can uniquely encode and decode any integer in any base with 'shifted' digits. If you allow some digits to be positive and some negative, you get both positive and negative integers encoded for free without needing sign extraction, using standard algorithms. You can also change base per slot and go into mixed-radix tricks for encoding (useful for turning things with varying choices per slot into unique encodings).

Things look like

    Encode(int val, int base, int shift)
        while (val != 0)
            d = ((val%b)+b)%b; // get positive mod 'digit'
            if (d + shift >= b) d = d-b; // shift digits
            val -= d; // kill off low digit - often not done in positive only case
            val /= d;
            output(d)

   Decode (list of digits, int base, int shift)
        val = 0
        reverse digits
        foreach digit d
           val = val * b + d
        return val
with positive shift, this encodes and decodes positive and negative integers in any base correctly, and works like the normal postive only case.

digits -1,0,1 also makes a unique base 3 representation of any integer using the same encoding and decoding algorithms. In fact, you can shift digits in any base like this and still get unique encoding and decoding, with the benefit that they handle positive and negative numbers for free.

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

#113

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.

Thinking on this on my drive, I recalled another puzzle you might like with another error corrected solution.

The puzzle is related to the game 20 questions. If you can ask only 20 yes/no questions, you can differentiate 2^20 items. For example, with 20 yes/no questions, you can determine an integer in 1 to 1,000,000 (technically, up to 2^20).

Now consider you need to figure out what integer between 1 and 1,000,000 I am think of, but I am allowed to lie at most once. Now how many questions will you need to ensure you get the answer?

Doing this by hand and creating more and more convoluted tricks is possible, but in reality this is another error correction problem: The original problem is a binary message of length 20 bits, from which you get the 20 bit message.

With at most one lie, there is a 20 bit message, me (the noisy channel) can add at most one error, so you need the minimal length binary code that takes a message of length 20 and a max error of 1 bit.

To find the number needed, use a coding table like http://www.codetables.de/.

So you need to find how many more bits you need. To fix d bits, you need 2d+1 'distance' in your code to make sure d errors do not move one valid point within Hamming distance d of another answer, so we need d = 3.

So you need a binary code, d = 3, and encoding a message of length k=20. Click on Linear Codes, then the GF2 button, and you see the big table of best codes. Find the column with k = 20 (our message length), scroll down over increasing n (number of questions needed), until the first d=3 entry. There n = 25, so 25 questions will do it. This is the result http://www.codetables.de/BKLC/BKLC.php?q=2&n=25&k=20

This is provably best, otherwise the table would have a range if there were not proof (look around the table, notice some are ranges).

To design the questions, most places with tables have code constructions. So click the entry, and they describe the construction (unfortunately in error correction code terms), but that can be reversed into English and actual questions to get your answer.

This technique would let you answer any problem along the line of "How many questions, each with b options, would it take to determine between N items, if there are at most d lies told?"

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

#114

Post by zem »

hgsgm wrote: post #102
zem wrote: 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.

Why doesn't the integer proof work on reals?

it relied on modular arithmetic

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

#115

Post by jacquesm »

SideQuark wrote: post #113
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.

Thinking on this on my drive, I recalled another puzzle you might like with another error corrected solution. The puzzle is related to the game 20 questions. If you can ask only 20 yes/no questions, you can differentiate 2^20 items. For example, with 20 yes/no questions, you can determine an integer in 1 to 1,000,000 (technically, up to 2^20). Now consider you need to figure out what integer between 1 and 1,000,000 I…

Interesting! Intuitively I would have had the answer right but I have no idea where that bit of info popped up from. Possibly something to do with SDLC or some other telecommunications protocol that I worked with or implemented the drivers for.

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

#116

Post by polishdude20 »

hgsgm wrote: post #103
SideQuark wrote: post #56

Earlier quoted context omitted.

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…

There's a slightly simpler solution if you don't care whether the odd ball is lighter or heavier: It's: X. AAAA vs BBBB If X was balanced, XX: C1 vs C2, then XXX: C2 vs C3 (general way to distinguish 2 unknowns: weigh one unknown against one known) If X was unbalanced, WLOG assume A was heavier. XY: A1 A2 B1 vs A3 A4 B2 Then if XY balanced, use the general method to distinguish B3 or B4 as answer. If XY unbalanced, W…

What is C1 and C2 and C3?

What is XY? What's WLOG?

Can you dumb this down a bit more please?

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

#117

Post by thaumasiotes »

SideQuark wrote: post #112
thaumasiotes wrote: post #101

Earlier quoted context omitted.

I'm a different person, but I can provide some commentary about that. A. There are many ways to identify the misweighted ball in three deterministic weighings. The simple approach is to label the possible states 1 to 24, or alpha to omega, or what have you, and then to assign an outcome code to each state. SideQuark wants to entwine the outcome codes with the state labels, so that the label for each state is the valu…

>It is not clear to me how we would get a negative number. Use base 3 with 'digits' -1,0,1. It's useful and interesting to note you can uniquely encode and decode any integer in any base with 'shifted' digits. If you allow some digits to be positive and some negative, you get both positive and negative integers encoded for free without needing sign extraction, using standard algorithms. You can also change base per s…

I'll look into this more later, but right now it's bothering me that (a) your writeup specifies that the digits of the result code are drawn from 0/1/2 [a minor issue]; and (b) the minimum number representable in three digits of base 3 where the digits are -/0/+ is ---, -9 + -3 + -1 = -13, which will make the results -14 through -19 unreachable. The same problem occurs on the other side, where the maximum result is +++, positive 13.

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

#118

Post by thaumasiotes »

SideQuark wrote: post #112
thaumasiotes wrote: post #101

Earlier quoted context omitted.

I'm a different person, but I can provide some commentary about that. A. There are many ways to identify the misweighted ball in three deterministic weighings. The simple approach is to label the possible states 1 to 24, or alpha to omega, or what have you, and then to assign an outcome code to each state. SideQuark wants to entwine the outcome codes with the state labels, so that the label for each state is the valu…

>It is not clear to me how we would get a negative number. Use base 3 with 'digits' -1,0,1. It's useful and interesting to note you can uniquely encode and decode any integer in any base with 'shifted' digits. If you allow some digits to be positive and some negative, you get both positive and negative integers encoded for free without needing sign extraction, using standard algorithms. You can also change base per s…

All right; I've done some more looking.

Shifting the digits is exactly equivalent to biasing the number; in this case, changing the interpretation of the graphical symbols "0", "1" and "2" to be the numeric values -1, 0, and 1 just means we subtract trinary 111 = decimal 13 from our three-digit value. So we could represent the value -4 as "0--" (in "shifted trinary") or we could represent it as "100" (in biased trinary, since 9-13 = -4) and those representations are glyph-to-glyph isomorphic. Since the representable range of three digits of ordinary trinary is 0-26, the representable range using three of these shifted digits is -13 to +13.

Using this -/0/+ representation, it is easy to state a weighing schedule in which the absolute value of the three trinary digits you get as output from the scale represent equals the label (1-12) of the misweighted ball.[1]

But it appears to be impossible for the representation to be positive whenever the ball is heavy and negative whenever the ball is light.

Let's assume that we record a - when the scale tips right and a + when the scale tips left.

The problem is that every time we do a weighing, there will be at least one ball on each side of the scale. (Or else the weighing would generate zero information.) So without loss of generality, there is a ball L on the left of the weighing which gives us our most significant digit, and a different ball R on the right of the same weighing.

Since we record a - when the scale tips right, our most significant digit will be -, and therefore our overall result will be negative, whenever ball R is heavy. This conflicts with your stated goal of having the result be positive whenever any ball is heavy.

This will make it difficult to design an algorithm to diagnose the ball that doesn't involve any branches - we can "branchlessly" (to the extent taking an absolute value doesn't branch) determine which ball is misweighted, but we need a branch (or a lookup table) to determine whether it's light or heavy.

[1] This will do the job:

    6 8 10 11  vs  5 7 9 12
    3 5  7 11  vs  2 4 6 12
    1 2  5 10  vs  4 7 8 11
Record 0 when the scale balances, and otherwise plus or minus 1. The magnitude of the result will always equal the value of the misweighted ball, but the meaning of the sign is different for balls 2, 4, 5, 7, 9, and 12 (which have their first appearance on the right) than it is for balls 1, 3, 6, 8, 10, and 11 (which have their first appearance on the left).

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

#119

Post by thaumasiotes »

expensive_news wrote: post #90
SideQuark wrote: post #82

Earlier quoted context omitted.

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…

I don't understand how SideQuark is distinguishing negative results from positive results. But using the representation he suggested to me sidethread, it isn't possible to have the result be positive whenever the misweighted ball is heavy and negative whenever it's light.

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

#120

Post by terminal_d »

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…

Isn't that overcomplicating the solution?

The only requirement is to have a unique number of coins from the fake coin pouch. Since we don't know which one that is, every pouch gets a different number of coins, and not necessarily a sequence starting from 1. Then, you weigh them all assuming they're all real, but wait, they're not! So you take the excess weight, divide it by the excess weight per fake coin, and the bag from which you took out that many coins is the bag with the fake coins.

Post reply on HN