My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
October 17th, 2014, 04: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
nwicole is offline  
 
October 17th, 2014, 08:32 PM   #2
Math Team
 
Joined: Dec 2006
From: Lexington, MA

Posts: 3,267
Thanks: 407

Hello, nwicole!

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

Is it 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.

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}$

soroban is offline  
October 18th, 2014, 07:05 AM   #3
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

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.)
CRGreathouse is offline  
October 22nd, 2014, 06:46 PM   #4
Newbie
 
Joined: Oct 2014
From: los angeles

Posts: 17
Thanks: 0

Quote:
Originally Posted by CRGreathouse View Post
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.)
ummm is that really unique? anyway thanks for helping
nwicole is offline  
October 23rd, 2014, 03:26 PM   #5
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by nwicole View Post
ummm is that really unique?
Yes, and I think my post is a proof of that fact.
CRGreathouse is offline  
October 23rd, 2014, 03:49 PM   #6
Senior Member
 
Joined: Jun 2013
From: London, England

Posts: 1,312
Thanks: 115

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 n-1. So, there must have been an initial pile with n-1 Koalas, which became n-2.

By this logic, there must have been a pile with each of n, n-1 ... 1 Koalas. As this requires n piles, this is the only solution where there are n piles.
Pero is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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 12:03 PM
Please help - Discrete math OriaG Applied Math 5 February 11th, 2013 11:27 PM
discrete math....i need help amyporter17 Applied Math 1 November 17th, 2010 08:23 AM
Discrete Math rainysomber Applied Math 10 December 3rd, 2009 03:55 AM
Plz help, no one seem to be able to ! Discrete Math Arturo Applied Math 6 April 3rd, 2008 09:06 PM





Copyright © 2018 My Math Forum. All rights reserved.