Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Negative Base

en.wikipedia.org

Post reply on HN
Print view View original

31–40 of 74 posts

Re: Negative Base

#31

Post by msoucy »

bhrgunatha wrote: post #24
msoucy wrote: post #15

When I was part of an organization in college, part of the onboarding process was that each applicant had to have a conversation and (possibly) do a "quest" for each member. My standing quest was that I would write the first 12 or so numbers in negabinary on my whiteboard, and have them determine the next few numbers and explain what they meant. I had people sitting outside my room for hours trying to figure it out.…

Looking at the table is bad enough, but I imagine most people looking would think "Aaah binary" and convert to decimal: 1, 6, 7, 4, 5, 26, 27, 24, 25, 30, 31, 28... That's cruel :)

I probably got a little too much sadistic pleasure out of it, yes...

However, I was always willing to answer nontrivial questions, and even convert numbers to/from negabinary to help them. (The program used the Schroeppel2 implementation, to prevent them from getting too much of a clue if they somehow managed to find its source code)

Re: Negative Base

#32

Post by philbarr »

TrinaryWorksToo wrote: post #26
catpolice wrote: post #22

Earlier quoted context omitted.

Hoo, that's one of my favorite puzzles - there was a version of it on Brooklyn Nine-Nine with no solution given, which ruined my sleep that night. I have a theory that it's actually a little harder for programmers than for other technically inclined people because the instinct to treat it as a kind of binary search problem is really hard to shake.

Is it not a binary search problem?

Not really - you can reduce it to one but you don't quite have enough information.

So I think it goes like this:

- you have 12 coins, and each one has an equal chance of being heavier or lighter than the others - so that's 24 possiblities

- you have 3 moves, and the result of each move could be one side of the beam goes down, one side goes up, or it balances. That means you can create a system that identifies 3^3 = 27 outcomes. So far so good.

- you need each of your outcomes to provide real information. if it was a binary problem that means you're not really getting any information if the beam balances

(bit sketchy on that last point, maybe someone can help with that)

Re: Negative Base

#33

Post by catpolice »

TrinaryWorksToo wrote: post #26
catpolice wrote: post #22

Earlier quoted context omitted.

Hoo, that's one of my favorite puzzles - there was a version of it on Brooklyn Nine-Nine with no solution given, which ruined my sleep that night. I have a theory that it's actually a little harder for programmers than for other technically inclined people because the instinct to treat it as a kind of binary search problem is really hard to shake.

Is it not a binary search problem?

Traditionally binary search involves recursively dividing the options into two roughly equal sized groups and then using a measurement to rule out every member of one of the groups (and thus half of the search space) with every step. The solution to this problem differs from that approach in certain key ways.

It is a kind of search problem, but the steps aren't recursive and you have to use several tricks to maximize the information you get out of each measurement.

Re: Negative Base

#34

Post by [deleted] »

TrinaryWorksToo wrote: post #26
catpolice wrote: post #22

Earlier quoted context omitted.

Hoo, that's one of my favorite puzzles - there was a version of it on Brooklyn Nine-Nine with no solution given, which ruined my sleep that night. I have a theory that it's actually a little harder for programmers than for other technically inclined people because the instinct to treat it as a kind of binary search problem is really hard to shake.

Is it not a binary search problem?

[deleted]

Re: Negative Base

#35

Post by catpolice »

philbarr wrote: post #32
TrinaryWorksToo wrote: post #26

Earlier quoted context omitted.

Is it not a binary search problem?

Not really - you can reduce it to one but you don't quite have enough information. So I think it goes like this: - you have 12 coins, and each one has an equal chance of being heavier or lighter than the others - so that's 24 possiblities - you have 3 moves, and the result of each move could be one side of the beam goes down, one side goes up, or it balances. That means you can create a system that identifies 3^3 = 2…

