View unanswered posts  View active topics

Page 1 of 1

[ 18 posts ] 

Author 
Message 
Jared

Post subject: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 9:36 am 

Joined: Mon Aug 18, 2008 10:16 pm Location: Somewhere Else

Suppose we have a set of containers C1, C2, and so on up to Cn. These containers have respective capacities of A1, A2, and so on up to An.
We also have an unlimited set of marbles which are numbered 1, 2, 3, and so on, up to some number x. We can call marbles by their numbers: 1marble, 2marble, and so on.
We want to fill all the containers with xmarbles using the following steps:
1) Put a 1marble into C1. 2) If C1 then overflows (contains A1 + 1 marbles), take all the 1marbles out of C1 (including the overflow marble), and put one 1marble in C2. If C2 then overflows (contains A2 + 1 marbles), repeat for C3, and so on. Do not move any marbles but 1marbles during this step. 3) If the last container, Cn, overflows, take all the 1marbles out of it as normal, but instead put a 2marble into C1. If this causes C1 to overflow, take all the 2marbles out of C1 and put one 2marble into C2, and so on if necessary. Do not move any marbles but 2marbles during these overflow steps. 4) When Cn overflows with kmarbles (1 < k < x), reiterate step 3 as needed by removing all the kmarbles from Cn, adding a (k+1)marble to C1, removing all and only (k+1)marbles from overflowing containers, and putting one marble in the next container for each overflow. 5) If all containers are full of xmarbles, stop. Otherwise, return to step 1.
So, how many 1marbles do we have to put into C1 to fill all the containers with xmarbles for any given set of parameters?
Here is a small example of how the rules work, using the following parameters:
n = 3 (so there are three containers, C1, C2, and C3) A1 = 5 A2 = 4 A3 = 3 x = 3
At the start it looks like this ("" is an empty space)
C1:  C2:  C3: 
So we add 1marbles to C1 until it's full:
C1: 11111 C2:  C3: 
The next 1marble makes C1 overflow:
C1: 11111 (1) C2:  C3: 
So as per the rules, all the 1marbles are removed from C1 and one 1marble goes to C2.
C1:  C2: 1 C3: 
This continues until both C1 and C2 are full of 1marbles:
C1: 11111 C2: 1111 C3: 
The next 1marble makes C1 overflow...
C1: 11111 (1) C2: 1111 C3: 
...Giving us an overflow in C2...
C1:  C2: 1111 (1) C3: 
...Which then gives us a 1marble in C3.
C1:  C2:  C3: 1
So we continue, filling all three containers in this way with 1marbles:
C1: 11111 C2: 1111 C3: 111
Our next overflow marble causes us to have this situation:
C1:  C2:  C3: 111 (1)
So we take all the 1marbles out of C3 because it is the last container, and put a 2marble in C1.
C1: 2 C2:  C3: 
Then on our next overflow in C1...
C1: 21111 (1) C2:  C3: 
...We leave the 2marble there and only remove the 1marbles from C1.
C1: 2 C2: 1 C3: 
Eventually we'll have this situation:
C1: 22222 (1) C2:  C3: 
So, in this case, the only 1marble we can remove is the overflow marble, bringing us here:
C1: 22222 C2: 1 C3: 
And so on. Eventually with these rules we will end up here:
C1: 22222 (1) C2: 2222 C3: 222
So, the 1marble is removed from C1 and another is put in C2, but that overflows that too:
C1: 22222 C2: 2222 (1) C3: 222
So a 1marble goes to C3, but that overflows there.
C1: 22222 C2: 2222 C3: 222 (1)
So we drop the 1marble altogether and put a 2marble in C1:
C1: 22222 (2) C2: 2222 C3: 222
And this cascades into eventually getting our first 3marble in C1.
C1: 3 C2:  C3: 
Then later overflows ignore this marble until the overflowing marble is also a 3marble. Since x = 3, we want to end at this point:
C1: 33333 C2: 3333 C3: 333
Last edited by Jared on Thu Oct 18, 2012 12:05 pm, edited 1 time in total.


Top 


Jared

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 9:58 am 

