The Islanders and their Birthday Presents

Question

Once upon a time, a band of colonists, all having distinct birthdays, settled on a remote island. They had brought some mementos from the old country, around which certain mores regarding friendships and birthdays eventually developed:

• Making new friends is encouraged, but with care: to ever break off a friendship is unthinkably rude.

• Friendships are mutual. To call someone a friend when they would not say the same of you is unthinkably rude.

• When someone has a birthday, each of their friends is expected to give them a birthday present of exactly one memento. To not have a memento to give or to give more than one memento is unthinkably rude.

• Mementos may be given to someone only on their birthday. To give a memento on any other day is unthinkably rude.

• To give a friend the same memento that they gave you on your most recent birthday is tacky. I.e., unthinkably rude.

One fine stormy day, a castaway washes up on the shore with nothing but the clothes on his back and a small portrait of his family, which counts as a memento in the island reckoning. He is brought to the leader who, after making sure that the sailor doesn't share his birthday with any islander, explains the local customs. "You should make at least one friend soon," she says. "To not have any friends would be looked on as unthinkably rude."

"Are there many people here?" he asks. "Many mementos?"

"Yes, very many." she says. "There are $n$ islanders, all perfectly polite, and as many mementos."

The refugee hesitates. He does not want to be rude, and he does not want to put someone else in a tight spot. Can he safely make a friend, or is a scandal inevitable?

Answer 1

I think

scandal is inevitable. This is because, before and after the stranger arrives, everyone must have exactly two friends. Proof follows.

A key rule is the "don't be tacky" rule, where you don't give a person the gift they most recently gave you. Suppose, some year before the stranger arrives, the islanders decide to flip this rule into a "must be tacky" rule, but keep all of the friendships and the general patterns for gift giving the same. It's clearly possible for them to continue to give gifts according to the other rules: a person gets a bunch of gifts on their birthday, then they proceed to hand each gift back to the person that gave it as the year progresses.

We then see for each friendship, there is one gift that passes back and forth between the two friends.

We can also assign partial ownership to each gift. For a gift that passes back and forth between two friends, we say each of the friends is a half owner of the gift. If you just keep a gift permanently, you are the sole owner of that gift. This latter ownership rule comes into play if a person (say Bob) has just one friend. Since Bob was following the "don't be tacky" rule before, Bob must have an extra gift to prevent being tacky. When it swaps to the "must be tacky" rule, then Bob just has a gift that just sits there and collects dust.

If a person has one friend, then they have ownership over 1.5 gifts (one that sits there, and half ownership over the one they trade back and forth). If a person has two friends, they have ownership over 1.0 gifts (two half ownerhips). If a person has more than two friends, then they have ownership over at least 1.5 gifts. Therefore, the only way for their to be on average one gift per person is if everyone has own 1.0 gifts, and therefore everyone has exactly two friends. This was true under the "don't be tacky" rule as well.

Now comes the stranger. We see that everyone must have exactly two friends before he arrives. After he arrives, we must maintain the property that everyone has exactly two friends. But that means it is impossible for the stranger to make any friends.

Answer 2

My conclusion is that:

Scandal is inevitable

This is demonstrated thus:

Because there are the same number of mementoes as islanders, all mementoes are in circulation. This means that if you have $x$ friends and it is your birthday, you have $x$ mementoes in your possession, and you give them all out. Over the course of the year you then get one memento from each of your $x$ friends, resulting in having $x$ mementoes again by your birthday.

This means that if the castaway befriends someone who has their birthday before his, then that islander won't have enough mementoes to give out = scandal!

But surely our castaway can befriend an islander whose birthday isn't for a while? He can only befriend one islander, because he only has one memento to give out. So the castaway has his birthday first, and gives his islander friend the memento. All good. And on that islander's birthday he gives the castaway a different memento. All good. But the castaway still only has one memento, so he can't befriend any more islanders, and he can't break off his existing friendship. Which means that when his islander friend's birthday comes around the only memento he has to give is the one his islander friend recently gave him = scandal!

The only slight consolation is that the castaway has at least a year before the scandal will erupt. I suggest he works on an escape plan!

Answer 3

It is not generally possible.

One configuration is that all $n$ people on the island have 2 friends: the person whose birthday is immediately before theirs and the one whose birthday is immediately after. This makes a big friendship ring.

