Waste less time on Facebook — follow Brilliant.
×

Extending The Crop Circles Problem

This is inspired by Driving Round In Circles by Charlton Teo.

\(n\) plots of land are arranged in a circle. Each plot of land has a flower planted on it. A farmer, starting from a certain plot of land, wanted to clear all the plots of land while having some fun. He move one spot in the clockwise direction and cleared that plot of land. Following which, he moved two spots in the clockwise direction and cleared that plot of land. Then, he moved three spots in the clockwise direction and cleared that plot of land. He continues in this manner, skipping 1 more spot each time. However, if he arrives at a plot of land which he has already cleared, he would plant a flower there.

1) For what integers \(n\) will he be able to clear all the plots of land?

2) Does it matter if he doesn't "plant a flower on a cleared plot"? Why, or why not?

Note by Calvin Lin
2 years, 8 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Here's a long solution.

1) Answer: \(\boxed{n=1}\)

Solution: It is easy to see why the case \(n=1\) works.

Lemma 1: I claim that the (k-1)th move and the (2n-k)th move will land on the same spot.

Proof: (k-1)th move will land at \(\sum_{i=1}^{k-1} i = \frac{(k-1)(k)}{2}\)th land to the right of the original position going clockwise.

The (n-k)th move will land at \(\sum_{i=1}^{2n-k} i = \frac{(2n-k)(2n-k+1)}{2}\)th land to the right of the original position going clockwise.

Since \(\frac{(2n-k)(2n-k+1)}{2}-\frac{(k-1)(k)}{2}=2n^2-2nk+n \equiv 0 \) (mod n), the two moves will land on the exact same spot, and thus our claim is true.

The (2n-1)th and the 2n-th moves will land on the same plot, so if the plots of land have flowers on them after (2n-2) moves, they will all have flowers on them after 2n moves.

In (n-1) moves, it is impossible for the farmer to have traveled to all the plots of land. Therefore, using Lemma 1, we see that it is impossible for the farmer to have traveled to all the plots of land after (2n-2) moves. However, since he visits each plot of land an even number of times, none of the plots of land will have been cleared after (2n-2) moves, and therefore, using the previous conclusion, after 2n moves, all of the plots will still have flowers on them after 2n moves.

Now, I claim that if after 2n moves all of the plots still have flowers on them, it is impossible to clear all the plots in any amount of moves. We can see this because the (2n+1)th move will land on the same plot of land as the 1st move and any following moves will be repeats of the first 2n moves. Therefore, it is impossible to clear all the plots of land for any n other than 1 and we are done.

2) Yes, one example of this would be \(n=4\), in which all of the plots will be cleared after 7 moves. This is because in the first part of this problem, whether or not there was a flower in a plot of land depended on how many times the farmer visited the same plot of land and because the farmer visited the same plot multiple times in the first 2n moves. Srnth <3 · 2 years, 8 months ago

Log in to reply

Srnth, it's possible to bit all plots of land in n-1 moves, because the farmer starts somewhere, and after k moves the farmer has been to k+1 plots. I claim that n=2^m works, for all nonnegative integers m. Proof: Label the plots of land 0, ..., n-1 going clockwise, with the farmer starting at 0. Then after k moves the farmer is standing on plot k(k+1)/2. Notice that, given integers k, r with 0<=k<2^u and 0<=r<2^u, if k(k+1)/2 == r(r+1)/2 mod 2^u, then r(r+1)=k(k+1) mod 2^(u+1) -> k and k+1 are r and r+1 multiplied by factors of 2^(u+1), in which case k and k+1 cannot be neighbouring integers, or k==-r-1 and k+1==-r mod 2^(u+1) which is impossible because we required that both k and r be between 0 and 2^u, or k=r, which must be the case. Therefore, all plots of land that the farmer visits between their 0th and (2^u)-1th move are unique, so the farmer has cleared all plots without planting any flowers by the (2^u)-1th move.

I now claim that if n is not a power of 2, then the farmer will never visit all plots, regardless of whether they plant any flowers along the way. Proof: The farmer will be at plot 0 after their n-1th move, because n(n-1)/2 = n*m for some integer m if n is odd ([n-1]/2 is an integer in this case). But the farmer will have been at plot 1 before that (since 0-(n-1) == 1 mod n), so the farmer has hit at most n-1 plots in total by the time they return to 0 after n-1 moves, and from then on they will repeat the cycle (n == 0, n+1 ==1, etc.). Now, if it is impossible for the farmer to hit all plots when there are n plots, we show that it's also impossible to hit all plots if there are 2n plots: Split the field in half, so that we label the plots as 0, ..., n-1, 0', 1', ..., (n-1)' going clockwise from the starting point. As the farmer proceeds, they will hit all of the plots from 0 to n-1 that they would normally hit if there were n plots - possibly some of the plots hit are k' instead of k - within the first n-1 moves. After the n-1st move, the farmer is either at 0 or 0', from which the farmer then moves to the other zero plot, and proceeds to do what they did in the first n-1 moves - only this time hopping over an extra n (adding one extra ' to every plot visited) this time. Once the farmer is done, they'll have been to at most the plots they could visit in a circle of n plots together with the mirror images k' of all those plots, but never to a plot that it's impossible to reach in a circle of n plots.

Therefore, the solution is exactly n=2^u for nonnegative integers u, and it doesn't matter whether the farmer replanted any flowers or not. Rahul Mane · 2 years, 8 months ago

Log in to reply

@Rahul Mane I don't think the problem statement says that he clears the land he initially stands on. If he does then I agree with your solution. I assumed that he didn't clear the initial plot of land he stood on. Srnth <3 · 2 years, 8 months ago

Log in to reply

@Srnth <3 Yes you are right. Lokesh Sharma · 2 years, 7 months ago

Log in to reply

If n is a perfect square then it is possible to clear all the plots of land. Vinay Sipani · 2 years, 8 months ago

Log in to reply

@Vinay Sipani Note that Charlton's question deals with the case \( n = 9 \), which is a perfect square. Does the answer agree with your claim? Calvin Lin Staff · 2 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...