Problem 688

[KING-OLE]

I have problems understanding the exact question.

Do the piles need to have different counts of plates:

1) before the new plates are added,
2) added to each pile,
3) after new plates are added
4) all or some of the above - which? _____________

Thanks.

[mdean]

What "new plates"? You take n plates and divide them into k piles. For each calculation of f(n,k), the total number of plates is fixed.

[KING-OLE]

"We stack n plates into k non-empty piles where each pile is a different size."

So, the new plates are n, and the k piles are NOT empty, therefore old or existing.

EDIT: Or am I reading that wrong? - Does it simply mean that I have to place at least one plate on each pile, leaving none empty, and that the k piles are empty before you place the plates?

[DJohn]

You might be reading "We stack n plates into k non-empty piles" as "We stack n plates onto k non-empty piles", which (to me at least) has a quite different meaning. We start with nothing but n plates. Stacking takes place. Then we have k piles, none of which are empty. The question is concerned with this final state: a total of n plates in k piles (with no two piles having the same number of plates). How they got there doesn't matter.

It might be the "non-empty" that's tripping you up. This is describing the piles after the stacking, not before. It's not something you'd say in every-day speech, but in maths a pile could contain zero plates, and that case must be excluded for this problem.

It might be better worded "We divide n plates into k non-empty piles".

[KING-OLE]

Thank you for clarifying DJohn.

The language had me misunderstanding the task. I would have preferred something like "Stack n plates in k piles. No pile must remain empty."

Anyway, I understand the question now, so I will now see if I can solve it.

[vamsikal3]

<deleted post>

[RobertStanforth]

The problem text reads: It is impossible to divide 10 into 5 non-empty piles and hence f(10,5)=0.

Thank you for pointing this out. The wording has now been amended.

[TGiordi]

Hello,

I'm able to compute the exact S(100) value with a simple algorithm and an optimized algorithm. My simple algorithm gives me the same result as the optimized one till 10⁶ or 10⁸. Anyway, the solution for 10¹⁶ is wrong. Could you provide S(10⁶) or S(10⁸) in order to be able to trouble shoot my simple & optimized algorithm as I assume there should be a special case that I've not taken into account and that is not visible in S(100).

Thanks

[castrate]

I came across almost the same problem as @TGiordi. I got the correct answer(12656) for S(100) and I was able to compute S(10^16) in reasonable time, but the answer was wrong. So can I PM someone in order to check my answers for higher results such as S(10^8)? Thanks

[castrate]

Hmm...Seems that I'm stuck. I tried sending PM to several administrators, but with no replies for over three months. So could someone help confirm the following results:
S(10^6)=***xxxxxxx***
S(10^8)=***xxxxxxxxxxx***
S(10^10)=***xxxxxxxxxxxxxxx***
S(10^12)=***xxxxxxxxxxxxxxxxxxx*** EDIT digits removed by moderator
where x represents a single digit.
I don't mean to spoil, but the problem has been confusing me for too long.
Thanks in advance.