Some fun mathematical puzzles | Hacker News Reader

Some fun mathematical puzzles

research.microsoft.com

84 pointskamechan51 comments

"Age of childen" is fun because at first you stumble over the hint with the oldest child playing piano and wonder how that could have anything to do with the children's ages.

So, there are three kids and the product of their ages is 36. Assuming that ages are integers, this gives us the following possibilities:

    (a) 1 1 36
    (b) 1 2 18
    (c) 1 3 12
    (d) 1 4 9 
    (e) 1 6 6 
    (f) 2 2 9
    (g) 2 3 6 
    (h) 3 3 4

The sum of their ages is the neighbor's house number. So let's see what the above age distributions sum up to:

    (a) 38
    (b) 21
    (c) 16
    (d) 14
    (e) 13
    (f) 13
    (g) 11
    (h) 10

The fact that the insurance agent still doesn't know the answer after returning from the neighbor's house means that it must be either (e) or (f) as those are the only two possibilities that sum up to the same value and thus are ambiguous.

But then the mother mentions that her oldest kid plays the piano, and of course it's not so much the piano that gives us the hint, but the fact that she has one oldest kid: in (e) there would be two oldest kids.

Therefore the answer is (f): two of the kids are 2 and one is 9 years old.

Even with twins one is older than the other.

but the ages are expressed as integers so in the domain of the problem, twins are exactly as old as each other.

Cutting cheese (start with a 3x3x3 cube of cheese and a knife, how many straight cuts at minimum are needed to turn it into 27 1x1x1 cubes?):

The obvious answer is 6, by cutting it the obvious way (2 parallel slices along each dimension at the appropriate locations), so that seems almost certainly wrong.

