Pop quiz!

[Nic Corelli]

PHJ, Fuyu, Daniel and possibly some other people (can`t remember quite right) took my quiz and thought my real name was Carlos Armando! :mrgreen: :mrgreen: :mrgreen:

[danieldoof]

maybe it will get better when I hang around here a bit :wink:
I barely know you all yet

but my score is not bad for guessing is it?

[PointyHairedJedi]

Originally Posted by Nic Corelli

PHJ, Fuyu, Daniel and possibly some other people (can`t remember quite right) took my quiz and thought my real name was Carlos Armando! :mrgreen: :mrgreen: :mrgreen:

GASP!

You mean it isn't? :shock:

[catalina_marina]

Thank you, Nic, for digging up this thread. For some reason I couldn't find it when I tried to, a week or so ago.

Originally Posted by Michiel

Any idea how you would go about it if you had, say, 4 balls?

Or: More than two balls and not enough balls for a binary search?

One ball: 100 tries.
Two balls: 14 tries.
Three balls: 9 tries.
Four balls: 8 tries.
Five or more balls: 7 tries.

Now, please don't ask me to generalize it further, for another number other than 100 stories, so that I'd actually have to set up a formula, because I already failed that once. And when I say once, I mean, of course, over and over again. :roll:

[PointyHairedJedi]

^ I forsee the potential for much fun here... :twisted:

[NAHTMMM]

Hmm. Actually, it should be fairly straightforward to generalize for a single ball... :?

[catalina_marina]

Uhm, well yes, if you stick to a certain number of balls, it is. But what if you vary that? And then, say, for 200 stories? Or for 150? Just to name a few.

It probably wouldn't even be all that hard, but I just suck at creating formulas. For now. :wink:

[Draknek]

(Draknek has been working this out for far too long)

Changing the number of floors is fairly trivial (once you get how to do it at all, that is - I didn't).

With only two balls, the formula is:

y = ceil(1/2*(sqrt(1+8x)-1))

Where y is the number of attempts you need to make and x is the number of floors. (Ceil means round up.)

Showing my working backwards, that formula is produced from this one:

1/2*y*(y+1) >= x

Which is, in turn, produced by this one:

(Sum of a between a=1 and a=y) >= x

Which is the original formula for 2 balls.

For one ball, the formula is:

y >=x

But that is equivelant to:

(Sum of 1 between a=1 and a=y) >= x

Going back to 2 balls:

(Sum of a between a=1 and a=y) >= x

Is the same as:

(Sum of (Sum of 1 between a=1 and a=b) between b=1 and b=y) >= x

Extending this, for three balls, it would be:

(Sum of (Sum of (Sum of 1 between a=1 and a=b) between b=1 and b=c) between c=1 and c=y) >= x

However, at 2:20 in the morning, I'm not willing to work that out and get a y=blah equation for three balls.

(Apologies if this makes little sense, is in a stupid order, or both. Draknek is tired now.)

[Nic Corelli]

No, my name is not Carlos Armando and you know that perfectly well, :P

[catalina_marina]

Ah yes, the sums. I thought of that, actually, but I couldn't make any direct formulas for them, after the first one. And my calculator is pretty slow on the recursive ones. :roll:

[Alexia]

Originally Posted by Nic Corelli

[PointyHairedJedi]

*Head explodes*

[Draknek]

Ah, my work here is done.

(Almost)

I worked out this to be the formula for 3 balls:

y^3 + 3y^2 + 2y - 6x >= 0

But either I've forgotten how to factor polynominals with magnitude > 2, or I haven't learnt yet.

[NAHTMMM]

Hmm, I shall have to program an appropriate program at school, just for the fun of it :twisted:

[Alexia]

Fun? FUN?! Are you insane?

Oh, yes. You are. In that case, I withdraw the question :wink:

[NAHTMMM]

I'm still not particularly happy with the (Mathematica) function I came up with...

ballfall[maxfloors_] := 
        Do[For[i = 0; cmax = IntegerPart[maxfloors];
               cmin = 1, cmax - cmin > 0, 
               i += 1, temp = Ceiling[(cmax + cmin)/2]; cmin = temp];
           Return[i], {1}]

^Highlight that code if you can't read it because of the colors


Ideally that would be a rounding-down function, not a ceiling function, but IntegerPart leads to an infinite loop of evil DOOM! when cmin is one less than cmax ... Still, the only mistakes should be that the smallest number of floors for which n trials are required might seem to require only n - 1 trials.


Here's a plot for up through 100 and a bit...

[Draknek]

That looks like the graph for 5 to an infinite number of balls.

Cat, are you sure that it's 9 tries minimum for 3 balls? I get 8.

EDIT: Nevermind. I wrote a program, which agrees with you.

#!/usr/bin/perl -w

use strict;

# Edit the next two values as appropriate

my $ballcount = 2;
my $floorcount = 100;

my $tries;
for ($tries = 0; 1; $tries++)
{
  if (howmanyfloors($tries,$ballcount) >= $floorcount)
  {
    print "It takes a maximum of $tries tries to check $floorcount floors with $ballcount balls.\n";
    exit;
  }
}

sub howmanyfloors
{
  my $tries = shift;
  my $ballcount = shift;
  
  # Can't check any floors without any balls
  return 0 if ($ballcount < 1);
     
  my $floors = 0;
  while ($tries > 0)
  {
    $tries -= 1;
    $floors += howmanyfloors($tries,$ballcount-1) + 1;
  }
  
  return $floors;
}

[catalina_marina]

I'm quite sure. You only get till the 92nd story with eight tries.

[Draknek]

Yeah, that's what my program told me, and I'm fairly certain now that it will be correct for any given values.

There's got to be a problem with my maths somewhere.

[NAHTMMM]

I don't even SEE much in the way of math in your program... :?



Anyway, it would seem that the number of building heights such that you need a maximum of n one-ball trials to find the minimum height from which the ball will break is equal to 2^n (which isn't terribly surprising). That is, there are 2^(2-1) = 2 building heights that require 2 trials, 2^(3-1) = 4 building heights that require 3 trials, etc. And of course there's the exception of the building just one story tall, where you don't need to run any trials because you know the ball will break if you drop it from the first story since there aren't any other stories to drop from :lol:.