Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Wed Apr 23, 2014 2:22 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 18 posts ] 
Author Message
 Post subject: A math problem I made up that is too difficult for me
PostPosted: Thu Oct 18, 2012 9:36 am 
Offline

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: 1-marble, 2-marble, and so on.

We want to fill all the containers with x-marbles using the following steps:

1) Put a 1-marble into C1.
2) If C1 then overflows (contains A1 + 1 marbles), take all the 1-marbles out of C1 (including the overflow marble), and put one 1-marble in C2. If C2 then overflows (contains A2 + 1 marbles), repeat for C3, and so on. Do not move any marbles but 1-marbles during this step.
3) If the last container, Cn, overflows, take all the 1-marbles out of it as normal, but instead put a 2-marble into C1. If this causes C1 to overflow, take all the 2-marbles out of C1 and put one 2-marble into C2, and so on if necessary. Do not move any marbles but 2-marbles during these overflow steps.
4) When Cn overflows with k-marbles (1 < k < x), reiterate step 3 as needed by removing all the k-marbles 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 x-marbles, stop. Otherwise, return to step 1.

So, how many 1-marbles do we have to put into C1 to fill all the containers with x-marbles 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 1-marbles to C1 until it's full:

C1: 11111
C2: ----
C3: ---

The next 1-marble makes C1 overflow:

C1: 11111 (1)
C2: ----
C3: ---

So as per the rules, all the 1-marbles are removed from C1 and one 1-marble goes to C2.

C1: -----
C2: 1---
C3: ---

This continues until both C1 and C2 are full of 1-marbles:

C1: 11111
C2: 1111
C3: ---

The next 1-marble 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 1-marble in C3.

C1: -----
C2: ----
C3: 1--

So we continue, filling all three containers in this way with 1-marbles:

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 1-marbles out of C3 because it is the last container, and put a 2-marble in C1.

C1: 2----
C2: ----
C3: ---

Then on our next overflow in C1...

C1: 21111 (1)
C2: ----
C3: ---

...We leave the 2-marble there and only remove the 1-marbles from C1.

C1: 2----
C2: 1---
C3: ---

Eventually we'll have this situation:

C1: 22222 (1)
C2: ----
C3: ---

So, in this case, the only 1-marble 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 1-marble is removed from C1 and another is put in C2, but that overflows that too:

C1: 22222
C2: 2222 (1)
C3: 222

So a 1-marble goes to C3, but that overflows there.

C1: 22222
C2: 2222
C3: 222 (1)

So we drop the 1-marble altogether and put a 2-marble in C1:

C1: 22222 (2)
C2: 2222
C3: 222

And this cascades into eventually getting our first 3-marble in C1.

C1: 3----
C2: ----
C3: ---

Then later overflows ignore this marble until the overflowing marble is also a 3-marble. 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
 Profile  
 
 Post subject: Re: A math problem I made up that is too difficult for me
PostPosted: Thu Oct 18, 2012 9:58 am 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
(Edited for clarity.)


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

Joined: Sat Oct 06, 2012 10:07 pm
Just a guess
Attachment:
guess.jpg
guess.jpg [ 4.14 KiB | Viewed 1939 times ]


Edit: formula updated with the new notations as below
Attachment:
update-guess.jpg
update-guess.jpg [ 14.2 KiB | Viewed 1939 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
 Profile  
 
 Post subject: Re: A math problem I made up that is too difficult for me
PostPosted: Thu Oct 18, 2012 11:10 am 
Offline
User avatar

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
 Profile  
 
 Post subject: Re: A math problem I made up that is too difficult for me
PostPosted: Thu Oct 18, 2012 11:35 am 
Offline

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 re-write 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
 Profile  
 
 Post subject: Re: A math problem I made up that is too difficult for me
PostPosted: Thu Oct 18, 2012 11:46 am 
Offline
User avatar

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
 Profile  
 
 Post subject: Re: A math problem I made up that is too difficult for me
PostPosted: Thu Oct 18, 2012 11:59 am 
Offline

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
 Profile  
 
 Post subject: Re: A math problem I made up that is too difficult for me
PostPosted: Thu Oct 18, 2012 12:05 pm 
Offline

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
 Profile  
 
 Post subject: Re: A math problem I made up that is too difficult for me
PostPosted: Thu Oct 18, 2012 12:11 pm 
Offline
User avatar

Joined: Wed Dec 14, 2011 12:25 pm
Location: Finland
When you remove the 1-marbles from an overflowing container, what happens to them? Are they discarded or reused?

_________________
My pen-and-paper puzzles


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

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
Coaster1235 wrote:
When you remove the 1-marbles 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 real-world objects. (If Kelvin had his way, they'd be sausages and I guess you could eat them in case of an overflow.)


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

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 1-marbles, you have the product of all of the capacities (A1 * A2 * A3 * ... * An). Let's call this number X1

Then, for the 2-marbles you have (X1 - 1) + (X1 - 2) + (X1 - 3) + ... + 1, since each 2-marble placed decreases the available places for 1-marbles 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 2-marble step, but decreasing the available space each time for both 1-marbles and 2-marbles. 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
 Profile  
 
 Post subject: Re: A math problem I made up that is too difficult for me
PostPosted: Thu Oct 18, 2012 12:31 pm 
Offline

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. :P


Top
 Profile  
 
 Post subject: Re: A math problem I made up that is too difficult for me
PostPosted: Thu Oct 18, 2012 12:53 pm 
Offline
User avatar

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 2-marble will appear in C1, after (A1+1)(A2+1)(A3+1) steps. Now the effective capacity of C1 becomes (A1-1). So the second 2-marble 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) + (A1-1) + ...+ 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
 Profile  
 
 Post subject: Re: A math problem I made up that is too difficult for me
PostPosted: Thu Oct 18, 2012 12:59 pm 
Offline
User avatar

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 2-marble will appear in C1, after (A1+1)(A2+1)(A3+1) steps. Now the effective capacity of C1 becomes (A1-1). So the second 2-marble 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) + (A1-1) + ...+ 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
 Profile  
 
 Post subject: Re: A math problem I made up that is too difficult for me
PostPosted: Thu Oct 18, 2012 1:18 pm 
Offline
User avatar

Joined: Tue Apr 27, 2010 10:38 am
MaeLSTRoM wrote:
since each 2-marble placed decreases the available places for 1-marbles by 1 each time.


I disagree; the first container's 2-marbles are removed once an overflow is generated when adding a 2-marble 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
 Profile  
 
 Post subject: Re: A math problem I made up that is too difficult for me
PostPosted: Thu Oct 18, 2012 1:27 pm 
Offline

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. :P


Top
 Profile  
 
 Post subject: Re: A math problem I made up that is too difficult for me
PostPosted: Thu Oct 18, 2012 1:47 pm 
Offline
User avatar

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
 Profile  
 
 Post subject: Re: A math problem I made up that is too difficult for me
PostPosted: Thu Oct 18, 2012 5:29 pm 
Offline

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
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 18 posts ] 

All times are UTC - 5 hours


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

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group