Extending The Crop Circles Problem

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

nn 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 nn 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?

#Combinatorics #RecurrenceRelations #ComputerScience

Note by Calvin Lin
7 years ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Here's a long solution.

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

Solution: It is easy to see why the case n=1n=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 i=1k1i=(k1)(k)2\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 i=12nki=(2nk)(2nk+1)2\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 (2nk)(2nk+1)2(k1)(k)2=2n22nk+n0\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=4n=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 - 7 years ago

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 - 7 years ago

Log in to reply

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 - 7 years ago

Log in to reply

Yes you are right.

Lokesh Sharma - 7 years ago

If n is a perfect square then it is possible to clear all the plots of land.

Vinay Sipani - 7 years ago

Log in to reply

Note that Charlton's question deals with the case n=9 n = 9 , which is a perfect square. Does the answer agree with your claim?

Calvin Lin Staff - 7 years ago
×

Problem Loading...

Note Loading...

Set Loading...