Yeah, the reason I suspect it tends to thwart programmers (if I recall correctly) is that there's a solution that looks a lot like binary search that _almost_ works, but the actual solution looks very different from it at every step. So the programmer will start with the one that looks like binary search, realize that it provides almost enough information, and try to squeeze a little more out of it by modifying it in little ways, when they sort of need to go back to the drawing board instead.

Re: Negative Base

#37

Post by JadeNB »

scentoni wrote: post #29
JadeNB wrote: post #23

Earlier quoted context omitted.

> There are lots of ways to represent numbers but they don’t change the thing they represent. Different representations of the same thing are not useless; one might make an argument (which I can only back up off the top of my head with mathematical examples, but I suspect that there are also many in the physical sciences) that they are at the root of much progress. The canonical example is to try to do positive-integ…

XVI ⨉ XXIII = XVI ⨉ (XVI + I) = (XVI ⨉ XVI) + XVI = CCLVI + XVI = CCLXXII

I didn't say that it wasn't computeable, only that I bet you couldn't do it in your head.

Note that your calculation for some reason (EDIT: ah, maybe because my Arabic-numeral problem has 16 ⨉ 17?) replaces XXIII = 23 by XVII = 17, and then black-boxes the calculation XVI ⨉ XVI = CCLVI (which I at least wouldn't know without converting).

Re: Negative Base

#38

Post by gkfasdfasdf »

philbarr wrote: post #18
Sharlin wrote: post #10

See also balanced ternary [1]. [1] https://en.wikipedia.org/wiki/Balanced_ternary

Which you can use to solve the puzzle: "You have 12 coins that all look exactly the same. One is counterfeit and is either heavier or lighter than the other 11. With a balance beam scale, isolate the counterfeit coin in three moves." Any uses for Negative-base systems?

I'm going to have to take this riddle bait. My solution:

Move 1: weigh 6 coins vs 6 coins. Isolate the heavier set for the next move. Move 2: weigh 3 coins vs 3 coins. Isolate the heavier set for the next move. Move 3: weigh any two of the 3 remaining coins. If one is heavier, that is the counterfeit. Otherwise (if coins are equal in weight) the remaining coin is counterfeit.

Re: Negative Base

#39

Post by soVeryTired »

msoucy wrote: post #15

When I was part of an organization in college, part of the onboarding process was that each applicant had to have a conversation and (possibly) do a "quest" for each member. My standing quest was that I would write the first 12 or so numbers in negabinary on my whiteboard, and have them determine the next few numbers and explain what they meant. I had people sitting outside my room for hours trying to figure it out.…

Looking at the sequence of negabinary representations, I could imagine (with the benefit of hindsight) that it wouldn't be too hard to guess the next numbers in the sequence. You'd just need to make a few observations: the rightmost digit always flips from 1 to 0. The second digit from the right reads one twice, then zero twice, etc. When you increase the length of the sequence, add two leading ones.

I'm not sure those would be enough, but just inspecting the digit-wise patterns would get you pretty far. Correctly interpreting the sequence is far harder!

Re: Negative Base

#40

Post by ythn »

gkfasdfasdf wrote: post #38
philbarr wrote: post #18

Earlier quoted context omitted.

Which you can use to solve the puzzle: "You have 12 coins that all look exactly the same. One is counterfeit and is either heavier or lighter than the other 11. With a balance beam scale, isolate the counterfeit coin in three moves." Any uses for Negative-base systems?

I'm going to have to take this riddle bait. My solution: Move 1: weigh 6 coins vs 6 coins. Isolate the heavier set for the next move. Move 2: weigh 3 coins vs 3 coins. Isolate the heavier set for the next move. Move 3: weigh any two of the 3 remaining coins. If one is heavier, that is the counterfeit. Otherwise (if coins are equal in weight) the remaining coin is counterfeit.

You failed because:

> One is counterfeit and is either heavier or lighter

It turned out the counterfeit was lighter and you discarded it after the first weighing.

Post reply on HN