8 balls problem

My friend and I were working on an interesting riddle recently. It's one that I'm sure most people have heard before, and probably didn't have much trouble solving. It goes as follows:

Given 8 balls, each weighing exactly the same except one (which we'll assume is heavier), and a scale, what is the least number of times you must use the scale to find the heavy ball?

The approach most frequently thought of is to split the 8 balls into 2 pairs 4 balls and place those on the scale. Then, go to the side that turns out heavier, and split those 4 balls into 2 pairs of 2 balls and place those on the scale. When one side turns out heavier, weigh those final 2 balls and you'll find the heavy ball.

But as anyone who has ever heard a riddle in his life would know, the most obvious answer is rarely the correct one. You can actually find the heavy ball using the scale only twice. To do this, you must set to balls aside, and weigh the final 6 with 3 on each side of the scale. If they balance, you know the heavy ball is among the final two and you need only weigh those. If they don't, you need only weigh 2 of the final 3, because, if those two balance, we know the heavy one is the final, unweighed ball, if they don't, the heavy ball would obviously be the heavier one of the two.


Pretty simple, yes? But then the question arises. What if you were given 9 balls? Or 20? 81 balls? What will the minimum usage of the scale be then? We worked on this for a bit, and got a table showing the least number of times required to find the heavy ball out of n balls. It started off like

1: 0*
2: 1
3: 1
4: 2
5: 2
6: 2
7: 2
8: 2
9: 2
10: 3

* If you have just one ball, you don't have to weigh anything to figure out it's the heavy ball.

Side Note:

Our table was actually a little bit more expressive. This is because of the fact that, in each case, you have the probability of finding the heavy ball on your first try, your second try, and so on, depending on how you weigh the balls. For example, given 4 balls, you could weigh 2 on each side, and weigh the heavier 2 again, giving you 0 chance of finding it on your first try. Or you could 1 on each side, and only weigh the remaining two if these balance out. But, if they don't balance out, then you'd have found the heavy ball in your first attempt. This post ignores that, as I haven't been able to find anything interesting when including these probabilities. That could be something for a later time.

Do you happen to see a pattern? For 1 ball it takes 0 weighings. For 2-3 balls it takes 1. For 4 - 9 balls it takes 2. Now, it turns out that for 10 - 27 balls it takes 3. I'm sure you've seen it by now. It is indeed a logarithmic growth rate, but of base 3, and not 2. The reason for this? Why, it's simple. While deciding how to weigh the balls one must consider both how many to place on each scale and how many to ignore. The naive method of simply splitting the balls in half and repeating completely disregards the information that can be gained from simply placing to the side a number of balls.

I won't bother at a formal proof that this is the least number of weighings needed to find the heavy ball. (If you don't believe me, you can try to find a more efficient way yourself). I will however, describe a simple method that can be used to find the proper way to weigh a set of "n" balls. You must keep in mind only two things. The number of balls you put on each scale and the number of balls you place aside. Each of these numbers must be less than the greatest power of 3 less than n. (the previous power of three to n.). As long as these criteria are met, you will weigh the balls most efficiently. For example, if given 100 balls, I'm allowed to put up to 81 on each scale (of course, the restraints of the number limit me to putting 50 on each scale), but I also must make sure not to put more than 81 aside. (Technically, I can only put 80 aside. If I put 81 aside, I'm left with 19 balls which I can't divide evenly among the scale).

Well, that's it for today. Hope you found it interesting.

Sum of Digits

This is just an intriguing fact I discovered while doing a project euler problem (number 56 to be specific). The problem asked for the largest sum of digits of any number of the form a^b where both a and b are between 0 and 100. As I often do, I'm going through a rather circuitous path in discovering the answer. While doing this, I happened upon an interesting fact about numbers. If you subtract the sum of the digits of any number, from the number itself, you gain a multiple of nine. That is

Where S(x) obviously denotes the sum of the digits of x. I honestly don't know why this is true just yet. Though, I do know that a similar formula is true for all other bases. That is, for any number n written in base b, if you subtract the sum of the digits of x from I decided to explore this some more. I wanted to see if I could define a function F(x) that defines the exact multiple of nine that results from subtracting the sum of the digits of a number from the number itself. What I mean to say is I want to find a function such that



So, I did some experimenting. I wrote a program that listed the values f(n) should take on from 1 to 100. It turns out that it followed a rather simple pattern.



Though, this probably won't get me any closer to solving the problem, it is something interesting to think about. Just thought I'd share.

My attempt at being Funny.

I was messing around with Macromedia's Flash movie creator recently. I've always been interested in comic making and thought it would be a good chance to try my hand at it. These are my first few attempts at being funny. Now, I don't expect to become the next Randall Munroe (Though, that'd be freakin' awesome), but I'd rather not make horrible comics. So, for all of you reading this (i.e. nobody) I'd be happy to see some criticisms of this work.

They're too large to fit in this screen directly, (and I'm too lazy to shrink them) so I'll just post direct links.

First Comic
Second Comic
Third Comic


Kind of a short post for me, but I don't have anything interesting to post right now. So....yeah. See ya later.

Golden Ratio, Part II

