The Tourney of a Thousand Princes

Question

You are a sage in service to a king of a profoundly troubled kingdom.

A sordid spectacle...

Every ten years, the king holds a grand tournament, inviting the 1,000 most suitable princes to compete for the hand of one of his daughters. Regrettably, the king's true motive lies in exploiting the princes' legendary oneupmanship.

At the beginning of the tourney, the king has his steward present the sitting princess with a gift (a piece of jewelry) in the presence of all 1,000 princes so that they can witness her delight. He then invites them to introduce themselves one at a time, and watches contentedly as a sordid spectacle of oneupmanship unfolds.

The first prince to approach, wanting to vastly outdo the steward, pledges to give the princess one piece of jewelry for every day of the tourney.

The second prince, wishing to vastly outdo the first, pledges that every day of the tourney he shall give the princess as many pieces of jewelry as the first prince gives her that day plus as many pieces of jewelry as the first prince has given her on all previous days.

Likewise, the third prince, determined to vastly outdo the second, pledges that every day of the tourney he shall give the princess as many pieces of jewelry as the second prince gives her that day plus as many pieces of jewelry as the second prince has given her on all previous days.

This mad spectacle of devotion continues for all 1,000 princes, ending when the 1,000th prince has boldly pledged that every day of the tourney he shall give the princess as many pieces of jewelry as the 999th prince gives her that day plus as many pieces of jewelry as the 999th prince has given her on all previous days.

The plot thickens...

The grand irony of the king's scheme is that he hates jewelry. He allows the princess to collect it only so that he can give it to the nobles attending his decennial Nobles Gala, which he holds after the tourney is completed.

There are 24 nobles he must invite to the gala, and they're notoriously fickle. For one thing, those who attend demand some jewelry in return for their attendance. For another, the attendees insist on each receiving exactly the same number of jewelry pieces as each other.

Worst of all, rumours abound that some of the invitees may not show up for the upcoming Nobles Gala. Perhaps all 24 will, perhaps only one will, or perhaps any number in between. The exact number is unknowable until the gala is held.

A sage is needed!

As the king's sage, issues related to distribution of jewelry naturally fall to you. He makes it clear to you that:

• regardless of how many nobles ultimately turn up at the gala, their fickle demands must be met
• the only jewelry that will be distributed among the attendees is the jewelry given to the princess during the tourney
• every single piece of jewelry must be given to the attendees. Throwing it away (which is a curse) or keeping it (which the king hates) is unacceptable.

The only thing in your power to control is the number of days the tourney will last. It must last at least one day (obviously), and ideally it should be as short as possible, minding that you must guarantee the nobles' demands are met.

In light of all the above, how many days should the tourney of 1,000 princes last?

Good luck, fair sage. ;)

Answer 1

The steward gives 1 gift on the first day and no gifts on any other day, so he gives a total of 1 gift.

The first prince gives 1 gift on every day, so he gives a total of $d$ gifts through day $d$.

The second prince gives $n$ gifts on day $n$, for a total of $d+1\choose2$ gifts through day $d$.

The third prince gives $n+1\choose2$ gifts on day $n$, for a total of $d+2\choose3$ gifts through day $d$.

This continues until the 1000th prince gives a total of $d+999\choose1000$ gifts through day $d$.

The total number of gifts is ${d-1\choose0}+{d\choose1}+{d+1\choose2}+\ldots+{d+999\choose1000}={d+1000\choose1000}$. So we have to find $d$ such that $d+1000\choose1000$ is divisible by every integer from 1 to 24.

${d+1000\choose1000}=\frac{(d+1000)\times((d+1000)-1)\times((d+1000)-2)\times\ldots\times1001}{d\times(d-1)\times(d-2)\times\ldots\times1}$. This product must be divisible by 5. However, 1000 is divisible by $5^3$, so every factor of 5 from a number in the product that is not divisible by $5^4$ will be cancelled out by the corresponding term in the denominator. For the result to be divisible by 5, at least one term in the numerator must be divisible by $5^4$. The smallest such number greater than 1000 is 1250, so $d$ must be at least 250.

$1250\choose1000$ is not divisible by 3, so 250 does not work. However, $1251\choose1000$ is divisible by every integer from 1 to 24, so 251 is the smallest possible number of days. The total number of gifts is $1251\choose1000$, which about $6.3\times10^{270}$.

Answer 2

To satisfy the nobles demand that the jewels must be shared evenly between them, the number of jewels must be a multiple of all the numbers under 24.

The smallest such number is 5354228880*

Assuming that the princes offer gifts in the same order each day.

There's the table of how many jewels are collected by each day of the gala.

d j pledged that day, cumulative** 
1 0,1000
2 501500,502500
3 167668500,168171000
4 42084793750,42252964750
5 8459043543950,8501296508700
6 1418299634202450,1426800930711150

If these were 1mm cube gemstones they would fill more than 10 cubic meter treasure chests by day 6.

Unfortunately on none of the six days was the treasure divisible.

On the 7th day my calculator reaches to limit of its precision, but the are then approximately 205459334022406530 pieces of jewellery to deal with, that's 5900 cubic metres of tiny gems, enough to fill a 24 meter square treasure vault up to your waist (or thighs depending on height).

If the princes bring larger pieces of jewellery around 1cm cube size, say sets of pearl earrings or fine gold chains, the by day 7 most of the castle is full of treasure.

If day seven didn't turn out to have just the right number then there are going to be problems because the pile of treasure grows in size by around 100 times a day at first. Although the rate of increase drops the pile still multiplying in size by 10 each day at day 100, and will have about 1.565e144 which is more than the number of atoms in the sun.

I can't say for sure but I feel like there will never be a day when the jewellery could be shared by any number of the guests who may arrive, if there is it won't be before the demand for jewellery has destroyed the economies of most of those 1000 principalities.

Changing the number of princes invited doesn't seem to help. Assuming I'm doing the sums right, no number of princes under 1000 will work within the number of days my calculator's precision allows me to test.

There may be a way to prove that no solution exists from this problem when p=1000 and n=24 but I am unaware of it.

*Thanks to CodeNewbie for correcting me on the number the treasure must be divisible by. I initially thought it would be 4684950270 but changed for instead 4260838982400, can you work out from those what I was doing wrong?

**CodeNewbie thinks my other numbers are wrong, I think I might have assumed that the pledges from each day are cumulative. Either way both our methods suggested the lack of an answer. that any answer will be too big to accurately calculate with ease and way too large to practically store that many objects.