This is a Combination and Optimization problem with Split n piles of stones. Q3

Question

This is a Combination and Optimization problem with Split n piles of stones.

Q3 (10 points) (a) Stephanie has three piles of stones containing 5, 15 and 25 stones. She can join any two piles into one pile. Also, she can divide a pile with an even number of stones into two piles of equal size. By repeating these steps, can he ever achieve 45 piles, each containing 1 stone? Show how she can do this or prove that it cannot be done. (b) Stephen has three piles of stones containing 5, 49 and 51 stones. He can join any two piles into one pile. Also, he can divide a pile with an even number of stones into two piles of equal size. By repeating these steps, can he ever achieve 105 piles, each containing 1 stone? Show how he can do this or prove that it cannot be done

Explanation / Answer

For both a and b , i can provide a single answer.

In order to achieve 1 stone for each pile , the total number of stones should defienitely be 2^x (where x>0).

Other that this case we coulddn't achive 1 stone for each pile.

Example: 5,15 and 25 stones in 3 piles

a) if we join 5 and 15

20 and 25 stones in 2 piles

10,10,25 in 3 piles

5,5,5,5,25 in 5 piles

join 5 and 25

5,5,5,30

divide 30

5,5,5,15,15

join 15 and 5 in 2 cases

5,20,20

divide both 20's

5,10,10,10,10

divide 10's

5,5,5,5,5,5,5,5,5

b) if we join 5 and 25

15,30

divide 30

15,15,15

c)if we join 15 and 25

5,40

divide 40

5,20,20

divide both 20's

5,10,10,10,10

divide 10's

5,5,5,5,5,5,5,5,5

That will the final step. we can't proceed further

  

Example 2:

Let us suppose we have 16 stones in 3 piles (2^4)

4,7,5 stones in 3 piles

join 7 and 5

4,12

join 4 and 12

16

divide

8,8

divide

4,4,4,4

divide

2,2,2,2,2,2,2,2

divide

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

so in this case we'll get the required output

I hope this could help. Thanks!

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.