Well, as I said, everything there is to know about the φ couldn't possibly be condensed into a single blog post. Probably wouldn't fit into two either but I figure there was still quite a bit more left to talk about that I didn't get into in the previous post. For starters, I sort of felt bad the proof I showed for the formula to produce Fibonacci numbers wasn't very original. You can find it on Wikipedia on the page for Fibonacci numbers. I thought about it some more, and came up with an alternate, albeit a slightly more complicated, proof. I just wanted to post it up because I thought it was pretty interesting.

Remember the formula for expressing powers of φ in terms of it's first power and a constant, reprinted below:



Rearranging the formula we can place to isolate the variable. Doing, this, we obtain:



Not very helpful so far. But, we can substitute F_(n-1) with a similar expression, repeat this with the F_(n-2) that appears and so on and so on, until Finally we reach F_0, which, as stated before, is equal to 0. The resulting equation will look something like this:




Yeah, still won't be very much use in the proof. It would help if we remove the fractions from the numerator. To do this, we simply multiply by φ / φ exactly n-1 times. (Had to be cautious at this point. A fencepost error would've screwed me over). Also, when subtracting, we must make sure to flip the negative signs to positive ones. When we do this, the resulting expression goes in a + then - pattern. When all is said and done, we obtain the following formula:


.

There is +/- sign is on the φ term is because in the cases where n is an odd number, it ends up being +φ at the end, but in cases where n is an even number, it ends up being -φ. (i.e., if n was 3, it would go φ^5 - φ^3 + φ, but if n was 4 it'd be φ^7 - φ^5 + φ^3 - φ). I just thought this formula was an intriguing one. Even more interesting is how it's equivalent to the previous one even though that's not obvious at all.

But, how do we prove this equivalence? We could equate it to (φ^n - (1-φ)^n)/sqrt(5) and use identities of \phi to make both expressions the same, but that would most likely end in a lot of headache and frustration (take my word for it). Instead, we could describe the left-hand expression as a series indexed by n. The series would correspond directly to the Fibonacci series, so if we can prove that (φ^n - (1-φ)^n)/sqrt(5) represents

The Series will be defined like this:



For example (using the next to last equation)


Which is what we were aiming for. All that remains is to prove that the formula describes this series. We do this through induction.

It is obviously true for the first element of the series.


Now, for the induction step. That is, proving:

.

Next, we muse the fact that (1-φ) = (-1/φ). We multiply by (1/φ) on the numerator and the denominator.



.

They are looking quite similar at this point. Now, all that's left to do is prove that . This can be done simply, and easily in a few steps.



Plugging in the actual value of φ will show the final statement to be true, thus proving the equivalence of the two formulas.

And there you have it. I don't think I've seen this proof anywhere else on the internet. I'd say it's inferior to the other one, though, because you have to know the end result in order to complete the proof. Though, it did yield an interesting expression that the other proof didn't. That's probably the only superior part.

PS:
If you're wondering about all the different font for the formulas, it's because I switched between using a program called MathType and this website http://mathurl.com/. I then went back and tried to change all the functions to use the website. Stopped caring, and left off with this mess.

Yeah.

Golden Ratio

The golden ratio is a truly remarkable mathematical constant. While, it's not quite as famous or important as π or e, there's still a wealth of information to be discovered from studying it.



For any two numbers a and b that satisfy the equation. That is, the ratio of the a + b to a is equal to the ratio of a to b. To find the exact value of φ we use the fact that (a/b) = φ, meaning a = bφ. Substituting in the first equation gives



And solving for the positive solution yields

.

(Approximated).


One of the coolest thing's about φ is it's relation to the Fibonacci series. The Fibonacci series begins with 1, and the next term is determined by the sum of the previous two terms. The first 10 terms of the series are

1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

So, you get the idea. The explicit definition of the Fibonacci series is below:



The first relationship that comes to mind is seen when you look at the following table

F(n) / F(n-1)	Value	Difference From φ
1/1	1	.618
2/1	2	-0.381
3/2	1.5	0.118
5/3	1.6667	-0.048
8/5	1.6	0.0180
13/8	1.625	-0.0070
21/13	1.6154	0.0026
34/21	1.6190	-0.00101
55/34	1.6176	0.000386
89/55	1.6182	-0.000148

As you can see, the ratio between the consecutive terms of the Fibonacci series approaches φ. This is only the beginning of the relationships these two mathematical phenomena share.

Now, comes the interesting part. Look back at the quadratic we used to calculate the value of &phi. Leave the squared term on the left-hand side of the equation and move the other two terms to the right-side. Now, if we multiply both sides of the equation by φ once, we have φ^3 = φ^2 + φ. If we multiply by φ again we have φ^4 = φ^3 + φ^2. Obviously, since we can multiply by φ any number of times, the following equation is valid.



The recursive nature of this equation leads tho the conclusion that any power of φ can be represented in terms of it's first power and another number. For example, φ^3 is equal to φ^2 + φ, but φ^2 is equal to φ + 1, so φ^3 = 2φ + 1. Any power of φ will go through a similar process until it's eventually expressed in terms of the first power of φ and a constant. The interesting part is the pattern that emerges as you express powers of φ in terms of it's first power.

φ^1 = φ
φ^2 = φ + 1.
φ^3 = φ^2 + φ = (φ + 1) + φ = 2φ + 1
φ^4 = φ^3 + φ^2 = (2φ + 1) + φ +1 = 3φ + 2
φ^5 = φ^4 + φ^3 = (3φ + 2) + (2φ +1) = 5φ + 3.


Observe the coefficients of φ. In order, they go 1, 1, 2, 3, 5. Recognize the pattern? If you don't, I'll give you a hint. It starts with 'F' and ends with 'ibonacci'. That's right! The coefficients of the φ-terms follow the Fibonacci series. That's not all. If you observe the constant term as well, you find that it follows the same pattern, only offset by a single index.



It's relationship with the Fibonacci series doesn't end there. Due to the fact that the formula for calculating the powers of φ is very similar to the formula for determining terms of the Fibonacci series, we can actually use φ to calculate any term of the series we want without bothering to generate the entire series up to that number. The formula to do this is as follows:



It's not immediately obvious where this came from. Though, the proof for it is really quite simple. Before beginning, you should note that φ only refers to the positive solution to the quadratic. The negative solution is simply ignored. But, notice that the negative solution to the quadratic also satisfies the relationship between it's powers that φ does. That is, it's nth power is equal to the sum of the (n-1)th power and the (n-2)th power. Notice also, that the second solution to the quadratic is equivalent to 1 - φ, because:



(Now you know where the (1-φ) came from.)

Now comes the proof. Let's take two real numbers, a and b, and form the expression .aφ^n + b(1-φ)^n. Because of the properties of φ and (1-φ), the value of the expression follows the patterns from before. That is, if we form a series by starting with n = 1, and incrementing n by one each time, it's value at n = k is equal to it's to the sum of it's value at n = k-1 and n = k-2. This can be proven through substitution from the formulas we already have.



Because of this, if this, if we have a function G(n) = aφ^n + b(1-φ)^n, we have the fact that G(n) = G(n-1) + G(n-2). Exactly like the Fibonacci series. Now, all that's left to do is make sure that it begins the same way as the Fibonacci series and the rest of the terms will follow automatically. That is, we must substitute values for a and b so it starts the same way as the series. We do this with a system of equations, using the first two terms of the series. (We could actually use any two terms, but that would make things unnecessarily complicated). Now, we could use the 1st, and 2nd term (1 and 1) but things are even simpler if we use the 0th term and the 1st term. Intuitively, the 0th term should be equal to 0, because 0 + 1 = 1 (the second term.). Now, we obtain the equations




Upon solving, we find



Substituting these values in aφ^n + b(1-φ)^n we obtain the formula we set out to prove.

~Q.E.D.


While this formula is great and all, it leaves a little to be desired. What if you had the problem of finding the first Fibonacci number to be over 1000? Or even determining whether or not a certain number is a Fibonacci number? This formula would be insufficient.


Look back at the formula for generating a Fibonacci number. We can re-express it as


We can use the fact (1-φ)^n / sqrt(5) is always less than one half (you can observe this yourself by punching a few values in your calculator), meaning, that the nth Fibonacci number is the number closets to φ^n / sqrt(5). That is, you plug in φ^n / sqrt(5) and merely round it to the nearest number. This is a very useful formula. Like answering the question from below. What is the first Fibonacci number over 1000? Now, it becomes a rather simple process:




You can use the change of base formula to solve for n. Since n is the point at which φ^n / sqrt(5) becomes 1000 we merely need to take the first integer greater than n and plug it into the equation for finding Fibonacci numbers. Easy peasy lemon squeasy.


Well, that's it for now. It's some pretty cool stuff. Also, for those of you that frequent Project Euler, you could use the final expression discussed here (φ^n / sqrt(5)) to solve Problem 25 with a few calculations on a scientific calculator. It's really quite epic.

My Favorite Things

Often I find that when i come across an interesting subject I find myself completely engrossing myself in int for hours, if not days. If I were to attempt to write my thoughts about the subject down, i could go on for pages. Which gave me the idea to start this blog. I figure it may or may not be a good way to share my ideas and interests. Which reminds me, I should probably get to explaining what those are.

My favorite things. Well, first and foremost, my favorite subject is mathematics, and all it's branches. Algebra, Calculus, Geometry, Graph Theory, Logic, Combinatorics. Secondly, I love programming. My most frequent languages or C++, Lisp, and Python (in that order). Programming has caused the mathematics under Computer Science to be my favorite. Now, I'm not an expert in any of these fields (I haven't even taking an official course in Calculus yet), so don't expect to find a master's thesis or anything like that. Just simple and intriguing tidbits of mathematical phenomena.

This blog will just be a means of delivering any interesting findings the world. These would most likely involve any of the subjects mentioned before. I don't claim my ideas are original or even difficult to discover. Though, I do try to present them in an original and intuitive way. (I truly detest mathematical papers that I have to read 10 times over in order to understand. I aim to keep that from happening).

And that's pretty much it. Nice to meet you. Hope you enjoy the blog.