12
$\begingroup$

It is well known that cats can be turned into perpetual motion machines under the right circumstances. Candy-sharing cats are such wonderful creatures that come in infinite supplies, called #1,#2,#3,...

An $M$ machine is made by $M$ of these cats sitting in a circle, each having any number of candies given by you: if cat #$n$ has $n$ candies ($n\leq M$), it will give each cat in its clockwise direction one candy until it runs out of candies (if $n=M$ then it will leave the last candy to itself). When it has finished the sharing, if there's another cat which also has its number of candies equal to its #number, it will become the next sharer. If more than one such cat exists, then the one with the smallest number becomes the sharer.

If we can make an $M$ machine in which there's always a next sharer, the candies will never stop flowing, then it's an $M$ perpetual motion machine!

For example, the picture below is a failed attempt to make an $M=6$ PMM. The number in the parentheses is the number of candies each cat is given at the start. Here's how it runs:

  1. #4 will give one candy to #1,#5,#3 and #6 each.
  2. #3 will give one candy to #6, #17 and #4 each.
  3. #6 will give one candy to all the other 5, leaving the last one to itself.
  4. the machine stops because no cat is a sharer now.

enter image description here

Question: What kind of PMM can you make? Is there an upper limit to the size you can achieve?

$\endgroup$
16
  • $\begingroup$ What do you mean by "what kind of PMM"? The number of rounds? Whether or not it can run indefinitely? $\endgroup$
    – justhalf
    May 11, 2023 at 14:47
  • $\begingroup$ @justhalf Sorry I just realized that I hadn't gave any definition of what a PMM is! How embarrassing! I edited the question to fix that, with the definition in bold font. $\endgroup$
    – Eric
    May 11, 2023 at 15:35
  • 1
    $\begingroup$ Yea, I asked because of the example, since it's not explicitly mentioned. One way to interpret the part "come in infinite supplies, called #1,#2,#3, ... ... by M of these cats" is that we take the first M cats (even moreso that we see the numbers #1, #2, #3, which subconsciously suggest we take the first M). Although technically it does mean we take any M cats from this bag of infinite cats, it's unusual, so the other meaning prevail for me :) $\endgroup$
    – justhalf
    May 12, 2023 at 9:09
  • 1
    $\begingroup$ @justhalf It doesn't matter in practice - an infinite sink will prevent perpetual motion, so any solution will use the set of cats #1 - #M. $\endgroup$ May 12, 2023 at 17:03
  • 1
    $\begingroup$ That only works if cats only share the first M-1 of their stash and keep the rest for themselves. @hexomino is clearly assuming that cats keep going round and round the circle until they run out. $\endgroup$
    – loopy walt
    May 13, 2023 at 11:14

4 Answers 4

4
$\begingroup$

To start, I'll grab your attention with this 13-PMM:

11 7 3 8 1 4 10 5 6 12 9 2 13
6 4 1 7 0 2 7 2 2 1 0 0 13

It is the largest PMM I found, and coincidentally the first odd one. It repeats after only 30 shares, so you can prove it works by hand if you really wanted to. Above, I provided one valid candy arrangement... however there are over 10,000 different arrangements that could be used with it such that each forms a unique repeating cycle.

This PMM was found using a computer algorithm. There are (n-1)! arrangements of n cats in a circle, and beyond that (n-2)! arrangements of candies for each (making some basic assumptions) which makes for some processor-intensive searching. The reason I did better than previous attempts, I suspect, comes down to an assumption I made that allowed me to create a surprisingly effective filter.

I assumed that the highest numbered cat, which I call n-cat, shares exactly one time before the cycle returns to the exact same candy configuration it started on

It's not that I think that is true (I actually don't), it's that this assumption allows me to solve for how many times each cat shares in order for a cycle to be possible. Each cat must share a whole number of times, and per my assumption the n-cat cannot receive more than n candies or else it would share twice. My algorithm to check this is just like the original problem, but instead of specific candy counts I'm using relative ones. I used this check to filter out the vast majority of cat combinations before I made any kind of assumption about what candy counts were in front of them.

n 1 2 3 4 5 6 7 8 9 10 11 12 13
After Filter 1 1 1 3 0 13 3 25 2 25 9 68 15
Actual PMMs 1 1 0 2 0 10 0 10 0 6 0 29* 2*

