Project Euler Forum

Hello everyone. I've had quite a hard time understanding the logic behind Problem 709 - Even Stevens. So let's just use the example they give in the problem to illustrate my issue:

After 4 days there are 5 possible packings and if the bags are numbered 1 (oldest), 2, 3, 4, they are:

1. Four empty bags,
2. 1 and 2 inside 3, 4 empty,
3. 1 and 3 inside 4, 2 empty,
4. 1 and 2 inside 4, 3 empty,
5. 2 and 3 inside 4, 1 empty.

How can this be? Isn't this inconsistent? If packaging 2 & 4 both use the same bags but leave diffrent bags empty then it follows that packaging 3 & 5 should be able to do the same, which results in 7 possible packings. Or 2 & 4 shouldn't be allowed swap empty bag and thus we reach 4 possible packings.

Please tell me if I'm wrong but I believe this problem has a false answer since I can come to the conclution that f(4) = 7 or 4 or 13 but not 5.

Packaging 2 and 4 are built up in different ways.

2 comes from:
A) place bag 1 inside
B) place bag 2 inside
C) place 1 and 2 in bag 3
D) place bag 4 inside

4 comes from:
A) place bag 1 inside
B) place bag 2 inside
C) place bag 3 inside
D) place bag 1 and 2 in bag 4

In other words, you are right that you are not allowed to swap the empty bag.

wrongrook wrote: Mon Apr 27, 2020 8:11 pm Packaging 2 and 4 are built up in different ways.

2 comes from:
A) place bag 1 inside
B) place bag 2 inside
C) place 1 and 2 in bag 3
D) place bag 4 inside

4 comes from:
A) place bag 1 inside
B) place bag 2 inside
C) place bag 3 inside
D) place bag 1 and 2 in bag 4

In other words, you are right that you are not allowed to swap the empty bag.

I'm not quite sure I understand what you mean. Even so, how does taking this packaging differance into a account change anything? If i do what you did for the rest I get the following:

1. Four empty bags,
1 comes from:
A) Place all bags inside

2. 1 and 2 inside 3, 4 empty,
2 comes from:
A) place bag 1 inside
B) place bag 2 inside
C) place 1 and 2 in bag 3
D) place bag 4 inside

3. 1 and 3 inside 4, 2 empty,
3 then comes from:
A) place bag 1 inside
B) place bag 3 inside
C) place bag 1 and 3 in bag 4
D) place bag 2 inside

4. 1 and 2 inside 4, 3 empty,
4 comes from:
A) place bag 1 inside
B) place bag 2 inside
C) place bag 3 inside
D) place bag 1 and 2 in bag 4

5. 2 and 3 inside 4, 1 empty,
5 then comes from:
A) place bag 2 inside
B) place bag 3 inside
C) place bag 2 and 3 in bag 4
D) place bag 1 inside

6. 1 and 3 inside 2, 4 empty,
6 then comes from:
A) place bag 1 inside
B) place bag 3 inside
C) place bag 4 inside
D) place bag 1 and 3 in bag 2

7. 2 and 3 inside 1, 4 empty,
7 then comes from:
A) place bag 2 inside
B) place bag 3 inside
C) place bag 1 inside
D) place bag 2 and 3 in bag 1

Each time you need to either place the new bag inside the cupboard empty, or place bags inside the new bag.

This means that your example 7 is invalid because in step D you cannot put bags into bag 1 (as it is not the new bag).

I think I'm doing the right calculations but my result for n=8 is nowhere near the description.

Here is how I calculated it:
All empty = 1

1 group with 3 (2 in 1) = C(8, 3)

1 group with 3, 1 group with 5 (4 in 1) = C(8, 3) * C(5, 5)

1 group with 5 = C(8, 5)

2 groups with 3 = [No. 3-groups ending with 3] * C(8-3, 3) + [No. 3-groups ending with 4] * C(8-4, 3) + [No. 3-groups ending with 5] * C(8-5, 3) = C(5, 3) + C(3, 2) * C(4, 3) + C(4, 2)

1 group with 7 (6 in 1) = C(8, 7)

All these values sum to 205, nowhere near 1 385. I don't see what I'm doing wrong.

Perhaps

1, 2, 3 and 4 in 5

and

1 and 2 in 3; 3 and 4 in 5

shall be treated as separate cases?

Misare wrote: Tue May 30, 2023 2:27 pm Perhaps

1, 2, 3 and 4 in 5

and

1 and 2 in 3; 3 and 4 in 5

shall be treated as separate cases?

These are separate cases. In the first case, 3 is empty. In the second case, 3 is not. Hope this clarifies it.

For n=8 I now get:

All bags empty: 1
2 bags in 1 bag, 5 bags empty: C(8, 5)
4 bags in 1 bag, 3 bags empty: C(8, 3)
6 bags in 1 bag, 1 bag empty: C(8, 1)
2 bags in 1 bag, 4 bags in 1 bag: C(8, 5)
4 bags in 2 bags, 2 bags empty: C(8, 2) * (1 + C(3, 2) + C(4, 2))

These results sum to 457. Have I missed some cases or am I calculating something incorrectly?

This is starting to stray away from "clarification" and into the "partial results" territory.

Please look at my previous response. I think you will realize what is missing.

neverforget wrote: Thu Jun 01, 2023 3:44 am This is starting to stray away from "clarification" and into the "partial results" territory.

Please look at my previous response. I think you will realize what is missing.

Fine. I see what I'm missing now.

For future reference, can bags be removed from other bags? For example, let's say we have bags 1 and 2 inside 3 and bag 4 empty, then introduce bag 5. Can we put bag 1 and bag 4 in bag 5?

mdean wrote: Thu Jun 29, 2023 8:53 am For future reference, can bags be removed from other bags? For example, let's say we have bags 1 and 2 inside 3 and bag 4 empty, then introduce bag 5. Can we put bag 1 and bag 4 in bag 5?

The example for n=4 rules out this possibility.

That said, I suppose "existing bags" is indeed ambiguous, since it really means "existing bags not in other bags"