Joined: Mon Aug 18, 2008 10:16 pm Location: Somewhere Else


Top 


keyfan

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 10:59 am 

Joined: Sat Oct 06, 2012 10:07 pm

Just a guess Attachment:
guess.jpg [ 4.14 KiB  Viewed 1916 times ]
Edit: formula updated with the new notations as below Attachment:
updateguess.jpg [ 14.2 KiB  Viewed 1916 times ]
As I said I didn't prove it. I did the same kind of calculation with schuma, the next formula would be useful in the summation: the sum of the (a+i)!/a!i! as i runs from 0 to n equals (a+1+n)!/(a+1)!n!.
Last edited by keyfan on Fri Oct 19, 2012 2:26 am, edited 3 times in total.


Top 


KelvinS

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 11:10 am 

Joined: Mon Mar 30, 2009 5:13 pm

Can we use sausages instead of marbles?
_________________ If you want something you’ve never had, you’ve got to do something you’ve never done  Thomas Jefferson


Top 


Jared

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 11:35 am 

Joined: Mon Aug 18, 2008 10:16 pm Location: Somewhere Else

Sorry Kelvin, I just ate so I'm not hungry.
Keyfan, I don't think that works because it doesn't take b, c, etc. into account.
I'm going to try to rewrite this for better clarity because I showed it to two other people and they both had trouble following it. I'll edit the main post.


Top 


Brandon Enright

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 11:46 am 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

When you fill up A and then take them out and put them in B, that implies there is an explicit ordering for A, B, ...
Instead using the notation
C0, C1, ... Ci
Where i is countable seems to fix the ordering issue.
It still isn't clear if the size of container 0 is 0, container 1 is 1, etc. Can any container hold any number of marbles arbitrary of the container's ordering? Is the size of the containers always countable? Is the number of marbles always countable?
Are the marbles marked Ω or the containers or both?
When you keep track of how many marbles you put into A, is that the number of marbles in A (limited to a)? Or if you put marbles in A and then take them out and then put in more, can the "number of marbles put into A" greater than a?
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


keyfan

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 11:59 am 

Joined: Sat Oct 06, 2012 10:07 pm

Pi is a product symbol in maths ,so what I actually wanna mean is the product of a sequence of (a+Ω)!/a!Ω！forms where 'a' could be a,b,c,etc. For example when Ω=1， (a+1)!/a!=a+1 and the expression turns into (a+1) * (b+1)*... 1 . I'm not a native English speaker, hope my explanation is clear enough.


Top 


Jared

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 12:05 pm 

Joined: Mon Aug 18, 2008 10:16 pm Location: Somewhere Else

I've posted a rewritten version of the problem with a small example.


Top 


Coaster1235

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 12:11 pm 

Joined: Wed Dec 14, 2011 12:25 pm Location: Finland

When you remove the 1marbles from an overflowing container, what happens to them? Are they discarded or reused?
_________________ My penandpaper puzzles


Top 


Jared

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 12:13 pm 

Joined: Mon Aug 18, 2008 10:16 pm Location: Somewhere Else

