My Math Forum Discrete math again :(

 Number Theory Number Theory Math Forum

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

 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:
 Originally Posted by CRGreathouse 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

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
Quote:
 Originally Posted by nwicole ummm is that really unique?
Yes, and I think my post is a proof of that fact.

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

 Tags discrete, math, structures

,

# mr suraj piles rasip the koala

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post pjlloyd100 Applied Math 11 April 18th, 2013 11:03 AM OriaG Applied Math 5 February 11th, 2013 10:27 PM amyporter17 Applied Math 1 November 17th, 2010 07:23 AM rainysomber Applied Math 10 December 3rd, 2009 02:55 AM Arturo Applied Math 6 April 3rd, 2008 08:06 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top