Let's discuss Mathematics

[tycoonist]

Starting to really hate infinities...

OK, I'll bite. So our box has n balls numbered x.
We remove one n ball, replace it with a number of n-1 balls. The number of balls we can replace it with can be enormous - But can't be infinite. Seeing as n isn't infinite, we have a finite number of balls to replace, and we can iterate. We can make it take as long as we want, but we will always have a finite number of balls left, regardless of how many we add with each iteration. Meanwhile, n can only decrease... the process will end - It can only take a finite number of steps.

Thats just me thinking out loud so to speak... Essentially, I agree with PS. Although I eagerly anticipate then next way that infinities will find to screw me over.

 

[Atticus]

My instinct sides with Ps and Tycoonist.

So if the result is surprising, it is possible to continue infinitely. That requires at least that the balls are numbered higher than 2. Also, I'd think that you should not take all the biggest numbers out first. But I still can't come up with a way.

 

[Souron]

The more I think about it, the more sure I get that there is no way.

 

[Atticus]

It's a matter of simple induction that eliminating all of the initial balls first empties the bowl in finite steps. I think all the other methods comes from induction too.

Suppose that any finite number of balls with the number n on them are necessarily eliminated in finitely many steps. Suppose also that you have k balls with number n+1 on them.

-You take one ball out and put k₁ balls with number n in it's place.
-Now you have two options: to eliminate another ball with n+1 on it or to eliminate balls with smaller indices.
-If you take out ball with number n+1 on it, it reduces to the latter option with different k and k₁
-If you choose the latter and don't eliminate any n+1 balls before all the offspring of the first ball is eliminated, the induction assumption tells that you eliminate all the non-n+1 balls in finitely many steps.
-If you eliminate some n+1 balls in between, then it reduces to the case where k₁ is bigger.
-The start of the induction (finitely many balls of number 2) is clear.

It seems that either Petek has very different intuition about this, or the puzzle was created by Devil himself!

 

[Petek]

You guys are just too smart! The inductive arguments to show that the process must terminate are correct. The wrong way to think about the problem is to focus on the number of steps it will take to empty the box. If there is even a single ball numbered greater than one, then there is no bound on the number of remaining steps.

This problem was discussed in one of Martin Gardner's Scientific American articles Bulgarian Solitaire and Other Seemingly Endless Task, which may be read in Google Books.

 

[Millman]

It's nice we have language to draw conclusions about math. And the math involved needed to verify the conclusion.

 

[Mise]

I don't get it!! And I really don't think it's because I'm too smart either.

 

[Petek]

I saw this one on another site (not meant to be difficult):

Consider the following sequence of integers

49
4489
444889
44448889

and so on. Beginning with the second integer, each is formed by inserting the digits 48 in the middle of the preceding entry. Prove that each such integer is a perfect square.

 

[IdiotsOpposite]

Well, it might first be good to write this as a formula...

Let's see, a_0=b_0 *10 + c_0, and b_0=4 and c_0=9, and then a_n = ...

Well, this is harder than I thought. I'm not even sure if I'm on the right track here.

 

[Atticus]

How I would start it would be to try induction on the length of the number.

Since every number has even number of digits, you can do it by the length of the string right to the added digits.

So 49 -> k=0
4489 -> k=1
444889 -> k=2 etc.

k=0 obvious.

Suppose that holds for k. Adding the digits is the same as.... Now it gets more difficult. Here I would try to do this for ten minutes or so, and then conclude that Petek has some nice smart solution for this too.

Have to think it more later...

 

[ParadigmShifter]

I'd look for a better (i.e. more analytic) pattern than just the digits, such as powers of 10 multiplied by 4 and 1, 11, 111, etc. as the most significant digits, and do something similar for the least significant digits.

Then again I have had too many beers to think about it properly.

 

[Mise]

Well the sequence of square roots is 7, 67, 667, 6667, ... So I would try to prove that that sequence always ended up generating squares of the required sequence. No idea how you'd do that...