Coaster1235 wrote: When you remove the 1marbles from an overflowing container, what happens to them? Are they discarded or reused? They can be discarded. We have an unlimited supply. The marbles are really just a convenient way to visualize the problem with realworld objects. (If Kelvin had his way, they'd be sausages and I guess you could eat them in case of an overflow.)


Top 


MaeLSTRoM

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 12:26 pm 

Joined: Sat Jun 11, 2011 2:34 pm

Hmm, Each layer of this problem makes it just that extra bit harder OK. So for the 1marbles, you have the product of all of the capacities (A1 * A2 * A3 * ... * An). Let's call this number X1 Then, for the 2marbles you have (X1  1) + (X1  2) + (X1  3) + ... + 1, since each 2marble placed decreases the available places for 1marbles by 1 each time. This can be represented as: (X1 * (X1+1))/2. Let's call this X2, or Y(X1) Now, this is where It gets harder to visualise. You then repeat the 2marble step, but decreasing the available space each time for both 1marbles and 2marbles. I think it's this: Y(X1  1) + Y(X1  2) + Y(X1  3) + ... + Y(1). I'm not really sure about this stage and any stages after it, but I'm pretty sure that the first 2 are OK, if someone wants to continue it on a bit.
_________________ I am a fan of the Face turning Dodecahedrons


Top 


Jared

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 12:31 pm 

Joined: Mon Aug 18, 2008 10:16 pm Location: Somewhere Else

keyfan wrote: Pi is a product symbol in maths ,so what I actually wanna mean is the product of a sequence of (a+Ω)!/a!Ω！forms where 'a' could be a,b,c,etc. For example when Ω=1， (a+1)!/a!=a+1 and the expression turns into (a+1) * (b+1)*... 1 . I'm not a native English speaker, hope my explanation is clear enough. I asked another friend to look at this (a physicist) and he said that after looking at it a bit your formula seems to be correct, so I'd like to know how you got it. For the above example in the original post, this works out to 39199 if I did my math right... can anyone check this and/or verify if it's correct? I'm at work so I can't sit down and count for that long.


Top 


schuma

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 12:53 pm 

Joined: Thu Jul 23, 2009 5:06 pm Location: Berkeley, CA, USA

keyfan's formula also looks good to me. I don't have a fancy technique. Just count. The first 2marble will appear in C1, after (A1+1)(A2+1)(A3+1) steps. Now the effective capacity of C1 becomes (A11). So the second 2marble will appear in C1 after (A1)(A2+1)(A3+1) steps. Keep counting like this... We surly need to do some summation, like (A1+1) + (A1) + (A11) + ...+ 1 = (A2+1)(A1+1)/2, and the higher order analog of this formula. Eventually the most compact form will be keyfan's formula.


Top 


KelvinS

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 12:59 pm 

Joined: Mon Mar 30, 2009 5:13 pm

schuma wrote: keyfan's formula also looks good to me. I don't have a fancy technique. Just count. The first 2marble will appear in C1, after (A1+1)(A2+1)(A3+1) steps. Now the effective capacity of C1 becomes (A11). So the second 2marble will appear in C1 after (A1)(A2+1)(A3+1) steps. Keep counting like this... We surly need to do some summation, like (A1+1) + (A1) + (A11) + ...+ 1 = (A2+1)(A1+1)/2, and the higher order analog of this formula. Eventually the most compact form will be keyfan's formula. This means the result is completely independent of b, c, d, etc., which is very interesting. But does it make sense?
_________________ If you want something you’ve never had, you’ve got to do something you’ve never done  Thomas Jefferson


Top 


HeavyTanHat

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 1:18 pm 

Joined: Tue Apr 27, 2010 10:38 am

MaeLSTRoM wrote: since each 2marble placed decreases the available places for 1marbles by 1 each time. I disagree; the first container's 2marbles are removed once an overflow is generated when adding a 2marble to that container, so for the next round the capacity of the first container is back to A1, and the capacity of the second is only reduced by 1 marble.


Top 


Jared

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 1:27 pm 

Joined: Mon Aug 18, 2008 10:16 pm Location: Somewhere Else

P.S. Super bonus internet points to anyone who can tell me what inspired this problem.


Top 


schuma

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 1:47 pm 

Joined: Thu Jul 23, 2009 5:06 pm Location: Berkeley, CA, USA

KelvinS wrote: This means the result is completely independent of b, c, d, etc., which is very interesting. But does it make sense? Oh, please check keyfan's clarification. When he said the product is over a, he actually meant a taking the elements in the set {a,b,c,...}. Now that Jared has changed the notation, it should be: (product of i=1...n of ( (Ai+x)!/(Ai)!/x! )) 1


Top 


Jared

Post subject: Re: A math problem I made up that is too difficult for me Posted: Thu Oct 18, 2012 5:29 pm 

Joined: Mon Aug 18, 2008 10:16 pm Location: Somewhere Else

Yeah, sorry about the confusion. I changed the notation so that it wasn't so dependent on the alphabet.


Top 



Page 1 of 1

[ 18 posts ] 

Who is online 
Users browsing this forum: No registered users and 4 guests 

You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot post attachments in this forum