If the cheese remains convex, any straight cut can at most double the number of pieces of cheese, so it would be impossible to do in less than 5 cuts (2^4 = 16, which just can't give us enough pieces, whereas 2^5 = 32 does). That holds only if we can assume convexity, but for the purposes of the problem, I assume the cheese isn't bendable or anything like that, in which case any set of straight slices you could do to make cheese non-convex would be "wasting" cuts (to maximize cheese-block count, you should always cut all the way through along a plane, and you'll only end up with convex pieces that way).

We might be tempted to go out on a limb and say that it must take 5 cuts, otherwise the problem isn't very interesting.

Unfortunately, we'd be wrong.

Think about the center piece of cheese in the 3x3x3 block. None of its faces are exposed in the original block, and there are six faces, none of which are coplanar. Unless we cheat pretty seriously (bending cheese), we cannot expose more than one of those faces with each cut, so there's no way to do it in less than six slices.

The difficulty of these is all over the map. Possibly the most difficult one is "Opening boxes in a prison courtyard". If you can solve this without any hints or help, and by solving it I mean working out a strategy that gives prisoners at least 30% chance of surviving, then you just may be a genius. Or at least very, very smart.

POTENTIAL SPOILER

You only have to think in terms of permutations, which always break up into cycles. How is this especially hard?

Anyone know how to do "Catching a spy"? Attempting it with someone I regard as a very good thinker; he is pretty adamant that it doesn't give enough information.

It can be done. Imagine a two dimensional array. One dimension corresponds to A and the other to B. Each cell in the array, corresponds to one possibility of the values of A and B.

At a time X, the spy is in a position (A+BX). At each time you pick a cell, and then guess the position associated with the A and B values of that cell. So for example, at time zero, you can pick cell (1, 1) which corresponds to position 1+0x1=1. So you guess 1. Then at time 1 you can pick cell (1,2), which corresponds to position 1+2x1=3. So you guess 3.

Every time you make a wrong guess, you cross out the cell associated with your guess. But you also cross out all cells which would have resulted in the erroneous position you picked. Thus, taking the above example, at time 1, you cross out the cell you tried (cell (1,2)) as well as all other cells that would have resulted in position 3 at time 1. These include cell (2,1), cell (-2, 5), cell (10, -7) etc.

In general, if your guess at time X is Y, you cross out all cells (A,B) such that A+BX=Y.

Every time you make a new guess you just have to make sure that your guess is associated with a cell that you have not crossed out. Since A and B are finite numbers, eventually you will catch the spy.

Now there are a couple of wrinkles. One is, "doesn't the array need to be infinite for this to work?" The answer is not really. You can grow the array as you keep guessing. Eventually you will guess the right number and at that time the array will still be finite, because the A and B you guessed were finite.

The other wrinkle is: "isn't the number of cells you are supposed to cross out each turn infinite?" That can be avoided as well. You can keep a finite array and only cross out the cells in the array. But also store a history of wrong guesses. Whenever you cross out every cell in the array, you grow the array by increasing its bounds. Then you look at your history and cross off any of the new cells in the grown array that are associated with any of your previous wrong guesses.

Hope this helps.

nice.

As I read the problem, what we need is a mapping of the integers (not reals) to guesses that will cover all (A,B) possibilities.

To solve it, we basically need to specify an ordering of guesses, one after another, covering all possibilities. Or equivalently, we want a function that takes the (integer) time and returns a guess, and will return all needed guesses as time goes to infinity.

Orderings are very important when dealing with infinities. If you just start by guessing things of the form 0,T as time goes to infinity, planning to guess 1,T stuff later, you never finish the first part, so you fail. What's needed is something like a methodical way to cover everything that doesn't do infinite back tracking.

As an example, if we wanted to map all integers to positive integers, the ordering for all integers is very important. If you try "all the positive ones first, then all the negative ones" it doesn't work b/c you never run out of positive ones, never get to the second part of the plan. But what you can do is 0,1,-1,2,-2,3,-3,4,-4 etc. Then you cover everything methodically without planning to backtrack after infinite steps have happened.

The above attempted solution does specify an ordering. It basically just says "keep trying stuff until you get it" which doesn't really address the problem. It might help to imagine you had to write a computer program to make the guesses. What would it guess first? Second?

BTW one neat thing about having an ordering, aka a function of time returning the next guess, is that no storage is needed (besides the current time). Or in other words, if you're guessing in a correct pattern you don't have to keep any lists of previous guesses, all you have to do is know what the pattern is and where you are in the pattern so you can figure out the next thing in the sequence.

It's also not clear that the suggestion of crossing out additional stuff (other than the exact thing you guessed) helps anything. We don't care about efficiency when we have infinite guesses, crossing stuff out is only useful if we have an ordering that misses some guesses but we know they can all be crossed out in this way so it fills in the stuff we know we'd never guess directly. If the solution involves something like that, it's pretty tricky, so one would definitely have to say how it works to solve it.

I'm no expert at this. I tried some and found it's hard to make an ordering that works. Try it yourself and see. I won't be surprised if it's trivial for a mathematician though. And I assume it's possible or they wouldn't ask this question.

If anyone does know the solution I'd be interested in reading it or getting a hint.

Yes, exactly, and very clearly written! The trick is at the bottom beneath "SPOILER", but unfortunately I can't think of a good hint that gets you partway there.

I learned of the method as part of the proof that the cartesian product of a countable set is still countable. (i.e. that if the integers are countable, then the set of all pairs (Z,Z) is countable, where Z is an integer.) If you're interested, you can look at Cantor's work on the different magnitudes of infinities. For instance, you'll notice that if (Z,Z) is as infinite as Z, then the set of all rational numbers is "as infinite" as the set of all integers, since a rational number is just one integer divided by another. But what about the real numbers? Cantor showed with a cute diagonalization proof that they are "more infinite". Is anything more infinite than the reals? (Yes) Is there some level of infinity between the rationals and the reals? (I forget, but I think this is unanswerable, or rather, can be proved both ways) Those are some of the questions he worked on.

SPOILER The trick is to think of a big square, with 0,-1,1,-2,2,etc going along the top and 0,-1,1,-2,2,etc going down the left side. Then the ordering is done by infinitely zig-zagging your way down from the top left to the bottom right.

Thanks! I worked out a different way, too.

SPOILER

For just positive numbers, have the first number count up to the second number. Then increment the second number and reset the first to 0. Then adjusting for negatives is no big deal. Pretty simple in concept. Here's non-simple ruby code for calculating the pair for any step directly:

  def inefficient(n)
    count = 0
    while n > count
      count += 1
      n -= count
    end
    [n, count]
  end
  
  def with_negatives(n)
    # wastes some steps trying to get the negative version of 0. whatever.
    tmp = inefficient(n/4)
    if n%4 == 1
      tmp[0] *= -1
    elsif n%4 == 2
      tmp[1] *= -1
    elsif n%4 == 3
      tmp[0] *= -1
      tmp[1] *= -1
    end
    tmp
  end
  
  50.times {|n| puts "#{n}: " + with_negatives(n).inspect}

Worked out the math to get rid of the loop.

  def efficient(x)
    num = (Math.sqrt(2 * x + 0.25) - 0.5).floor
    num2 = (num**2 + num)/2
    [x-num2, num]
  end

Edit: Or:

  def efficient2(x)
    num = (Math.sqrt(2 * x + 0.25) - 0.5)
    num2 = ((num - num.floor) * num).round
    [num2, num.floor]
  end

Here's the easiest way I can think of to imagine an ordering that works for what you need. Imagine an infinite square lattice: a plane where the As lie on one axis and the Bs on the other, and there's a dot in every integer-coordinates point. Now just do a "spiral", for example counterclockwise: 0,0 -> 1,0 -> 1,1 and keep unwinding your way to infinity. The exact formulas can be written out but intuitively it should be enough to convince you it works even without them.

Initializing an array in constant time, My sneaky solution:

getting and setting seem very simple - if you know the starting memory address and the size of an element (assuming constantly sized elements), you can implement get(i) as "return the value at memory location: start + (i * size) and similarly for set.

So as the question suggests, it's the initialising that's the problem.

My sneaky solution is not to actually initialise the array.

Instead, init(N,d) performs as follows: Store 'd' in some memory location outside of the array.

Set(i,v) finds memory location: start + (i * size) and sets v and a checkdigit.

Get(i) retrieves the value at memory location start + (i * size) and if the checkdigit isn't present or doesn't match, returns the default as set in init, else returns the value.

I think (think) each of those is O(1), but I'm not sure if that's the expected solution.

edit: reading up, I think this won't work as the uninitialised array will be filled with random data and so might 'happen' to pass the checkdigit test :(

The hard thing about this problem is to neutralize the "random data" that can pass whatever error-checking you want to enforce.

I don't remember all the details but the trick is (substantial hint)

SPOILER

to use indirection. Let the data at location i in the array not be the actual value but an index to another array that we continue to fill as we get new set() calls to previously unvisited places. When someone says set(i,v), we look at location i in the first array and see an index into the second. Suppose we can tell if the index is genuine (previously put there by us) or random junk; then everything's easy - when it's junk, allocate a new cell in the second array for the value and update the index. get() with default value also becomes easy. So the problem remains, how to tell random junk from a genuine index we stored before, and I've remembered the rest by now but I'd better stop here.

You are right, this won't work, you do not know what is in the check digit. There is actually a very clever way to do this, which involves using pointers that go back and forth to avoid the random value problem.

I do not have time to explain it, (and since it involves pointers, it would be pretty hard to explain without a white board) but I encourage anyone interested to look into the Knuth book and check it out.

yeah I was reading up on a solution which sounds pretty much like what you're talking about.

Trouble with these things is that if you think you've solved it, there's no way to find out without spoiling it if you haven't. (apart from thinking about it longer and harder)

quite annoying that there's no answer sheet. Some of them seem incredibly simple, so I'd like to know if I'm missing some subtle edge case or if I have actually solved it.

Example: Lemmings on a ledge:

My answer: one minute. Seems to me that we want to maximise the time before collision and the time after collision. So if we start with a lemming at each end heading towards each other, they'll collide in the middle at 30 seconds, change directions and walk back to the end for 30 seconds and then fall off. But that's actually no longer than if we just started with 1 lemming at the far end and he walks uninterrupted to the other side and falls off. Which makes me think I'm missing something because the collision rule adds nothing. A little help here?

edit: (actually 1 minute+planck time, because after 1 minute they'll have gone exactly to the edge but not fallen off, but I think that's not part of the problem. We're also assuming zero-width lemmings)

(update: it's amusing how I switched from lemmings to ants in the below without noticing, because I remember this problem told about ants. Won't change it now).

Well, you're almost right. The point of this problem is that many people find it quite difficult because they think an ant may "survive" for quite a while on the ledge, getting reflected by other ants. So maybe it starts near the middle, gets reflected soon, then gets reflected again, and who knows how much time it can survive by reflecting off other ants which it directs to the edge during these reflections.

Your solution doesn't address this because it only looks at two ants and doesn't explain why couldn't many more other ants make it possible for one ant to survive longer. But actually your solution does contain the crucial insight to solving the puzzle, which is

SPOILER SPACE

to notice that the reflection doesn't actually do anything. When two ants collide and reflect, we can pretend that they just walked past each other - the movements will be the same and the identities of ants don't matter. If we look at it that way, after 1 minute all ants are off the ledge trivially, as they just keep walking in the same direction. The reason this problem is interesting is that it looks tough before this one insight, and completely trivial afterwards. So the collision rule does add nothing, but not everybody can see that, and that's kinda the point of this puzzle.

I see, yes the first instinct is to think that perhaps a lemming could survive forever by constantly bumping into other lemmings. But that's not possible because a lemming traveling in the same direction as the candidate will never bump into him, and traveling in the opposite direction the maximum survival time after the bump is the 30 seconds I mentioned - which I why I only considered 2 ants.

I hadn't quite got to the conclusion that a bump and change is equivalent to no bump and no change though.

> which I why I only considered 2 ants.

dammit now you've got me doing it too!

Path On The Surface Of The Earth is a neat one, took a while to realize why there were multiple answers.

SPOILER: Obviously the North Pole is one answer, because if you're 1 km south of the pole then it doesn't matter what longitude you're at, if you go 1 km north you'll be back at the pole.

The other answers are more interesting, though, and involve the south pole. The key observation is that at certain locations fairly close to the south pole, going east by 1 km will bring you back exactly where you started because the longitude circles are very small, so there's a set of latitudes where your 1 km journey will wrap you around the world any number of times. From that observation you can figure out the rest if you care to flex your trig...

For Boris and Natasha:

Boris places the ring into the box and locks it with the padlock. He sends the locked box to Natasha and it reaches her unharmed. Natasha receives the box and places her own padlock on it without removing Boris' padlock, so it now has two locks on it. She sends the doubly-locked box back to Boris and it reaches him unharmed. Boris then removes his own padlock, so that the box now only has Natasha's lock and then mails it back to Natasha. Natasha receives the locked box unharmed and removes her own padlock, thus receiving the ring.

Multiples of 11: Multiplication with 1-digit number: 11x = 10x + x (Sum of digits=x+x=2x=even) Multiplication with 2-digit number: 11(10x+y) = 110x + 11y = 100x + 10(x+y) + y If x+y<10, Sum of digits = x+x+y+y=2(x+y)=even If x+y>=10, 11(10x+y) = 100x + 10(x+y) + y = 100(x+1) + 10 (x+y-10) +y, Sum = x+1+(x+y-10)+y = 2x+2y-9, which is odd. So, we need to find smallest x+y>=10 where 0<=x,y<10 So, x=1,y=9 and hence the number 11*19=209

For Knight, Knave, Commoner, how can this be done?

> Find a strategy for the king where the king can ask only one yes/no question and only of one suitor.

Seems impossible since the commoner can use the strategy "pretend to be the knight, answer exactly how he would if our places were swapped". Then you won't know if you're talking to the commoner or the knight.

Asking two questions of only one person has the same problem.

What's underspecified is that the commoner doesn't answer randomly. He is either truthful or a liar, so if you add enough "what would you say" qualifiers, you can figure it out.

Actually you don't need many qualifiers, just "Imagine in your head that I ask you if you're suitable to marry. What do you answer in your head?"

If you speak to a liar, this gets two lies (negations) out of them. So anyone has to tell the truth.

Here's my solution to Poisoned wine.

48 hours, and a prisoner will die 24 hours after drinking from the poisoned wine. you only need one prisoner, and a decent stopwatch. Have him drink from a barrel of wine every 6 minutes, watch the exact moment he dies. Take the time in minutes, divide by 6 and that's the wine barrel that's poisoned (zero indexed).

> one dies within 24 hours

Is it really correct to interpret that as "dies in exactly 24 hours"?

Edit: My solution, which assumes that after tasting wine it could take any time between 0 and 24h to die; and that it could vary between tastings:

Given N slaves, you can test 2^N wines in a single iteration, as so:

  - A set of size N has 2**N distinct sub-sets.
  - Have each distinct sub-set taste a different wine.
  - After 24h, everyone who drank the poisoned wine will be dead, and,
    provided you took notes about which set consumed which wine, you
    can look up which wine they drank.
  - (Note also, you leave one wine untasted; if nobody dies, it is the
     poisoned one.)

For our first iteration, we have each set taste multiple wines, like so:

  - The set with five slaves will taste a single wine.
  - Sets with four slaves will taste 2 wines.
  - Sets with three slaves will taste 4 wines.
  - Sets with two slaves will taste 8 wines.
  - Sets with one slave will taste 16 wines.
  - We leave 32 wines untouched.

Of course, in general: a set with N slaves will taste 2^(5 - N) wines.

After 24 hours, all slaves who drank poisoned wine will be dead, and we will have the following possible states:

  - One slave is dead. We know the 16 wines he drank, and we have 4
    slaves left. As shown above, we can easily determine which of
    the 16 wines is poisoned in a single iteration.
  - N slaves are dead. We know which 2**(5-N) wines they drank, and
    we have 5-N slaves left. So we can easily determine which of
    the 2**(5-N) wines is poisoned in a single iteration.

Note that N = 0 is a valid case above.

So, we need to calculate how many wines we can test in this manner. Going through each set:

  - 5 choose 1 * 16 = 80
  - 5 choose 2 * 8 = 80
  - 5 choose 3 * 4 = 40
  - 5 choose 4 * 2 = 10
  - The one wine that all slaves drink the first time.
  - The 32 wines none of them drink the second time.

The sum is 243. Garçon!!! Fetch three more barrels!

i got the same result.

Note that it says the prisoner will die "within 24 hours".

My solution (which looks somewhat correct, so don't read unless you want it spoiled)

Day 0: Where all numbers are base 6 (240 in base 6 == 104)

d0 = last digit of barrel number (in base 6) d1 = second last digit of barrel number (in base 6)

Servant 0: drink if d0 == 0 or d1 == 0 Servant 1: drink if d0 == 1 or d1 == 1 Servant 2: drink if d0 == 2 or d1 == 2 Servant 3: drink if d0 == 3 or d1 == 3 Servant 4: drink if d0 == 4 or d1 == 4

At the end of the day, we will have at least 3 servants alive. (i.e. a maximum of 2 can die)

We now have 3 cases, depending on how many actually died:

- If no servants die, then d1 == 5, d2 == 5. It is barrel 55 (in base 6)

- If servant N dies, then d1 == N, d2 == 5 or d1 == 5, d2 == N. (note that the maximum barrel number is 104, so we can't have confusion between 105 and 5). So we have only two possibilities to test, which is easy with 3 servants alive.

- If servants N1 and N2 die, then d1 == N1, d2 == N2 or d1 == N2, d2 == N1. This gives us at most 4 possible barrels that could be poisoned [1,N1,N2], [1,N2,N1], [0,N1,N2], [0,N2,N1].

So at the end of day 1, we have at least 3 servants, and at most 4 possibilities to test for. Assign possibility 0, 1, 2 to remaining servants. If they all survive, then untested possibility is poisoned. Otherwise, it is obvious.

Except 240 in base 10 in 1040 in base 6. (When moving to a lower base the number will always 'look' higher.)

Gah. Excellent maths by me :)

240(base10) == 1040(base6)

Call the slaves a,b,c,d,& e Each slave (5 - a,b,c,d,e) drinks from 16 barrels - 80. Each unique pair (10 - ab,ac,ad,ae,bc,bd,be,cd,ce,de) drinks from 8 barrels - 80. Each unique trio (10 - abc,abd,abe,acd,ace,ade,bcd,bce,bdc,cde) drinks from 4 barrels - 40. Each unique quartet (5 - abcd,abce,abde,acde,bcde) drinks from 2 barrels - 10. Everyone (5 - abcd) drinks from 1 barrel - 1. Nobody drinks from remaining 9 barrels - 9.

If 1 slave dies we have 16 suspect barrels Each remaining slave (4), pair (6), trio (4) and quartet (1) drink from 1 barrel - 15

If 2 slaves die we have 8 suspect barrels Each remaining slave (3), pair (3), and trio (1) drink from 1 barrel - 7

If 3 slaves die we have 4 suspect barrels Each remaining slave (2), pair (1) drink from 1 barrel - 3

If 4 slaves die we have 2 suspect barrels The remaining slave drinks from 1 barrel

If 5 slaves die we have a positive ID on the barrel

If 0 slaves die we have 9 suspect barrels Each remaining slave (5) and 3 pairs drink from 1 barrel - 8

Yeah, "within 24 hours" doesn't mean "in exactly 24 hours".

Edit: Here's my hint to those who have trouble solving this puzzle. Don't read it before trying to solve yourself!

http://pastehtml.com/view/1c02p65.txt

Ok, this is my solution. This may end up similar to the algorithm 124816 proposed, but I am not sure I understood his solution. So I will give you mine. I arrived at my solution independently from 124816 although it does seem similar.

You label each barrel of wine with a 5 digit binary label. "But wait," you say "5 digits in binary can only enumerate 32 barrels from 00000 (0) to 11111 (31)." You are right, but I did not say the labels were unique.

There is only one barrel labeled 11111. For every barrel that has a label that has exactly one zero, there are two barrels carrying that label. This there are two barrels with the label 01111 and two more barrels labeled 10111, etc. For every label with exactly two zeros, there are four barrels having that same label.

In general, if a label has n zeros (0<=n<=5) there are 2^n barrels having that same label. Now lets see how many barrels we can label using this scheme.

There will be 2^5=32 barrels having the number 000000.

For numbers with 4 zeros there are 5 possible labels and 16 barrels per label. 5x16=80.

For barrels with 3 zeros, there are 5 choose 3 = 10 possible labels, and 2^3=8 barrels per label. 8x10 = 80 total barrels that can be labeled.

For barrels with 2 zeros, there 5 choose 2 = 10 possible labels again with 4 barrels per label. 10x4= 40 barrels.

And for barrels with one zero there are 5 possible labels with 2 barrels per label, which equals 10 barrels.

As mentioned before there is only one barrel that is labeled 11111.

So the grand total is 32+80+80+40+10+1=243 barrels. Thus we can label 243 barrels using the above described scheme. We label 240 barrels and throw away three labels.

Now we get to the slaves. We number the slaves from 1 to 5. Each slave number will be a significant position in a binary barrel label number. We take the slaves to each barrel, and look at the label for the barrel. The slaves whose numbers correspond to significant positions which have "1" on the barrels label drink. The slaves who correspond to significant positions which have "0" on the label don't drink. Thus, a label "10011" means that slaves number 1, 2 and 5 drink. A label "00100" means that only slave number 3 drinks.

After 24 hours we have 0-5 dead slaves. At this point we get a little sad and wonder why couldn't the problem have been worded in terms of rats, or something similar. But we keep on going; by the numbers of the dead slaves, we can determine which label is associated with the poisonous wine. The label with the poisonous wine is the one that has 1's in the positions associated with dead slaves. Thus if the first and second slave died, the poisonous label was 00011.

If all slaves died, it kind of sucks for them, but we are in luck - that means the poisonous label was 11111 and there is only one barrel with this label, so we know which was the poisonous barrel.

But if some slaves survived we will know the poisonous label but will have multiple barrels carrying this label.

The number of slaves surviving will be equal to the number of zeros in the poisonous label. That is because the number of dead slaves is equal to the number of ones in the poisonous label. As discussed above, the number of barrels carrying any label is equal to 2^n where n is the number of zeros in the label.

Thus, after 24 hours we are left with n slaves still living and 2^n barrels that are still suspicious (i.e., one of them is poisonous). If you have followed me thus far, solving this part will be trivial. We tear down the old labels and relabel the 2^n barrels with new n digit binary numbers. This time there is only one barrel per label. We also number the slaves from 1 to n to signify a significant position. We have each slave drink from each barrel that has a "1" in his significant position. And then we wait to see who dies. The poisonous barrel is the one whose label has "1" in every significant position associated with a dead slave.

Well, this is it, I hope you enjoyed it, and yes I am brilliant.

Truly brilliant people don't need to tell other people they are brilliant.

I tried it that way, but the other people keep forgetting.

First, i dont think its exact time. And, second if it was, imho why would anyone wait for 6mins?? Have the prisoner drink every second!!

Came up with a beautiful and elegant solution. Have a look: http://ashishlive.blogspot.com/2010/11/puzzle-poisoned-wine-...

(quite detailed, believe me explaining the approach in words was hard.)

I've posted a solution to counting coins here: http://tech.bluesmoon.info/2010/11/counterfeit-coins-solutio...

Let me know if you think it's right or wrong.

Your solution is not correct. For example, if the counterfeit pile is initially measured with one coin and Delta is -1 (29 modulo 30), you set D1 to 1, but D2 will be 28, 29, or 30. You cannot determine Delta or the counterfeit pile with such values of D1 and D2 using your algorithm.

It's certainly not the case that D{1,2} <= 20 as your comments suggest, and you seem to realize this by checking for D1 >= 25. Also, you ignore the case of 20 < D1 < 25.

Note that Delta is strictly between -5 and 5, so it can't be equal to -5 or 5.

There is actually a really elegant solution to this problem. I'll send you an email so you can let me know if you'd like a hint.

Thanks, I see the issue.

I'm currently having fun at http://hacker.org, which features a cool map.

Looks like microsoft have taken down the page.

multiples of 11 => you need to get the digits to sum to be odd => you need to find a number with a 2:1 ratio of even:odd digits {odd + odd = even, even + even = even, odd + even = odd, odd + even + even = odd [(odd + even)=odd + even = odd], etc.}.

so 209 is the first number with the appropriate 2:1 ratio (edited).

1+5+4=10 so that's not it. if you meant 154x11=1694

1+6+9+4=20 so that's not it either.

By checking manually, it's 209.

19x11=209 2+0+9=11

The way you are doing doesn't seem correct even if what you said it's true, you aren't multiplying by 11.

I have no idea what the reasoning to prove the negative would be. I'd be interested to read it, if anyone knows.

The reason I began my post with "multiples of 11 =>" is because I was addressing that problem.

1+5+4 = 10 (even digit sum)

For small values of X < 10

11X = X+X, 2X always even

For slightly larger values of X, where 11X < 200

11x10 = 110, (starts out even)

11x11 = 121, (both of the first two digits increment by one, flipping even or odd ... in unison)

11x18 = 198, (only two signs will flip until we increment the 100s place, when that happens we will reverse three signs instead of two)

11x19 = 209, (now, three instead of two flip, and our sum comes up odd for the first time, 2+0+9=11)

Reply on news.ycombinator.com