Keep in mind that this is under the assumption I made, so there could be more. I additionally put asterisks on some of the higher-PMM values because I began cutting corners to save processing time, and while I think its probably right I should be safe and say "there could be more". I'm glad that my techniques were able to get at least to n=12, as before that point the data seemed to be slowing down in terms of viable PMMs. With n=12 containing nearly as many PMMS as the rest combined, I think its very possible that there could be an infinite number of them.

A Link for all 61 PMMs I've found

My PMM List (Try pasting it into excel or something, the formatting of paste-bin doesn't make it look right)

Additional observations:

Others had conjectured that switching the position of the n-cat with the second-highest cat of a PMM will lead to another PMM. This seems to often be true, and I call such pairs of arrangements "sisters". The two 13-PMMs I found are sisters. Sisters behave exactly the same through my filter, which might help illuminate why both tend to end up being viable together. I do not believe sisters always both work, however, as the following PMM appears to be a counter-example. I think its sister has a hard time because the 1-cat would directly feed the n-cat which tends to be a recipe for disaster.

9 5 2 6 7 4 10 3 1 11 8 12
4 4 1 0 4 3 5 2 0 3 0 12

I don't think anyone has yet observed that total candy counts can vary for PMMs of the same size. Since larger PMMs tend to have many viable candy arrangements, there are a considerable number of data points as the list progresses and so I can even add that the distribution seems to tend towards something like a bell-curve. The trend line for the average candies per n seems to be roughly $.27n^2-.12n+1.18$. I used this to predict what candy counts to be analyzing for bigger PMMs instead of just trying everything.

n 1 2 3 4 5 6 7 8 9 10 11 12 13
Min Candies 1 2 - 5 - 10 - 16 - 25 - 36* 40*
Max Candies 1 2 - 5 - 11 - 19 - 29 - 42* 48*

I wish I had more to say about what sorts of arrangements seemed best. The 1-cat seems like it is more important than most the rest but you'll see it feeding just about every other cat. Only when it feeds the n-cat directly does it seem problematic, and even that is hard to be sure about since that could very well be where my assumption made me blind to the higher truth. You might think that grouping together the bigger cats are either good or bad, but again I see both in viable PMMs and can't make any meaningful observation about it.

I'm curious to know if my assumption could be proved incorrect, but that's not quite enough to inspire me to keep at it. Still a fun problem, Eric, thanks for the fish.

$\endgroup$
1
  • $\begingroup$ I believed that only even pmms are possible before this answer. Thanks Skosh for this enlightening answer! $\endgroup$
    – Eric
    Jun 17, 2023 at 15:08
4
$\begingroup$

Partial answer to get things rolling.

It is impossible to make a PMM with exactly

3 cats

Explanation

Start with the following observations.

Observation 1:

In a working PMM, all cats involved will share an infinite number of times.
As a shorthand, I will call any cat who does not share "miserly."
In a PMM, any cat who shares a non-infinite number of times will eventually become miserly, after they've completed their finite sharing.
If cat #N is miserly, then any time cat #N-1 shares, a candy will be given to the miserly cat, therefore cat #N-1 cannot share more times than there are candies in the system.
The number of candies is finite, therefore cat #N-1 will also become miserly over time.
By induction, a single miserly cat will eventually cause all cats in the circle to become miserly.
When all cats are miserly, the system halts.
Therefore, a PMM cannot contain miserly cats, and since finitely-sharing cats become miserly over time, a PMM cannot contain finitely-sharing cats either.

Observation 2:

No cat will ever have more candies than its number.
If they did, the cat will become miserly and never share again, because its amount of candy can never decrease unless it is exactly equal to its number.

Observation 3:

The cats in any PMM will always be numbered consecutively, starting from #1
From the problem statement: "if cat #n has $n$ candies ($n≤M$), it will give each cat in its clockwise direction one candy until it runs out of candies"
I take this to mean that if $n>M$, then cat #n is miserly.
Since a PMM cannot contain any miserly cats, a configuration with $M$ cats can cannot contain any cat with a number higher than M.
Since cats have distinct positive integers, and there are exactly $M$ positive integers $n$ where $n≤M$, the cats must have exactly those integers.

With those out of the way, let's get back to the specific case.

There are two possible configurations, either ascending (#1, #2, #3), or descending (#3, #2, #1).
In both configurations, we'll need exactly 4 candies. With 5 or more candies, the #3 cat can never share because there will always be a lower numbered cat with more candies. With 3 or fewer candies, then after the #3 cat shares, each cat would have exactly 1 candy, which terminates in both arrangements. (#1 cat shares in both configurations, then #2 cat shares in the ascending configuration, but after that there is no further sharing).
Now that we know the number of candies, we can use the observation from before to know that the #3 cat will always share, and only consider placements of candies such that the #3 cat is about to share. Any PMM must eventually reach such a placement of candies, otherwise the #3 cat would be miserly.
There is exactly one such configuration: #1 has $0$, #2 has $1$, and #3 has $3$.

In the ascending arrangement, the following sequence occurs:

#1, #2, #3
(0, 1, 3), #3 shares
(1, 2, 1), #1 shares
(0, 3, 1), This system fails because #2 becomes miserly.

In the descending arrangement, the following sequence occurs:

#3, #2, #1
(3, 1, 0), #3 shares
(1, 2, 1), #1 shares
(2, 2, 0), #2 shares
(3, 0, 1), #1 shares
(4, 0, 0), This system fails because #3 becomes miserly.


I know that fewer cats is possible (if a bit trivial). I think it is likely that there is at least one stable configuration involving more cats.

$\endgroup$
6
  • $\begingroup$ I think the cat's numbers can be chosen arbitrarily. So for example, your don't need to necessarily pick #1, #2, #3 in the three cat configuration. See the example in the question. $\endgroup$
    – hexomino
    May 12, 2023 at 22:24
  • $\begingroup$ @hexomino - That's my understanding as well, but no configuration that does so can be a PMM. I will add another lemma explaining why. $\endgroup$
    – Tim C
    May 12, 2023 at 22:48
  • 3
    $\begingroup$ There's at least one PMM with four cats. One of the positions in the repeating cycle, listing the cats in clockwise order with the number in parentheses indicating the number of candies, is #1(0), #2(0), #3(1), #4(4). After six sharings we return to the original position. $\endgroup$
    – Adam S
    May 12, 2023 at 23:03
  • 1
    $\begingroup$ @hexomino - I think we're reading the problem statement differently. As I read it, it says that cats share if cat #n has exactly n candies for n <= M. It doesn't say that they share when n > M, and there's be no reason to specify that condition if they did. In your example, #4 would not share even though it has 4 candies. $\endgroup$
    – Tim C
    May 13, 2023 at 0:04
  • 1
    $\begingroup$ @TimC yes, you are right, I didn't notice that, my apologies. I think I was thrown by the example in the question. $\endgroup$
    – hexomino
    May 13, 2023 at 0:09
4
$\begingroup$

Another partial answer containing a few nice-ish lemmas which unfortunately I couldn't cobble together into a coherent story. At least I was able to use them to accelerate a computer search which yielded a few 8-PMMs.

Theory

Let $p = p_1,p_2,p_3,...,p_N$ be a permutation of the first $N$ cats that when properly seeded form an $N$-PMM. As once the total number of candies has been set there is only a finite number of states the system can only run forever by periodically revisiting previously inhabited states. Let $m = m_1,m_2,m_3,...,m_N$ where $m_i$ is the number of times cat $\#i$ shares during each cycle. Then in a cycle $m_{p_i} p_i$ candies leave position $i$ and the same amount must enter the position. From this we derive constraint

$$(C1)\qquad m_{p_i} p_i=\sum_{\forall j:p_i \in \{p_j+1,p_j+2,...,p_j+j\}} m_j$$

where index arithmetic here and below is understood to wrap around.

Taking the scalar product with the vector $(1,2,3,4,...,N)$ then yields

$$\sum_{i=1}^N i m_{p_i} p_i = \sum_{i=1}^N m_{p_i} \sum_{j=1}^i p_i+j \equiv \sum_{i=1}^N m_{p_i} (i p_i + \frac{i(i+1)}2)\mod N$$

which simplifies to

$$(C2)\qquad \left . 2N \middle | \sum_{i=1}^N m_{p_i} i (i+1) \right . $$

Technically, C2 is fully contained in C1 as it follows from it. It is, however, still useful, for example, for cheap pre-screening in a computer search.

Another potentially useful corollary of C1 can be gained by summing the absolute differences in "flow rate" between adjacent positions:

$$ (C3)\qquad 2\sum_{i=1}^{N-1} m_i \ge \sum_{i=1}^{N}\left | p_im_{p_i}- p_{i+1}m_{p_{i+1}}\right |\ge 2\left ( \max_{i=1}^N i m_i - \min_{i=1}^N i m_i \right ) $$

8-PMMs:

 1 4 7 2 5 6 3 8
 0 0 3 0 2 2 2 8

 1 6 3 4 5 2 7 8
 0 0 0 0 3 0 6 8

 2 5 6 3 7 1 4 8
 0 0 3 1 3 0 2 8

 4 1 2 5 6 3 7 8
 0 0 0 2 4 0 3 8

 7 1 6 3 4 5 2 8
 0 0 2 1 1 4 1 8

 7 4 1 2 5 6 3 8
 3 0 0 0 2 4 0 8
$\endgroup$
5
  • $\begingroup$ So I noticed a property from my attempts was that I could swap the position of the last 2 cats (candy moves with cats), and the resulting set was still a PMM. This isn't always true, but it is true for your second PMM. What makes that really interesting is that the cat order now matches the order in your 5th PMM, which means there are 2 PMMs with identical cat order but different cycles. $\endgroup$ May 14, 2023 at 1:31
  • 1
    $\begingroup$ @JoelRondeau The property you describe is always true. Just do not move all the candy with the cats; leave them all in place except for one candy that goes with the highest cat. Re the different cycles for the same cat arrangement: I checked with the computer and it actually finds lots (dozens) of distinct cycles for some cat arrangements. $\endgroup$
    – loopy walt
    May 14, 2023 at 1:57
  • $\begingroup$ Do you find it plausible that there are some hidden rules which make M-PPM possible iff M is even? $\endgroup$
    – Eric
    May 16, 2023 at 14:32
  • $\begingroup$ So far it seems each cycle must contain an even number of sharings. I wonder why and if this must be true for all PPMs. $\endgroup$
    – Eric
    May 16, 2023 at 15:06
  • $\begingroup$ @Eric I wouldn't read too much into such a small number of small examples. Also, IIRC M=10 did not produce a solution, but I'm not 100% sure of that. $\endgroup$
    – loopy walt
    May 16, 2023 at 16:52
2
$\begingroup$

I decided to see how far I could get just using the numbers in order with cat #1 primed. Which leads to the following:

My notation will simply be lists of numbers
1 2 3 (Cat # in bold)
1 1 1 (Candy #, no moves)
0 2 1 (Candy #, first move, ...)

We start with the identity PMM:

1
1

Next, the still simple 2 cat solution:

1 2
1 1
0 2
1 1
PMM

The next one I found was for:

4 cats
1 2 3 4
1 1 2 1
0 2 2 1
0 0 3 2
1 1 0 3
0 2 0 3
0 0 1 4
1 1 2 1
PMM

And finally,

6 cats
1 2 3 4 5 6
1 1 2 2 3 1
0 2 2 2 3 1
0 0 3 3 3 1
0 0 0 4 4 2
1 1 0 0 5 3
0 2 0 0 5 3
0 0 1 1 5 3
1 1 2 2 0 4
0 2 2 2 0 4
0 0 3 3 0 4
0 0 0 4 1 5
1 1 0 0 2 6
0 2 0 0 2 6
0 0 1 1 2 6
1 1 2 2 3 1
PMM

Now, for numbers in order, I think I have hit the maximum because

Any additional numbers cause cat #3 to have 4 candies.

However, I still intend to try to work through this by

Changing the order in which the cats give out candy. So instead of my current system requiring that before cat n gives it's first candy, all cats 1..n-1 have already given candy, I will loosen that requirement to see if I can find a working order. I will still start with cat 1 and end with cat M, since it's a cycle, so even if I accidently start in the middle, it makes the most sense to show it in that form.

$\endgroup$
4
  • $\begingroup$ If I understand you correctly, by your final paragraph you mean that in cases where more than one cat has the number of candies equal to their own number, you're about to freely choose one of them to share, instead of only the one with the smallest number. $\endgroup$
    – Eric
    May 14, 2023 at 0:05
  • $\begingroup$ “Any additional numbers cause cat #3 to have 4 candies.” Why? Did you prove this? $\endgroup$
    – Eric
    May 14, 2023 at 0:38
  • $\begingroup$ No. I meant that rather than plan it so that for every cat n, all 1..n-1 cats had already distributed candy, I was going to remove that requirement from my attempt (I recognize it is not a requirement of the question). Modified answer to clarify. $\endgroup$ May 14, 2023 at 1:17
  • $\begingroup$ "Any additional numbers..." - not proven, just show for my attempts up to 12. This is mostly moot, given Loopy's superior attempt. Any further attempts will likely use his work as a base. $\endgroup$ May 14, 2023 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.