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. A few did do it, and normally had some expletives for me afterward.
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)
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!
It seems to me like the n-th number repeats 2^n times, with 1 being in the middle of each sequence.
From this, you could get the 13th number quite easily.
Interpreting it would be a lot more difficult though.
Interestingly, normal binary has the same pattern, but with different offsets for the start of the sequence.
I bet they were frustrated. I was thinking of the various puzzles online trying to understand a sequence of numbers when I read about this, and realizing there's no way I'd ever have come up with the answer on my own.
I'd think that in all those languages, -0 == +0 tests true, though. In JavaScript even -0 === +0 tests true.
The only way to tell them apart in general is to divide by them. In some languages you might be able to type-pun and examine the bit pattern, or do things like Object.is() or whatnot.
"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."
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.
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)
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.
"that means you're not really getting any information if the beam balances"
Wrong. If it was true, that would imply that the probability of it balancing is 1, since the information you get is -log2(probability). Obviously the probability of it balancing is lower than 1, so you do get information.
Nope. It's ternary in nature. The subproblem of "You have 3 coins, one of which is lighter than the others. On a balanced scale, figure out which one is lighter in one weighing." is a good place to start. Just enumerate all 3 possible weighings and you should be able to see the correct approach.
ABC, one of them is different weight than the other two (either more or less)
Possible ways to weigh them:
A v B
A not enough information
E C is odd one out
B not enough information
A v C
A not enough information
E B is odd one out
C not enough information
B v C
B not enough information
E A is odd one out
C not enough information
AB v C
AB not enough information
E C is odd one out
C C is odd one out
AC v B
AC not enough information
E B is odd one out
B B is odd one out
BC v A
BC not enough information
E A is odd one out
A A is odd one out
In all possible ways to weight 3 coins, all have uncertainty which means you cannot deduce which is the odd one out.
Pretend you only had 3 coins. The idea is -- when you use the scale to measure 2 coins against each other -- you actually gain "information" about all three coins.
This is because there are 3 possible scenarios:
1. the biased coin is on the right side of the scale,
2. the biased coin is on the left side of the scale,
3. or the biased coin is the coin not measured (since the scale is balanced).
In essence, even though this scale only has 2 sides, you gain information proportional to having 3 sides.
Hence if we were to extend this to a scenario where you had n coins, of which one was biased and others fair, you would only need log_3 n measurements total to find the biased coin.
This idea has pretty neat applications. For example, if you wanted to prove that merge sort has a O(n log n) computational complexity, you can use this scale idea.
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.
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.
I don't think anyone ever imagined a use for imaginary numbers either, but those turned out to be quite useful for reducing dimensionality. Towards the bottom of the article it states that Donald Knuth proposed imaginary base numerical systems.
So this may eventually find a use, likely with higher-dimensional math.
Imaginary numbers were useful as soon as they were invented. They are algebraically closed, unlike the real numbers, and are required for the fundamental theorem of algebra.
The first use of negative roots was to find the (real) roots of certain polynomials. They were considered a mathemathical hack: useful, but specious on their own. And then it turned out that if you take them on their own terms, they're fantastically useful.
In addition to the other points, imaginary numbers immediately added to the representation of things we could represent. Simply rewriting existing numbers in other ways isn't all that interesting; it doesn't add anything. We already knew there's an infinite number of ways to serialize numbers to symbols. Negative base numbers don't behave differently than positive base numbers, because "negative base numbers" and "positive base numbers" are artifacts of English and don't actually exist mathematically. There are numbers, which are written in different representations, but are not actually different entities.
So there's no possible way this could be useful for "higher dimensional math" or anything, because there's no entity being added here. Higher dimensional math already uses numbers. At most there might be one or two concepts that might in some manner if you squint hard enough could be better represented by negative base numbers, but even then the positive base representation would probably still be how people actually understood it.
It will be really funny if there is some bit of new, undiscovered physics, that went undiscovered for so long just because it's best described using some esoteric maths like complex base numbers.
I recall some effort in moving from imperial measurement to metric. Reality itself does not care, but the math sure gets easier if you carefully select units.
Actually, another neat example is analog vs digital computation. your models can get very different answers. I recall some Mandelbrot guy talking about that.
> 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-integer arithmetic with Arabic versus Roman numerals; they represent exactly the same thing, but I'll bet you can compute 16 ⨉ 17, but not XVI ⨉ XXIII (without converting), in your head.