EDIT: maybe by long multiplication??

 

[sanabas]

Well the sequence of square roots is 7, 67, 667, 6667, ... So I would try to prove that that sequence always ended up generating squares of the required sequence. No idea how you'd do that...

EDIT: maybe by long multiplication??

Not doing it properly right now, but induction should work. 7^2 = 49, (7 + 6 x 10)^2 = 7^2 + 3600 + 840 = 7^2 + 4440 = 4489, (67 + 6 x 100)^2 = 67^2 + 360000 + 80400 = 67^2 + 440400, 6667^2 = 667^2 + 36000000 + 8004000 = 667^2 + 44004000, ...

In each case you're adding 44 to the front, and turning the final 4 into an 8, so the pattern clearly does continue indefinitely.

 

[Petek]

Nice argument. That seems to work. Here's a sketch of what I came up with:

Let x = 66 ... 67. Then x = 66 ... 6 + 1 = 6(11 ... 1) + 1
= 6(99 ... 9)/9 +1
= 6(10ⁿ - 1)/9 +1
= 2(10ⁿ - 1)/3 +1
= (2x10ⁿ + 1)/3

and so x² = (4x10²ⁿ + 4x10ⁿ + 1)/9
= (4(10²ⁿ - 1))/9 + (4(10ⁿ - 1))/9 +1
= (4x99 ... 9)/9 + (4x99 ... 9)/9 + 1 (where the first series of 9s has 2n terms and the second n terms)
= 4x11 ...1 + 4x11 ... 1 + 1 (similar comment about the number of ones)
44 ...488 ... 89, as required.

 

[IdiotsOpposite]

So I looked into quaternions. Now, for those of you who don't know, quaternions are an extension of the complex numbers, and instead of just i, they use i j and k. The fundamental relationship between these two is:

i²=j²=k²=ijk=-1

However, I have a problem with this. Say that we take (ijk)². Well, by the first three equations, this SHOULD equal i²j²k², which of course equals (-1)(-1)(-1) or -1. By the last two equalities, this equals (-1)², or 1. So which one is it?

 

[Atticus]

Quaternions are not commutative. When you add dimensions to the numbers, they lose properties. Just like there's no order in C.

 

[ParadigmShifter]

Yup.

I know quite a bit about quaternions being a games programmer (used for rotations for animation/cameras).

EDIT: so (ijk)²

is ijkijk = ij(kijk) = k(kijk) = k²ijk = -1(ijk) = -i(jk) = (-ij)k = -k.k = -k² = -(-1) = 1.

EDIT2: Note that -1, being real, is commutative.

EDIT3: Octonions are even weirder, they aren't even associative!

EDIT4: But since quaternions are associative, you can just do (ijk)² = (ijk)(ijk) = (-1)(-1) = 1.

 

[IdiotsOpposite]

Quaternions are not commutative. When you add dimensions to the numbers, they lose properties. Just like there's no order in C.

Yup.

I know quite a bit about quaternions being a games programmer (used for rotations for animation/cameras).

EDIT: so (ijk)²

is ijkijk = ij(kijk) = k(kijk) = k²ijk = -1(ijk) = -i(jk) = (-ij)k = -k.k = -k² = -(-1) = 1.

EDIT2: Note that -1, being real, is commutative.

EDIT3: Octonions are even weirder, they aren't even associative!

EDIT4: But since quaternions are associative, you can just do (ijk)² = (ijk)(ijk) = (-1)(-1) = 1.

Ah, I see. Thanks!

 

[ParadigmShifter]

You can also express quaternions as matrices with complex entries:

I = [ 1 0 ]
    [ 0 1 ]

A = [ 0 1 ]
    [ -1 0 ]

B = [ 0 i ]
    [ i 0 ]

C = [ i 0 ]
    [ 0 -i]

Then A² = B² = C² = -I

and ABC = -I.

 

[SS-18 ICBM]

What are factorions useful for?