October 17th, 2014, 03:49 PM  #1 
Newbie Joined: Oct 2014 From: los angeles Posts: 17 Thanks: 0  Discrete math again :(
We have several piles of koala bears. In an attempt to disperse them, we remove exactly one koala bear from each pile and place all of those koalas into one new pile. For example, if we started with koala piles of sizes 1, 4, and 4, we would then end up with koala piles of sizes 3, 3, and 3; or, if we started with piles of size 3 and 4, we would end up with piles of size 2 and 3 and 2. It is possible that we do this operation exactly once and end up with the exact same pile sizes as we started with? (the order of them is irrelevant; only the sizes matter). Identify all the collections of piles that have this property and explain why they are the only ones. thank you so much 
October 17th, 2014, 07:32 PM  #2  
Math Team Joined: Dec 2006 From: Lexington, MA Posts: 3,267 Thanks: 408  Hello, nwicole! Quote:
I found one such collection. I have no proof that if it is the only one. The sizes of the piles are the first $n$ consecutive $\quad$ natural numbers in some order. Suppose $n = 6$ Before the operation, we have: $\quad \begin{array}{cccccccc} 2 & 4 & 1 & 6 & 3 & 5\end{array}$ After the operation, we have: $\quad \begin{array}{ccccccc} 1 & 3 & 0 & 5 & 2 & 4 & 6 \end{array}$  
October 18th, 2014, 06:05 AM  #3 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
Well, if we want to have the same number of piles as before, we need exactly one pile to have 1 koala (since we're making a new pile we need to remove one as well). It could be that this is the only koala 1 or there could be others. In the latter case the new pile will have at least two koalas in it, so there must be exactly one other pile with two koalas. This works 1 2 since the new pile replaces the two, but if we have any others the new pile will have at least 3 koalas, so we need another pile  just one  with exactly 3 koalas to replace the one with 2. You can continue the process as far as you'd like, getting (as soroban says) the first n positive integers. I think this construction is unique and should give you all the answers. (You may need to include the trivial collection of 0 koalas as well.) 
October 22nd, 2014, 05:46 PM  #4  
Newbie Joined: Oct 2014 From: los angeles Posts: 17 Thanks: 0  Quote:
 
October 23rd, 2014, 02:26 PM  #5 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  
October 23rd, 2014, 02:49 PM  #6 
Senior Member Joined: Jun 2013 From: London, England Posts: 1,316 Thanks: 116 
By a slightly different argument: Suppose there are n piles initially. Then a new pile with n Koalas will be formed. So, there must have been an initial pile with n Koalas, which became n1. So, there must have been an initial pile with n1 Koalas, which became n2. By this logic, there must have been a pile with each of n, n1 ... 1 Koalas. As this requires n piles, this is the only solution where there are n piles. 

Tags 
discrete, math, structures 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Discrete Math Help?  pjlloyd100  Applied Math  11  April 18th, 2013 11:03 AM 
Please help  Discrete math  OriaG  Applied Math  5  February 11th, 2013 10:27 PM 
discrete math....i need help  amyporter17  Applied Math  1  November 17th, 2010 07:23 AM 
Discrete Math  rainysomber  Applied Math  10  December 3rd, 2009 02:55 AM 
Plz help, no one seem to be able to ! Discrete Math  Arturo  Applied Math  6  April 3rd, 2008 08:06 PM 