They are in a status quo. The person who most recently had a birthday has 2 momentos, the person whose birthday is next has 0 momentos and everyone else has 1 momento. On the next birthday, the celebrant receives two presents, one from the person who had two momentos and one from the next person to have a birthday. Status quo remains: most recent birthday celebrant has 2 momentos, next one has 0, everyone else 1.

On the next person's birthday, the one who has 2 momentos gives the one they received from the other person. They always have two presents to choose from, so this is always possible. This means that one present is regifted every time, moving forward around the ring, and each other present moves back one space each year.

Now add a new person: you. If you make a friend with someone whose birthday is further out than your own, then that person will have to give out one more present than they would have, before their next birthday. The status quo had them giving out all their presents, so they're guaranteed to run out.

If you make a friend with someone whose birthday is before yours, then you give your present to that person on their birthday, raising their number to 3. The other person then gives you a different present back when you have your birthday. The problem is that on the next time your friend has a birthday, the only gift you have is the one they just gave you, and that is not allowed.

Making multiple friends doesn't work either; someone would be guaranteed to run out of presents. If your birthday is before any of your new friends', then that person will run out. If it is after more than one, then you will run out.

There could be multiple, possibly intersecting rings. But even if there are, you run into the same problem: either you force someone to run out, you run out, or you are forced to give back the same present you received to the person who gave it to you.

There may be configurations where it is possible to add you (I don't think so), but there are definitely configurations where it is not.

Answer 4

Let's look at the island, before the refugee arrives, on the date Jan 1. We will show that every islander must have exactly two friends. Consider the following directed graph: the islanders are vertices, and there is an edge between friends which is directed towards the islander with the earlier birthday. I claim that

• Every islander must, right now, have at least as many presents as their "out-degree" (the number of edges they have which point away).
• Every islander with exactly one friend must have at least one present, plus at least one more if his edge directs out.

To understand the first bullet point: if an islander has, for example, three edges pointing out, that means he will have to give three gifts before his birthday. If he didn't have at least three presents right now, he would run out.

However, islanders with one friend (loners) are a special case. A loner can never be without a present, else he would have to regift the next gift he receives. This explains the second bullet point: he needs the extra present to ensure he is never empty.

The above two bullet points show that $$ \text{# of friendships }+\text{ # of loners }\le \text{ # of mementos }=n $$ Letting $f_k$ be the number of islanders with $k$ friends, and using the fact that the number of edges an undirected graph has is the half the sum of the vertex degrees, the above equation can be written as $\big(\frac12\sum_1^n k\cdot f_k\big)+f_1\le n,$ or as $$ \tfrac32 f_1+f_2+\tfrac32 f_3+\tfrac{4}2f_4+\dots+\tfrac{n}{2}f_n\le n $$ The only solution to the above inequality is for every islander to have exactly two friends. Every islander contributes at least one to the above sum, and since there are $n$ islanders, he must contribute exactly one. Every category other than $f_2$ contributes $\frac32$ or more to the sum, so every islander must have two friends.

This means that the refugee cannot avoid a scandal: we have shown that the island's customs can only be maintained if every islander has two friends, but the refugee arriving and making a friend would destroy that property.

Answer 5

I think its pretty simple.

Given that that are only n mementos and with n people, we can model the stable equilibrium/solution as a series of graphs with each person as a node. Friendships exist already which forms each edge in the graph.

Each edge is directional, in that one end has their birthday before the other end does.

We know that given those rules, we have been able to map all the edges into a series closed loops. This shall be left as an exercise to the reader....(hint what would have happened to all the mementoes if there was an open end?)

Given this is the case, the new node can always insert himself into the appropriate part of a cycle, if he befriends the person who has a birthday just before him in the cycle, and the person who is just after him in the cycle.

Answer 6

Yes, he can kill the leader, take his place, and all of the leader's friends. For some bizarre reason, this is not unthinkably rude in the strange and unusual customs of this island.

alternatively, there are n islanders and each one is friends with exactly one other islander. Adding another person to the system is easy because the new person can simply trade mementos with their new friend.

a third alternative: He simply chooses to befriend someone whose birthday was yesterday, and he will be fine up until almost two years from now when he might run out of mementos. (unless he makes new friends at the rate of slightly over 1 per year)