We have your learning goals covered with Spring and Summer courses available. Enroll today!

Contests & Programs AMC and other contests, summer programs, etc.
AMC and other contests, summer programs, etc.
3 M G
BBookmark  VNew Topic kLocked
Contests & Programs AMC and other contests, summer programs, etc.
AMC and other contests, summer programs, etc.
3 M G
BBookmark  VNew Topic kLocked
G
Topic
First Poster
Last Poster
k a March Highlights and 2025 AoPS Online Class Information
jlacosta   0
Mar 2, 2025
March is the month for State MATHCOUNTS competitions! Kudos to everyone who participated in their local chapter competitions and best of luck to all going to State! Join us on March 11th for a Math Jam devoted to our favorite Chapter competition problems! Are you interested in training for MATHCOUNTS? Be sure to check out our AMC 8/MATHCOUNTS Basics and Advanced courses.

Are you ready to level up with Olympiad training? Registration is open with early bird pricing available for our WOOT programs: MathWOOT (Levels 1 and 2), CodeWOOT, PhysicsWOOT, and ChemWOOT. What is WOOT? WOOT stands for Worldwide Online Olympiad Training and is a 7-month high school math Olympiad preparation and testing program that brings together many of the best students from around the world to learn Olympiad problem solving skills. Classes begin in September!

Do you have plans this summer? There are so many options to fit your schedule and goals whether attending a summer camp or taking online classes, it can be a great break from the routine of the school year. Check out our summer courses at AoPS Online, or if you want a math or language arts class that doesn’t have homework, but is an enriching summer experience, our AoPS Virtual Campus summer camps may be just the ticket! We are expanding our locations for our AoPS Academies across the country with 15 locations so far and new campuses opening in Saratoga CA, Johns Creek GA, and the Upper West Side NY. Check out this page for summer camp information.

Be sure to mark your calendars for the following events:
[list][*]March 5th (Wednesday), 4:30pm PT/7:30pm ET, HCSSiM Math Jam 2025. Amber Verser, Assistant Director of the Hampshire College Summer Studies in Mathematics, will host an information session about HCSSiM, a summer program for high school students.
[*]March 6th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar on Math Competitions from elementary through high school. Join us for an enlightening session that demystifies the world of math competitions and helps you make informed decisions about your contest journey.
[*]March 11th (Tuesday), 4:30pm PT/7:30pm ET, 2025 MATHCOUNTS Chapter Discussion MATH JAM. AoPS instructors will discuss some of their favorite problems from the MATHCOUNTS Chapter Competition. All are welcome!
[*]March 13th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar about Summer Camps at the Virtual Campus. Transform your summer into an unforgettable learning adventure! From elementary through high school, we offer dynamic summer camps featuring topics in mathematics, language arts, and competition preparation - all designed to fit your schedule and ignite your passion for learning.[/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Sunday, Mar 2 - Jun 22
Friday, Mar 28 - Jul 18
Sunday, Apr 13 - Aug 10
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Tuesday, Mar 25 - Jul 8
Sunday, Apr 13 - Aug 10
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21


Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, Mar 23 - Jul 20
Monday, Apr 7 - Jul 28
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Sunday, Mar 16 - Jun 8
Wednesday, Apr 16 - Jul 2
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Monday, Mar 17 - Jun 9
Thursday, Apr 17 - Jul 3
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Sunday, Mar 2 - Jun 22
Wednesday, Apr 16 - Jul 30
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Tuesday, Mar 4 - Aug 12
Sunday, Mar 23 - Sep 21
Wednesday, Apr 23 - Oct 1
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Mar 16 - Sep 14
Tuesday, Mar 25 - Sep 2
Monday, Apr 21 - Oct 13
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Sunday, Mar 23 - Aug 3
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Friday, Apr 11 - Jun 27
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Sunday, Mar 16 - Aug 24
Wednesday, Apr 9 - Sep 3
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Wednesday, Mar 5 - May 21
Tuesday, Jun 10 - Aug 26

Calculus
Sunday, Mar 30 - Oct 5
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Sunday, Mar 23 - Jun 15
Wednesday, Apr 16 - Jul 2
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Friday, Apr 11 - Jun 27
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Tuesday, Mar 4 - May 20
Monday, Mar 31 - Jun 23
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT

Programming

Introduction to Programming with Python
Monday, Mar 24 - Jun 16
Thursday, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Sunday, Mar 30 - Jun 22
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Tuesday, Mar 25 - Sep 2
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Sat & Sun, Apr 26 - Apr 27 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
Mar 2, 2025
0 replies
k i Peer-to-Peer Programs Forum
jwelsh   157
N Dec 11, 2023 by cw357
Many of our AoPS Community members share their knowledge with their peers in a variety of ways, ranging from creating mock contests to creating real contests to writing handouts to hosting sessions as part of our partnership with schoolhouse.world.

To facilitate students in these efforts, we have created a new Peer-to-Peer Programs forum. With the creation of this forum, we are starting a new process for those of you who want to advertise your efforts. These advertisements and ensuing discussions have been cluttering up some of the forums that were meant for other purposes, so we’re gathering these topics in one place. This also allows students to find new peer-to-peer learning opportunities without having to poke around all the other forums.

To announce your program, or to invite others to work with you on it, here’s what to do:

1) Post a new topic in the Peer-to-Peer Programs forum. This will be the discussion thread for your program.

2) Post a single brief post in this thread that links the discussion thread of your program in the Peer-to-Peer Programs forum.

Please note that we’ll move or delete any future advertisement posts that are outside the Peer-to-Peer Programs forum, as well as any posts in this topic that are not brief announcements of new opportunities. In particular, this topic should not be used to discuss specific programs; those discussions should occur in topics in the Peer-to-Peer Programs forum.

Your post in this thread should have what you're sharing (class, session, tutoring, handout, math or coding game/other program) and a link to the thread in the Peer-to-Peer Programs forum, which should have more information (like where to find what you're sharing).
157 replies
jwelsh
Mar 15, 2021
cw357
Dec 11, 2023
k i C&P posting recs by mods
v_Enhance   0
Jun 12, 2020
The purpose of this post is to lay out a few suggestions about what kind of posts work well for the C&P forum. Except in a few cases these are mostly meant to be "suggestions based on historical trends" rather than firm hard rules; we may eventually replace this with an actual list of firm rules but that requires admin approval :) That said, if you post something in the "discouraged" category, you should not be totally surprised if it gets locked; they are discouraged exactly because past experience shows they tend to go badly.
-----------------------------
1. Program discussion: Allowed
If you have questions about specific camps or programs (e.g. which classes are good at X camp?), these questions fit well here. Many camps/programs have specific sub-forums too but we understand a lot of them are not active.
-----------------------------
2. Results discussion: Allowed
You can make threads about e.g. how you did on contests (including AMC), though on AMC day when there is a lot of discussion. Moderators and administrators may do a lot of thread-merging / forum-wrangling to keep things in one place.
-----------------------------
3. Reposting solutions or questions to past AMC/AIME/USAMO problems: Allowed
This forum contains a post for nearly every problem from AMC8, AMC10, AMC12, AIME, USAJMO, USAMO (and these links give you an index of all these posts). It is always permitted to post a full solution to any problem in its own thread (linked above), regardless of how old the problem is, and even if this solution is similar to one that has already been posted. We encourage this type of posting because it is helpful for the user to explain their solution in full to an audience, and for future users who want to see multiple approaches to a problem or even just the frequency distribution of common approaches. We do ask for some explanation; if you just post "the answer is (B); ez" then you are not adding anything useful.

You are also encouraged to post questions about a specific problem in the specific thread for that problem, or about previous user's solutions. It's almost always better to use the existing thread than to start a new one, to keep all the discussion in one place easily searchable for future visitors.
-----------------------------
4. Advice posts: Allowed, but read below first
You can use this forum to ask for advice about how to prepare for math competitions in general. But you should be aware that this question has been asked many many times. Before making a post, you are encouraged to look at the following:
[list]
[*] Stop looking for the right training: A generic post about advice that keeps getting stickied :)
[*] There is an enormous list of links on the Wiki of books / problems / etc for all levels.
[/list]
When you do post, we really encourage you to be as specific as possible in your question. Tell us about your background, what you've tried already, etc.

Actually, the absolute best way to get a helpful response is to take a few examples of problems that you tried to solve but couldn't, and explain what you tried on them / why you couldn't solve them. Here is a great example of a specific question.
-----------------------------
5. Publicity: use P2P forum instead
See https://artofproblemsolving.com/community/c5h2489297_peertopeer_programs_forum.
Some exceptions have been allowed in the past, but these require approval from administrators. (I am not totally sure what the criteria is. I am not an administrator.)
-----------------------------
6. Mock contests: use Mock Contests forum instead
Mock contests should be posted in the dedicated forum instead:
https://artofproblemsolving.com/community/c594864_aops_mock_contests
-----------------------------
7. AMC procedural questions: suggest to contact the AMC HQ instead
If you have a question like "how do I submit a change of venue form for the AIME" or "why is my name not on the qualifiers list even though I have a 300 index", you would be better off calling or emailing the AMC program to ask, they are the ones who can help you :)
-----------------------------
8. Discussion of random math problems: suggest to use MSM/HSM/HSO instead
If you are discussing a specific math problem that isn't from the AMC/AIME/USAMO, it's better to post these in Middle School Math, High School Math, High School Olympiads instead.
-----------------------------
9. Politics: suggest to use Round Table instead
There are important conversations to be had about things like gender diversity in math contests, etc., for sure. However, from experience we think that C&P is historically not a good place to have these conversations, as they go off the rails very quickly. We encourage you to use the Round Table instead, where it is much more clear that all posts need to be serious.
-----------------------------
10. MAA complaints: discouraged
We don't want to pretend that the MAA is perfect or that we agree with everything they do. However, we chose to discourage this sort of behavior because in practice most of the comments we see are not useful and some are frankly offensive.
[list] [*] If you just want to blow off steam, do it on your blog instead.
[*] When you have criticism, it should be reasoned, well-thought and constructive. What we mean by this is, for example, when the AOIME was announced, there was great outrage about potential cheating. Well, do you really think that this is something the organizers didn't think about too? Simply posting that "people will cheat and steal my USAMOO qualification, the MAA are idiots!" is not helpful as it is not bringing any new information to the table.
[*] Even if you do have reasoned, well-thought, constructive criticism, we think it is actually better to email it the MAA instead, rather than post it here. Experience shows that even polite, well-meaning suggestions posted in C&P are often derailed by less mature users who insist on complaining about everything.
[/list]
-----------------------------
11. Memes and joke posts: discouraged
It's fine to make jokes or lighthearted posts every so often. But it should be done with discretion. Ideally, jokes should be done within a longer post that has other content. For example, in my response to one user's question about olympiad combinatorics, I used a silly picture of Sogiita Gunha, but it was done within a context of a much longer post where it was meant to actually make a point.

On the other hand, there are many threads which consist largely of posts whose only content is an attached meme with the word "MAA" in it. When done in excess like this, the jokes reflect poorly on the community, so we explicitly discourage them.
-----------------------------
12. Questions that no one can answer: discouraged
Examples of this: "will MIT ask for AOIME scores?", "what will the AIME 2021 cutoffs be (asked in 2020)", etc. Basically, if you ask a question on this forum, it's better if the question is something that a user can plausibly answer :)
-----------------------------
13. Blind speculation: discouraged
Along these lines, if you do see a question that you don't have an answer to, we discourage "blindly guessing" as it leads to spreading of baseless rumors. For example, if you see some user posting "why are there fewer qualifiers than usual this year?", you should not reply "the MAA must have been worried about online cheating so they took fewer people!!". Was sich überhaupt sagen lässt, lässt sich klar sagen; und wovon man nicht reden kann, darüber muss man schweigen.
-----------------------------
14. Discussion of cheating: strongly discouraged
If you have evidence or reasonable suspicion of cheating, please report this to your Competition Manager or to the AMC HQ; these forums cannot help you.
Otherwise, please avoid public discussion of cheating. That is: no discussion of methods of cheating, no speculation about how cheating affects cutoffs, and so on --- it is not helpful to anyone, and it creates a sour atmosphere. A longer explanation is given in Seriously, please stop discussing how to cheat.
-----------------------------
15. Cutoff jokes: never allowed
Whenever the cutoffs for any major contest are released, it is very obvious when they are official. In the past, this has been achieved by the numbers being posted on the official AMC website (here) or through a post from the AMCDirector account.

You must never post fake cutoffs, even as a joke. You should also refrain from posting cutoffs that you've heard of via email, etc., because it is better to wait for the obvious official announcement. A longer explanation is given in A Treatise on Cutoff Trolling.
-----------------------------
16. Meanness: never allowed
Being mean is worse than being immature and unproductive. If another user does something which you think is inappropriate, use the Report button to bring the post to moderator attention, or if you really must reply, do so in a way that is tactful and constructive rather than inflammatory.
-----------------------------

Finally, we remind you all to sit back and enjoy the problems. :D

-----------------------------
(EDIT 2024-09-13: AoPS has asked to me to add the following item.)

Advertising paid program or service: never allowed

Per the AoPS Terms of Service (rule 5h), general advertisements are not allowed.

While we do allow advertisements of official contests (at the MAA and MATHCOUNTS level) and those run by college students with at least one successful year, any and all advertisements of a paid service or program is not allowed and will be deleted.
0 replies
v_Enhance
Jun 12, 2020
0 replies
k i Stop looking for the "right" training
v_Enhance   50
N Oct 16, 2017 by blawho12
Source: Contest advice
EDIT 2019-02-01: https://blog.evanchen.cc/2019/01/31/math-contest-platitudes-v3/ is the updated version of this.

EDIT 2021-06-09: see also https://web.evanchen.cc/faq-contest.html.

Original 2013 post
50 replies
v_Enhance
Feb 15, 2013
blawho12
Oct 16, 2017
Stanford Math Tournament (SMT) Online 2025
stanford-math-tournament   5
N 29 minutes ago by stanford-math-tournament
[center]Register for Stanford Math Tournament (SMT) Online 2025[/center]


[center] :surf: Stanford Math Tournament (SMT) Online is happening on April 13, 2025! :surf:[/center]

[center]IMAGE[/center]

Register and learn more here:
https://www.stanfordmathtournament.com/competitions/smt-2025-online

When? The contest will take place April 13, 2025. The pre-contest puzzle hunt will take place on April 12, 2025 (optional, but highly encouraged!).

What? The competition features a Power, Team, Guts, General, and Subject (choose two of Algebra, Calculus, Discrete, Geometry) rounds.

Who? You!!!!! Students in high school or below, from anywhere in the world. Register in a team of 6-8 or as an individual.

Where? Online - compete from anywhere!

Check out our Instagram: https://www.instagram.com/stanfordmathtournament/

Register and learn more here:
https://www.stanfordmathtournament.com/competitions/smt-2025-online


[center]IMAGE[/center]


[center] :surf: :surf: :surf: :surf: :surf: [/center]
5 replies
stanford-math-tournament
Mar 9, 2025
stanford-math-tournament
29 minutes ago
AIME Math History
hashbrown2009   82
N an hour ago by stjwyl
Idk why but I wanted to see how good ppl are
Post all your AIME scores ever (if you qualified for USA(J)MO, you may put that score, too)

(Note: Please do not post fake scores. I legit want to see how good ppl are and see how good I am)
I'll start:

5th grade: AIME : 2 lol
6th grade: AIME : 5
7th grade: AIME : 8
8th grade : AIME : 13 USAJMO: 18
9th grade (rn): AIME: 11 (sold)
82 replies
hashbrown2009
Feb 20, 2025
stjwyl
an hour ago
Power of 4: 2011 USAMO #4, 2011 USAJMO #6
tenniskidperson3   129
N 4 hours ago by chenghaohu
Consider the assertion that for each positive integer $n\geq2$, the remainder upon dividing $2^{2^n}$ by $2^n-1$ is a power of $4$. Either prove the assertion or find (with proof) a counterexample.
129 replies
tenniskidperson3
Apr 28, 2011
chenghaohu
4 hours ago
AIME score for college apps
Happyllamaalways   50
N 5 hours ago by Equinox8
What good colleges do I have a chance of getting into with an 11 on AIME? (Any chances for Princeton)

Also idk if this has weight but I had the highest AIME score in my school.
50 replies
Happyllamaalways
Thursday at 1:34 AM
Equinox8
5 hours ago
AMC 10 to AMC 12 Score Translation
MathRook7817   6
N 6 hours ago by MathRook7817
Hey guys, what does a 132 on the AMC 10 translate to on the AMC 12?
6 replies
MathRook7817
Yesterday at 6:44 PM
MathRook7817
6 hours ago
USPHO qual
jlcong   26
N 6 hours ago by jlcong
If I am consistently able to mock a 7, how can I improve in 3 easy steps.

Also will improving my amc10 score indirectly help my on my physics endeavors?
I know I can do it!!!
26 replies
jlcong
Feb 19, 2025
jlcong
6 hours ago
[~$2000 In Prizes!] Register for Crack the Code: A Cybersecurity Hackathon
ayushiayanna   0
6 hours ago
Hello!

We invite you to compete at Crack the Code, a defensive cybersecurity hackathon taking place from March 22nd-23rd at Concordia University, Irvine!.

We’re excited to offer you the opportunity to take part in our hackathon and compete in teams of 2-4 for ~$2000 in prizes, secure internships with professors and CEOs, and create a meaningful project. There is no cost to sign up and you will be provided with a lively working environment, fun side competitions, and most of all, FREE FOOD!

SIGN UP by filling out this form: bit.ly/crackthecode2025! For more information, see our website cui2025.crackthecode.dev or email us at cui@crackthecode.dev. Hope to see you there!

Happy Hacking,

The Crack the Code Team
0 replies
ayushiayanna
6 hours ago
0 replies
2016 Sets
NormanWho   107
N Yesterday at 6:18 PM by ItsBesi
Source: 2016 USAJMO 4
Find, with proof, the least integer $N$ such that if any $2016$ elements are removed from the set ${1, 2,...,N}$, one can still find $2016$ distinct numbers among the remaining elements with sum $N$.
107 replies
NormanWho
Apr 20, 2016
ItsBesi
Yesterday at 6:18 PM
Vertices of a pentagon invariant: 2011 USAMO #2
tenniskidperson3   50
N Yesterday at 6:09 PM by blueprimes
An integer is assigned to each vertex of a regular pentagon so that the sum of the five integers is 2011. A turn of a solitaire game consists of subtracting an integer $m$ from each of the integers at two neighboring vertices and adding $2m$ to the opposite vertex, which is not adjacent to either of the first two vertices. (The amount $m$ and the vertices chosen can vary from turn to turn.) The game is won at a certain vertex if, after some number of turns, that vertex has the number 2011 and the other four vertices have the number 0. Prove that for any choice of the initial integers, there is exactly one vertex at which the game can be won.
50 replies
tenniskidperson3
Apr 28, 2011
blueprimes
Yesterday at 6:09 PM
9 Can I make MOP
Bigtree   14
N Yesterday at 3:58 PM by GlitchyBoy
My dream is to be on IMO team ik thats not going to happen b/c the kids that make it are like 6th mop quals :play_ball:. I somehow got a $208.5$ index this yr (118.5 on amc10+ 9 on AIME) i’m in 7th rn btw first year comp math also. I will grind so hard until like 30 hrs/week. I’m ok at proofs.
14 replies
Bigtree
Mar 9, 2025
GlitchyBoy
Yesterday at 3:58 PM
Geo equals ABsurdly proBEMatic
ihatemath123   72
N Yesterday at 7:15 AM by Ilikeminecraft
Source: 2024 USAMO Problem 5, JMO Problem 6
Point $D$ is selected inside acute $\triangle ABC$ so that $\angle DAC = \angle ACB$ and $\angle BDC = 90^{\circ} + \angle BAC$. Point $E$ is chosen on ray $BD$ so that $AE = EC$. Let $M$ be the midpoint of $BC$.

Show that line $AB$ is tangent to the circumcircle of triangle $BEM$.

Proposed by Anton Trygub
72 replies
ihatemath123
Mar 21, 2024
Ilikeminecraft
Yesterday at 7:15 AM
average FE
KevinYang2.71   73
N Yesterday at 6:42 AM by Ilikeminecraft
Source: USAJMO 2024/5
Find all functions $f:\mathbb{R}\rightarrow\mathbb{R}$ that satisfy
\[
f(x^2-y)+2yf(x)=f(f(x))+f(y)
\]for all $x,y\in\mathbb{R}$.

Proposed by Carl Schildkraut
73 replies
KevinYang2.71
Mar 21, 2024
Ilikeminecraft
Yesterday at 6:42 AM
happy configs
KevinYang2.71   60
N Yesterday at 6:38 AM by Ilikeminecraft
Source: USAJMO 2024/2
Let $m$ and $n$ be positive integers. Let $S$ be the set of integer points $(x,y)$ with $1\leq x\leq 2m$ and $1\leq y\leq 2n$. A configuration of $mn$ rectangles is called happy if each point in $S$ is a vertex of exactly one rectangle, and all rectangles have sides parallel to the coordinate axes. Prove that the number of happy configurations is odd.

Proposed by Serena An and Claire Zhang
60 replies
1 viewing
KevinYang2.71
Mar 20, 2024
Ilikeminecraft
Yesterday at 6:38 AM
[Registration open!] SCMC Spring 2025
Bluesoul   4
N Yesterday at 6:09 AM by Bluesoul
[center]IMAGE[/center]

Registration is open until March 14! Find the form here.

Calling all SoCal high-school math students!
From the University of Southern California, the student-run Southern California Mathematics Competition (SCMC) returns for another year!

Contest info
We plan to hold our Spring 2025 contest on Saturday, 29 March, on USC's University Park Campus. This time we are going to introduce the online version! Competitors not in Socal area could select the online version.

However, the online competition will be considered unofficial; i.e. only onsite, in-person competitors will be eligible for awards, but we might still recognize the top scorers. Online competitors will compete in the Individual Round only. We will send out the Team Round problems after the conclusion of the Individual Round, but we will not be collecting answers to these problems or scoring them.

[list]
[*] The intended target audience for this competition is high-school students, but middle-school students are also welcome to participate!
[*] As is typical, our competition will feature both individual and team-based components: you may choose to compete individually or as part of a team of 4 students, although we strongly encourage you to compete with a team.
[*] This year we are going to have one division only. All competitors will compete in a 20-problem, 120-minute individual round with problems on topics in algebra, number theory, combinatorics, and geometry.
[*] Those competitors on a team will then compete in a 10-problem, 30-minute team round. One or more problems on the team round will feature content covered in a faculty lecture given on the day of the competition.
[*] Before the awards ceremony, we will have a head-to-head MATHCOUNTS Countdown Round-style contest (just for fun). Top 8 competitors face off head-to-head in single-elimination tournament.
[/list]
Detailed information about scoring, timing, etc. can be found on our website.

Additionally, you may view samples of our past work here. If you're looking for resources to study, this page may also be of help.

Hope to see you there, and math on!
- Bluesoul, SCMC Competition Design Chair
4 replies
Bluesoul
Feb 19, 2025
Bluesoul
Yesterday at 6:09 AM
Paths around a circle
tenniskidperson3   44
N Yesterday at 2:10 AM by scannose
Source: 2013 USAMO Problem 2
For a positive integer $n\geq 3$ plot $n$ equally spaced points around a circle. Label one of them $A$, and place a marker at $A$. One may move the marker forward in a clockwise direction to either the next point or the point after that. Hence there are a total of $2n$ distinct moves available; two from each point. Let $a_n$ count the number of ways to advance around the circle exactly twice, beginning and ending at $A$, without repeating a move. Prove that $a_{n-1}+a_n=2^n$ for all $n\geq 4$.
44 replies
tenniskidperson3
Apr 30, 2013
scannose
Yesterday at 2:10 AM
Paths around a circle
G H J
G H BBookmark kLocked kLocked NReply
Source: 2013 USAMO Problem 2
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
tenniskidperson3
2376 posts
#1 • 5 Y
Y by Davi-8191, mobro, megarnie, Adventure10, Mango247
For a positive integer $n\geq 3$ plot $n$ equally spaced points around a circle. Label one of them $A$, and place a marker at $A$. One may move the marker forward in a clockwise direction to either the next point or the point after that. Hence there are a total of $2n$ distinct moves available; two from each point. Let $a_n$ count the number of ways to advance around the circle exactly twice, beginning and ending at $A$, without repeating a move. Prove that $a_{n-1}+a_n=2^n$ for all $n\geq 4$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dinoboy
2903 posts
#2 • 3 Y
Y by mobro, Adventure10, Mango247
darnit MAA why were #2, #3 so much harder than #1 ~_~
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
anchenyao
292 posts
#3 • 3 Y
Y by mobro, Adventure10, Mango247
^I solved 2 and most of 3 but failed #1

Outline
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
iglenini
50 posts
#4 • 3 Y
Y by mobro, Adventure10, Mango247
I showed $ a_n=a_{n-1} + 2 * a_{n-2} $ and it fell from there
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
tenniskidperson3
2376 posts
#5 • 2 Y
Y by mobro, Adventure10
Note that the typo "Let $a_n$ count the number the number of ways" was on the USAMO paper. Not my fault.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
thecmd999
2860 posts
#6 • 2 Y
Y by mobro, Adventure10
I noticed that too.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
antimonyarsenide
875 posts
#7 • 3 Y
Y by mobro, Adventure10, Mango247
Huge recursion solution (remnants of a bijection attempt) took 4 pages but worked :D
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ihatetheaime
22 posts
#8 • 3 Y
Y by mobro, Adventure10, Mango247
Showed the recursive formula an = an-1 + 2an-2, used induction -> base case: show a4 = 16 (a4 = 11, a3 = 5), then by induction proved an + an-1 = 2^n
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Lawrence Wu
267 posts
#9 • 3 Y
Y by mobro, Adventure10, Mango247
Click to reveal hidden text
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ophiophagous
79 posts
#10 • 7 Y
Y by tim9099xxzz, A_Math_Lover, mobro, mijail, Adventure10, Mango247, Om245
Does this work? Label each point 1 or 2, and for every point move the labeled number of points forward if it's the first time you visit the point, and the other move if you're visiting the point a second time. The path ends either on A or on the point right after A. In the first case, there are a_n paths, and in the second case, there's a bijection to the a_(n-1) paths that work for n-1 points by just removing the point right before A.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
zero.destroyer
813 posts
#11 • 4 Y
Y by mobro, Adventure10, Mango247, and 1 other user
@above, I did the same thing.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cag10
10 posts
#12 • 3 Y
Y by mobro, Adventure10, Mango247
If we have a set of points like S1,S2,S3....Sn-1 could you use casework on S1 going to S2(giving a_n-2 comibinations for if the point returns back to S1 and a_n-2 combinations for if the point returns back to S_n-1). What I said I was doing was essentially getting rid of two of the points out of n depending on the case. I did something similar for a_n-1. Not sure if it works. Can anyone tell me?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
1=2
4594 posts
#13 • 3 Y
Y by mobro, Adventure10, Mango247
I had a random bijection: a_n is the number of strings containing only 1s and 2s all summing up to $2n$ such that for any substring that sums to $n$ (these exist always), the number directly to the right of that substring (which might not exist) does not equal the first character in the substring.

I couldn't produce anything with this though. Perhaps someone else can extract an nicer solution out of it.

Comment: The number of such strings without the substring condition turns out to be F_(2n+1).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Yoshi
36 posts
#14 • 13 Y
Y by tim9099xxzz, r31415, Mediocrity, A_Math_Lover, mobro, Enthurelx, Adventure10, Mango247, and 5 other users
/Didn't take the contest, but here's a solution anyways

Constructive (?) Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ALvez
2 posts
#15 • 3 Y
Y by mobro, Adventure10, Mango247
By expanding the points traveled on a n-point circle along a line, we have 2n+1 points, observe
n=3 .......
n=4 .........
hence the recurrence: a_n=2*a_{n-1}
Let induction do rest of the work.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
anchenyao
292 posts
#16 • 4 Y
Y by mobro, sabkx, Adventure10, Mango247
@ALvez then $3|a_n+a_{n-1} \neq 2^n$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ALvez
2 posts
#17 • 3 Y
Y by mobro, Adventure10, Mango247
anchenyao wrote:
@ALvez then $3|a_n+a_{n-1} \neq 2^n$
I didn't see the part about " without repeating a move" It doesn't work then.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
james4l
2172 posts
#18 • 3 Y
Y by mobro, sabkx, Adventure10
also, if it were allowing move repetitions the answer would simply be the $2n$th fibonacci number (well depending on how you index things)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pickten
711 posts
#19 • 3 Y
Y by mobro, Adventure10, Mango247
anchenyao wrote:
^I solved 2 and most of 3 but failed #1

Outline
Same! Although I did casework for the first move.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
hyperbolictangent
961 posts
#20 • 5 Y
Y by Davi-8191, mobro, Adventure10, and 2 other users
Here's another approach, significantly uglier but more straightforward.

Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mssmath
977 posts
#21 • 4 Y
Y by cynthiadu, mobro, Adventure10, Mango247
ophiophagous wrote:
Does this work? Label each point 1 or 2, and for every point move the labeled number of points forward if it's the first time you visit the point, and the other move if you're visiting the point a second time. The path ends either on A or on the point right after A. In the first case, there are a_n paths, and in the second case, there's a bijection to the a_(n-1) paths that work for n-1 points by just removing the point right before A.
Can somebody please explain why the bijection to a_(n-1) paths works.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JSGandora
4216 posts
#22 • 5 Y
Y by gradysocool, mobro, Adventure10, Mango247, and 1 other user
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
leader
339 posts
#23 • 3 Y
Y by mobro, Adventure10, Mango247
I will only explain the steps in my solution it;s kinda long and uses lots of recursive formulas.
I proved the recursion formula by letting $b_n$ be the number of such paths that pass through $A$ after one cycle and $c_n$ the ones that don't. Then $a_n=c_n+b_n$ and for $b_n$ we easily find a recursive formula by considering the first point after $A$(clockwise) that the marker passess twice. So $b_n=2(b_{n-2}+b_{n-3}+....+b_1)$ Now this gives $b_n-b_{n-1}=2b_{n-2}$ giving the wanted formula for $b_n$ but we need it for $c_n$ as well. This can be accomplished similarly by considering the last point before $A$ and first point after $A$ where the marker passess twice. This proves $2(c_{2k+1} - c_{2k})=b_{2k-1}+2$ and $2(c_{2k}-c_{2k-1})=b_{2k-2}-2$. Now we can prove by induction \[b_{2k-1}+2=4c_{2k-1},b_{2k-2}-2=4c_{2k-2}\]
This gives the result $c_n-c_{n-1}=2c_{n-2}$ for all $n$ giving the desired result
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AnonymousBunny
339 posts
#24 • 4 Y
Y by adityaguharoy, mobro, Adventure10, Mango247
Sorry to revive this thread, but I can't understand what the problem means by "without repeating a move". Does it mean that after the marker is moved one unit forward, it has to be moved two units forward (and vice-versa)? Doesn't the whole path get determined by the starting move then?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
tenniskidperson3
2376 posts
#25 • 3 Y
Y by mobro, Adventure10, Mango247
No, it means that if you move forward one from some point, if you return to that point then you must move forward 2. That is, if you go all the way around the circle and hit the point again, then you must choose the other of $1$ and $2$ to move forward.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MathPanda1
1135 posts
#26 • 3 Y
Y by mobro, Adventure10, Mango247
Yoshi wrote:
By treating the node just before $A$ as an alternative start node, the circle passes through n-1 numbers, ends at a start node, then makes a second pass through n-1 numbers ending at a start node. This path then represents that of one drawn out for a circle of size $n-1$.

Can anyone explain what this means and why this is true? Thanks a lot!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MathPanda1
1135 posts
#27 • 2 Y
Y by mobro, Adventure10
Anyone? Thanks.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ABCDE
1963 posts
#28 • 9 Y
Y by niraekjs, mssmath, v_Enhance, Tommy2000, Davi-8191, rashah76, mobro, Adventure10, Mango247
Label each point with the number of times the marker is on it not counting the starting position. Every point must have the marker at some point because otherwise the move from the point before it to the point after it would be made twice. Hence, every point has 1 or 2 since the marker goes around the circle twice. Also, we can't have two consecutive points both labelled 2, because that would mean that on both times around the circle the marker moved from one point to the other, which is a repeated move.

Now, we will split into two cases, first if $A$ is labelled 2. Given any two consecutive 2-labelled points, the paths the marker takes the first and second time must intersect only at those two points and not in between. Hence, two consecutive points in between the two points cannot both be on one path, because the other path will have to contain one of them otherwise. This results in two ways to get from the first 2-point to the next. Either move the marker by 1, 2, 2, ... or by 2, 2, 2, ... and making the appropriate move at the end to get onto the second 2-point. Whichever way the marker goes the first time, it must go the other way the second time. Hence, if there are $k$ points labelled with 2 on the circle, there are $2^k$ paths. The number of ways to choose $k$ non-consecutive points including $A$ on the circle is $\binom{n-k-1}{k-1}$, so there are $\sum_{k=1}\binom{n-k-1}{k-1}2^k$ ways.

For the second case, $A$ is not labelled with 2. The argument for consecutive 2-points that do not have $A$ between them is the same. We will show that there is exactly one way to move between consecutive 2-points that have $A$ between them. Suppose that the closest two 2-points to $A$ are $B$ and $C$, where $B\rightarrow A\rightarrow C$ is in the clockwise direction. Merge the path from $A$ to $C$ at the start and the path from $B$ to $A$ at the end. This creates two paths from $B$ to $C$ that cannot intersect. As in the last case, there are two such choices for one of these paths. However, one of them must pass through $A$, so this uniquely determines the other path as well. Hence, there will be $2^{k-1}$ paths if there are $k$ 2-points. Since there are $\binom{n-k}{k}$ ways to choose $k$ non-consecutive points not including $A$ on the circle, there are $\sum_{k=1}\binom{n-k}{k}2^{k-1}$ ways for this case.

For the final case, we consider if there are none of the points are labelled with 2. If this happens, every point is visited exactly once. The marker travels a total distance of $2n$. If every point is visited exactly once, then it makes exactly $n$ moves, so on each of those moves it must travel a distance of 2. However, if $n$ is even this obviously brings it back to $A$, but if $n$ is odd then this becomes a valid path.

So if $n$ is odd then $a_n=1+\sum_{k=1}\binom{n-k-1}{k-1}2^k+\binom{n-k}{k}2^{k-1}$ and if $n$ is even then $a_n=\sum_{k=1}\binom{n-k-1}{k-1}2^k+\binom{n-k}{k}2^{k-1}$. Substituting the sums into $a_n+a_{n-1}=2^n$, we find an identity that can be easily proven by induction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6857 posts
#29 • 8 Y
Y by A_Math_Lover, mobro, anonman, v4913, HamstPan38825, megarnie, Adventure10, Mango247
Imagine the counter is moving along the set $S = \{0, 1, \dots, 2n\}$ instead, starting at $0$ and ending at $2n$, in jumps of length $1$ and $2$. We can then record the sequence of moves as a matrix of the form \[ 	\begin{bmatrix} 		p_0 & p_1 & p_2 & \dots & p_{n-1} & p_n \\ 		p_n & p_{n+1} & p_{n+2} & \dots & p_{2n-1} & p_{2n} 	\end{bmatrix} \]where $p_i$ denotes whether $i$ was used; in particular, $p_0 = p_{2n} = 1$. (Note that the upper-right and lower-left entries are equal.) Then, the problem amounts to finding the number of such matrices which avoid the contiguous submatrices \[ 	\begin{bmatrix} 0 & 0 \end{bmatrix} 	\qquad 	\begin{bmatrix} 0 \\ 0 \end{bmatrix} 	\qquad 	\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} \]which correspond to forbidding jumps of length greater than $2$, repeating a length $2$ jump and repeating a length $1$ jump.

We will for now ignore the boundary conditions. Instead we say a $2 \times m$ matrix is silver ($m \ge 2$) if it avoids the three shapes above. We can classify silver matrices into two shapes:
  • type B matrices, of the shape $\begin{bmatrix} 	1 & \dots & 1 \\ 	0 & \dots & 0 \end{bmatrix}$, and
  • type C matrices, of the shape $\begin{bmatrix} 	1 & \dots & 0 \\ 	0 & \dots & 1 \end{bmatrix}$.
We let $b_m$ and $c_m$ denote matrices of each type, of size $2 \times m$, and claim the following two recursions for $m \ge 4$: \begin{align*} 	b_m &= c_{m-1} + b_{m-2} + c_{m-2} \\ 	c_m &= b_{m-1} + b_{m-2} + c_{m-2}. \end{align*}We prove the first recursion since the second is analogous. Consider the second column of a type B matrix. If it is $\left[ \begin{smallmatrix} 0 \\ 1 \end{smallmatrix} \right]$ then we find a type C matrix, giving $c_{m-1}$. If it is $\left[ \begin{smallmatrix} 1 \\ 1 \end{smallmatrix} \right]$ then the third column must be either $\left[ \begin{smallmatrix} 0 \\ 1 \end{smallmatrix} \right]$ or $\left[ \begin{smallmatrix} 1 \\ 0 \end{smallmatrix} \right]$, and we get a count of $b_{m-2} + c_{m-2}$.

Using this recursion, the first few values are \[ 	\begin{array}{rrrrrrrr} 		n  & 2 & 3 & 4 & 5 &  6 &  7 &  8 \\ \hline 		b_n & 0 & 2 & 2 & 6 & 10 & 22 & 42 \\ 		c_n & 1 & 1 & 3 & 5 & 11 & 21 & 43 	\end{array} \]and a calculation gives $b_n = \frac{2^{n-1} - 2(-1)^{n-1}}{3}$, $c_n = \frac{2^{n-1} + (-1)^{n-1}}{3}$.

We now relate $a_n$ to $b_m$ and $c_m$. Observe that a matrix as described in the problem is a silver matrix of one of two forms: \[ 	\begin{bmatrix} 		1 & p_1 & p_2 & \dots & p_{n-1} & 0 \\ 		0 & p_{n+1} & p_{n+2} & \dots & p_{2n-1} & 1 	\end{bmatrix} 	\qquad 	\text{or}\qquad 	\begin{bmatrix} 		1 & p_1 & p_2 & \dots & p_{n-1} & 1 \\ 		1 & p_{n+1} & p_{n+2} & \dots & p_{2n-1} & 1 	\end{bmatrix}. \]There are $c_{n+1}$ matrices of the first form and $2b_{n-1} + 2c_{n-1}$ matrices of the second form, thus calculation gives the result \[ a_n = c_{n+1} + 2b_{n-1} + 2c_{n-1} 	= \frac{2^{n+1} + (-1)^{n+1}}{3}. \]
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
vjdjmathaddict
502 posts
#30 • 3 Y
Y by mobro, Adventure10, Mango247
For those who think that the above interpretation was magic. The motivation was to actually remove the circle.
Because it was the main criminal, which was not allowing us to think. one actually realises that the only condition important is the repeatation of the $A$ the starting point.The rest of the proof is nothing but translating the language of the problem in terms of the number of moves. The next tedious part comes in guessing the formula. You can expect the formula to be almost the same and a few calculation shows that too.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
william122
1576 posts
#31 • 5 Y
Y by Vfire, pad, mobro, Adventure10, Mango247
Lemma: Every point is hit at least once in the sequence of moves.

Proof: If a point $P_i$ wasn't hit the first time around, that means that a move of length 2 was performed from $P_{i-1}$. In the second revolution, if $P_{i-1}$ is hit, then a move of length 1 must be performed, meaning $P_i$ will be hit. Otherwise, $P_{i-1}$ was skipped (i.e. a move of length 2 was performed from $P_{i-2}$) which will still result in $P_i$ being hit.

As a corollary, this means that any sequence of moves which skipped $A$ on its first revolution is a valid sequence.

Now, consider a circle of $n$ points, and assign each point a number - either 1 or 2. Consider the move sequence: If a point has not been hit yet, move the amount of steps its number dictates. Otherwise, move the remaining move. As each point is hit during the sequence of moves, all $2^n$ of these numberings will create different move sequences.

Suppose $a_n=k$ of these sequences end up landing on $A$ after exactly 2 revolutions. So, $2^n-k$ of them failed. Now, consider a circle of size $n+1$, with numbers also assigned to all of the points.

We define the $n$-subgame of such a circle to be the result obtained from taking a circle of size $n$ with the first $n$ labels from the current circle.

If the $n$-subgame skips $A$ on its first revolution, that means that it will skip the point before $A$ in the $n+1$ circle, so the point before $A$ will be hit on the second revolution. This means that it must be numbered with a 1.

If the $n$-subgame hits $A$ on its first revolution, then it hits the point before $A$ on its first revolution in the $n+1$ circle. If we label the point with 2, then $A$ will be skipped for the first revolution, and this must be a valid sequence of moves. On the other hand, if we label it with a 1, then we don't affect the result of the $n$-subgame. So, if the $n$-subgame yielded a good sequence of moves, then we will end up on the point before $A$, causing this to be a bad sequence of moves. However, if the $n$-subgame was bad, then this results in hitting $A$ on the second revolution, so this is a good sequence.

To recap, if the $n$-subgame is good, then we can only number the last point with a 1, and if it is bad, then we can number it with 1 or 2. (recall all subgames in the first case were good by lemma.) So, $a_{n+1}=k+2(2^n-k)=2^{n+1}-k$ as desired.
This post has been edited 1 time. Last edited by william122, Mar 26, 2019, 2:14 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
TheUltimate123
1739 posts
#32 • 1 Y
Y by mobro
Let \(B\) be the point directly counterclockwise to \(A\).

Claim: We land on each point either once or twice.

Proof. If we never land on a point, then we jump over it twice. \(\blacksquare\)

Consider a circle with \(n\) points and a marker labeled \(A\), and assign each point either the number \(1\) or the number \(2\); this may be done in \(2^n\) ways. Then proceed around the circle starting from \(A\), such that the first time the marker reaches a certain point labeled \(i\), it moves \(i\) points forward. (If it reaches a point labeled \(i\) a second time, its only option is to move forward \(3-i\) points.)
  • The paths where we reach the point \(A\) the second time around biject with the \(a_n\) ways to advance around a circle with \(n\) points.
  • If we do not reach the point \(A\) the second time around, then we must have jumped over \(A\) from \(B\). Just delete the point \(B\) completely; it is easy to see these paths bijects with the \(a_{n-1}\) ways to advance around a circle with \(n-1\) points.
Hence \(a_n+a_{n-1}=2^n\) as needed.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jj_ca888
2726 posts
#33 • 3 Y
Y by mobro, mijail, sargamsujit
Remark: Cool problem!!! Thankfully, this was not the recursion bash I thought it would be :P Also this is very similar to the solutions provided above by users TheUltimate123 and JSGandora.

Label the points from $1$ to $n$ cycling modulo $n$. Notice that the marker must arrive at each point at least once because otherwise, it jumps over that point twice, which is not possible since that would be using the same move twice. Furthermore, if we arrive at a point $\geq 3$ times, then we use the jump $2$ or jump $1$ moves twice. Hence, each point is reached by the marker once or twice.

Next we establish a bijection between $a_{n-1}$ and $a_n$. Label each point with either $1$ or $2$, and there are $2^n$ ways to do this. For each point, when it is reached the first time, the marker performs the move on the label, and the second time, it performs the move not on the label. We divide these $2^n$ ways of labeling into two groups: one group for those where the marker reaches $A$ twice, and another for when it reaches $A$ once.

For the former group of labelings, we see that they biject to the $a_n$ ways to advance around a $n$ point circle. For the latter group of labelings, we see that they biject to the $a_{n-1}$ ways to advance around a $n-1$ point circle, because the move from $A-1$ to $A+1$ is fixed, hence the remaining $n-1$ points biject to $a_{n-1}$ ways.

Therefore, $a_{n-1} + a_n = 2^n$ for all $n$, as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
GeronimoStilton
1521 posts
#34
Y by
This is not similar to the solutions above.

Assign the points numbers $1,2,\dots,n$ modulo $n$. Within the context of the set of moves, let the points be enumerated as $1,2,\dots,n,n+1,n+2,\dots,2n,2n+1$. Clearly any interval $[a,a+1]$ is contained within exactly one move in a particular sequence of moves.

Define a brick road as a collection of two sequences of moves going from $1\to n+1$ composed such that no two collections of moves contain the same particular individual move $a\to b$. Let the number of brick roads be $b_n$. Observe that
  • $b_1=0$,
  • $b_2=2$,
  • Let index $i+1>1$ denote the first instance of the two sequences agreeing. If $i+1=n+1$ then we have $2$ cases for $b_n$. Else, we get $2b_{n-i}$ for $i>1$. Thus $b_n=2\cdot [1+\sum_{1<i<n}b_{n-i}] $.
  • Counting, we get $b_3=2,b_4=6,b_5=10,b_6=22,b_7=42,\dots$. We claim in general that $b_n = 2\cdot \frac{2^{n-1}-(-1)^{n-1}}{3}$. This holds by induction, since then
    \[b_n = 2\cdot \left[1+2\cdot \frac{2^{n-2}-\frac 32-\frac 12(-1)^{n-1}}{3}\right] = 2\cdot \left[1+\frac{2^{n-1}-3-(-1)^{n-1}}{3}\right] = 2\cdot \frac{2^{n-1}-(-1)^{n-1}}{3}.\]
Then $a_n$ is simply $b_n$ plus the number of sequences of moves from $1\to 2n+1$ which include $n\to n+2$. Now, observe there are a number of types of this: if $1\to 2$ is also one of the moves and so is $2n\to 2n+1$, this is simply $b_{n-2}$. If $1\to 2$ is a move and $2n-1\to 2n+1$ is a move, this is $\frac 12 b_{n-1}$. The same holds if $1\to 3$ is a move and $2n\to 2n+1$ is a move. So far we have then counted $b_n+b_{n-1}+b_{n-2}$ sequences.

Now, suppose $1\to 3,n\to n+2,2n-1\to 2n+1$ are all moves. View the complete sequence of moves as a brick road. By selecting the first point at which the two sequences agree, we count $\frac 12\sum_{1<i<n}b_{n-i}$ possibilities. If there exists no such point, then $n$ must be odd, thus we count $\frac 12+\frac 12(-1)^{n-1}$ additional possible moves. Hence
\[a_n = 2\cdot \frac{2^{n-1}+2^{n-2}+2^{n-3}-(-1)^{n-1}}{3} + \frac{2^{n-2}-\frac 32-\frac 12(-1)^{n-1}}{3}+\tfrac 12+\tfrac 12(-1)^{n-1}=\]\[\frac{7\cdot 2^{n-2}+2^{n-2}-\frac 32-\frac 52(-1)^{n-1}}{3}+\tfrac 12+\tfrac 12(-1)^{n-1} = \frac{2^{n+1}-(-1)^{n+1}}{3}.\]The problem is now dead because
\[a_n+a_{n-1}=\frac{3\cdot 2^n}{3}=2^n.\]
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IAmTheHazard
4999 posts
#35 • 1 Y
Y by sargamsujit
jj_ca888 wrote:
Remark: Cool problem!!! Thankfully, this was not the recursion bash I thought it would be :P Also this is very similar to the solutions provided above by users TheUltimate123 and JSGandora.

Remark: Cool problem!!! Unfortunately, I couldn't find the creative solution I knew existed :P Also this is very similar to the solutions provided above by user GeronimoStilton.

We first do some work to write $a_n$ in terms of a few simpler sequences. Observe that since our first move is from $A$, we either move once or twice from $A$. If we move twice from $A$, we can view the sequence of moves as a pair of two moves, each of length $n$, such that no move from the same point is the same. From here, we can discard the circle entirely and instead view the moves in terms of two horizontal bars filled with blocks of length 1 or 2 such that no two blocks are at the same length and the same spot. Here's an example:
[asy]
size(150);
draw((0,0)--(6,0)--(6,1)--(0,1)--cycle);
draw((0,2)--(6,2)--(6,3)--(0,3)--cycle);
draw((1,0)--(1,1));
draw((2,0)--(2,1));
draw((4,0)--(4,1));
draw((2,2)--(2,3));
draw((3,2)--(3,3));
draw((5,2)--(5,3));
[/asy]
Let the number of ways to fill a pair of bars, both with length $n$, be $b_n$. We will do the recursion work later. Now suppose we move once from $A$. If we let the point counterclockwise from $A$ be $B$, then it is clear that on the first cycle around the circle we reach $B$, then move two points forward from there, and after that move to $A$. Once again, we can discard the circle and view it in terms of bars, but this time the bars are offset from each other.
[asy]
size(150);
draw((0,0)--(6,0)--(6,1)--(0,1)--cycle);
draw((1,2)--(7,2)--(7,3)--(1,3)--cycle);
draw((1,0)--(1,1));
draw((2,0)--(2,1));
draw((4,0)--(4,1));
draw((3,2)--(3,3));
draw((5,2)--(5,3));
[/asy]
[asy]
size(150);
fill((4,0)--(4,1)--(6,1)--(6,0)--cycle,red);
fill((4,2)--(4,3)--(6,3)--(6,2)--cycle,red);
draw((0,0)--(6,0)--(6,1)--(0,1)--cycle);
draw((1,2)--(7,2)--(7,3)--(1,3)--cycle);
draw((1,0)--(1,1));
draw((2,0)--(2,1));
draw((4,0)--(4,1));
draw((3,2)--(3,3));
draw((4,2)--(4,3));
draw((6,2)--(6,3));
[/asy]
In the examples above, the upper example is valid, but the lower is not since the two red blocks are the same length at the same spot. Let the number of ways to fill these two bars of length $n$ be $c_n$. It is clear that
$$a_n=b_n+c_{n-1}.$$Finally, introduce the sequence $(d_n)$, which counts the number of ways to fill two bars: one of length $n$, and the other of length $n-1$. Here's an example:
[asy]
size(150);
draw((0,0)--(6,0)--(6,1)--(0,1)--cycle);
draw((0,2)--(5,2)--(5,3)--(0,3)--cycle);
draw((1,0)--(1,1));
draw((2,0)--(2,1));
draw((4,0)--(4,1));
draw((2,2)--(2,3));
draw((3,2)--(3,3));
[/asy]
Now that we've defined everything, it's time to do the recursion work. First consider $c_n$. Call the bar which is offset to the right the "right bar" and the other bar the "left bar". Consider the following cases:
Case 1: The first block in the left bar is a block of length 1. Then we clearly have $d_n$ ways to fill the remaining blocks.
Case 2: The first block in the left bar is a block of length 2, and the first in the right bar is of length 1. Then we clearly have $d_{n-1}$ ways to fill the remaining blocks.
Case 3: The first blocks in the left and right bars are both of length 2. Then we have $c_{n-2}$ ways to fill the remaining blocks.
Hence we have the recursion
$$c_n=c_{n-2}+d_n+d_{n-1}.$$Now we establish a relationship between $b_n$ and $d_n$. By inspection, we can see that in one of the bars, the rightmost block is of length 1, and in the other the rightmost block is of length 2 (anything else breaks the condition). If we delete/ignore the rightmost blocks, we then get one bar of length $n-1$ and another of $n-2$. Since $d_n$ doesn't count alignment, but there are two distinct possiblities for orientation after deleting the rightmost blocks, we establish $b_n=2d_{n-1}$.
Now we compute $b_n$. Consider the leftmost distance along the block, except from the very left of the block, where two blocks both end (this must exist, since two blocks both end at the right edge of the bar). Here, this distance is marked by the red line:
[asy]
size(150);
draw((0,0)--(6,0)--(6,1)--(0,1)--cycle);
draw((0,2)--(6,2)--(6,3)--(0,3)--cycle);
draw((1,0)--(1,1));
draw((2,0)--(2,1));
draw((4,0)--(4,1));
draw((2,2)--(2,3));
draw((3,2)--(3,3));
draw((5,2)--(5,3));
draw((2,-1)--(2,4),red);
[/asy]
It is not hard to see that it is impossible for this distance to be 1, and for any (integer) distance in $[2,n]$ there is exactly two ways to fill in the blocks to the left of this distance. Hence we have the recursion:
$$b_n=2b_{n-2}+2b_{n-3}+\cdots+2b_0.$$Comparing $b_n$ and $b_{n-1}$ and subtracting, we obtain
$$b_n-b_{n-1}=2b_{n-2} \implies b_n=b_{n-1}+2b_{n-2}.$$Further, it's not hard to compute $b_0=1$ (there is one way to fill in the empty bars: doing nothing), and $b_1=0$ (if necessary, you can also compute a bit more). From here, simple induction is sufficient to show that
$$b_n=\frac{2}{3}(2^{n-1}+(-1)^n),$$which also gives
$$d_n=\frac{1}{3}(2^n-(-1)^n).$$Using this, we can verify the identity
$$b_n+b_{n-1}=2^{n-1},$$as well as
$$d_n+d_{n-1}=2^{n-1} \implies c_n=c_{n-2}+2^{n-1}.$$Further, we can get $c_0=c_1=1$, so
\begin{align*}
c_{2m}&=2^{2m-1}+2^{2m-3}+\cdots+2^1+1\\
c_{2m+1}&=2^{2m}+2^{2m-2}+\cdots+2^2+1.
\end{align*}We're actually done now, since
\begin{align*}
a_{n-1}+a_n&=b_n+b_{n-1}+c_{n-1}+c_{n-2}\\
&=2^{n-1}+2^{n-2}+2^{n-3}+\cdots+2^2+2^1+1+1\\
&=2^{n-1}+2^{n-1}=2^n.\quad \blacksquare
\end{align*}
This post has been edited 2 times. Last edited by IAmTheHazard, Jun 15, 2021, 1:15 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AOPqghj
546 posts
#36 • 1 Y
Y by megarnie
Hey look it's the precursor to samrocksnature @mobro!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
samrocksnature
8791 posts
#37 • 1 Y
Y by megarnie
AOPqghj wrote:
Hey look it's the precursor to samrocksnature @mobro!

??? What is this supposed to mean

@below oops I am observationally challenged
This post has been edited 1 time. Last edited by samrocksnature, Jul 3, 2021, 8:08 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
NathanTien
335 posts
#38 • 2 Y
Y by samrocksnature, megarnie
8charlimit
This post has been edited 1 time. Last edited by NathanTien, Mar 20, 2023, 4:32 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
fclvbfm934
759 posts
#39 • 1 Y
Y by channing421
We populate a boolean $2 \times n$ grid where we write a $1$ if the marker touches that position. For example, in the $2 \times 5$ below for $n = 5$,
$$\begin{bmatrix}
1 & 1 & 0 & 1 & 0 \\
1 & 0 & 1 & 1 & 1
\end{bmatrix}$$this means we move along the circle $1 \to 2 \to 4 \to 1 \to 3 \to 4 \to 5 \to 1$.

Each column of the grid cannot be $\begin{bmatrix} 0 \\ 0 \end{bmatrix}$, so it must be one of $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$, $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, or $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$. Furthermore, three more constraints apply:
  • No two consecutive columns are allowed to repeat. A repeat of $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$ corresponds to repeating the same move, and repeating a $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, or $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$ means we jumped more than 2 spots.
  • The first column must either be $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$ or $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$
  • If we start with $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$, we cannot end with $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$. If we start with $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$ we cannot end with $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$.

My previous solution actually had a bug -- thanks to v_Enhance for catching it below!
Previous edition's incorrect claim

So, we've reduced the problem to the following: we have three states, $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$, $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, and $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$. We must start on either $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$ or $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$. Count the number of ways to hop $n - 1$ times between the states (without repeating a state), and end up on a spot that doesn't violate the third constraint above. This is a routine exercise in recursion: one systematic way to do this is to assume you start at $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, and define $x_k, y_k, z_k$ to be the number of ways to reach $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$, and $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$ respectively after $k$ hops. You would have
\begin{align*}
x_{k+1} &= y_k + z_k \\
y_{k + 1} &= x_k + z_k \\
z_{k + 1} &= x_k + y_k
\end{align*}with initial conditions $(x_0, y_0, z_0) = (1, 0, 0)$. Repeat the exercise, but assume you start at $(1, 1)$, and stitch your results together.

There's a couple of observations that will save us a lot of algebra though. Notice that there's a symmetry among the three states. Specifically, suppose if $x_k$ is the number of ways to start at $(1, 0)$, hop $k$ times, and end up at $(1, 0)$, then $x_k$ should also be the number of ways to start at $(1, 1)$, hop $k$ times, and end up at $(1, 1)$. Furthermore, you can also see that $y_k = z_k$, which can be proven by induction on $k$. Then, we just have
\begin{align*}
a_n &= x_{n-1} + y_{n-1} \qquad \text{start at (1, 0) end at (1, 0) or (1, 1)} \\
&+ y_{n-1} + z_{n-1} \qquad \text{start at (1, 1) end at (1, 0) or (0, 1)}
\end{align*}Focusing on what the problem asks for:
\begin{align*}
a_n + a_{n - 1} &= x_{n-1} + 2y_{n-1} + z_{n-1} + x_{n-2} + 2y_{n-2} + z_{n-2} \\
&= (y_{n-2} + z_{n-2}) + 2(x_{n-2} + z_{n-2}) + (x_{n-2} + y_{n-2}) + x_{n-2} + 2y_{n-2} + z_{n-2} \\
&= 4(x_{n-2} + y_{n-2} + z_{n-2}) \\
&= 4 \cdot 2^{n-2} \\
&= 2^n
\end{align*}as desired. Note that in the last step, we used the observation that $x_k + y_k + z_k = 2^k$, since this corresponds to just counting how many ways there are to hop $k$ times, and there are two choices at each hop. One can also just prove that from the recursion itself.
This post has been edited 1 time. Last edited by fclvbfm934, Sep 4, 2023, 4:54 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6857 posts
#40
Y by
We populate a boolean $2 \times n$ grid where we write a $1$ if the marker touches that position. For example, in the $2 \times 5$ below for $n = 5$,
$$\begin{bmatrix}
1 & 1 & 0 & 1 & 0 \\
1 & 0 & 1 & 1 & 1
\end{bmatrix}$$this means we move along the circle $1 \to 2 \to 4 \to 1 \to 3 \to 4 \to 5 \to 1$.

Each column of the grid cannot be $\begin{bmatrix} 0 \\ 0 \end{bmatrix}$, so it must be one of $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$, $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$, or $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$. Furthermore, no two consecutive columns are allowed to repeat, including wraparound (meaning $n$-th column is not allowed to be equal to $1$-st column). One can easily check that these conditions alone are necessary and sufficient for a sequence being valid.
I think the wraparound condition is not quite correct. As an example for $n=5$, the matrix
\[
\begin{bmatrix}
1 & 1 & 0 & 1 & 1 \\
0 & 1 & 1 & 1 & 0
\end{bmatrix}
\]corresponds to $1 \to 2 \to 4 \to 5 \to 7 \to 8 \to 9 \to 1$. I think this is a valid sequence of moves, but the first and and $n$th column are both $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$. This seems to cause some problems later, for example you wrote $a_n = 2x_n$ written, but I think \[ a_n = \frac{2^{n+1}+(-1)^{n+1}}{3} \]is actually odd for all $n \geq 3$.

I think this is not too hard to fix. The symmetry observation is nice, and does lead to a shorter solution.
This post has been edited 1 time. Last edited by v_Enhance, Sep 4, 2023, 2:23 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6857 posts
#41
Y by
Here is what I think is a repaired version of the solution in post #39. (Note that in my write-up, the matrix has one extra redundant column compared to the notation in fclvbfm934's post).

Record the sequence of moves as a matrix of the form \[ \begin{bmatrix} p_0 & p_1 & p_2 & \dots & p_{n-1} & p_n \\ p_n & p_{n+1} & p_{n+2} & \dots & p_{2n-1} & p_{2n} \end{bmatrix} \]where $p_i = 1$ if the point $i$ was visited by the counter, and $p_i = 0$ if the point was not visited by the counter. Note that $p_0 = p_{2n} = 1$ and the upper-right and lower-left entries are equal. Then, the problem amounts to finding the number of such matrices which avoid the contiguous submatrices \[ \begin{bmatrix} 0 & 0 \end{bmatrix} \qquad \begin{bmatrix} 0 \\ 0 \end{bmatrix} \qquad \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} \]which correspond to forbidding jumps of length greater than $2$, repeating a length $2$ jump and repeating a length $1$ jump.
If we focus on just the three possible column vectors that appear, say \[ \mathbf u \coloneqq \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \qquad \mathbf v \coloneqq \begin{bmatrix} 0 \\ 1 \end{bmatrix}, \qquad \mathbf w \coloneqq \begin{bmatrix} 1 \\ 1 \end{bmatrix} \]then we can instead describe valid matrices as sequences of $n+1$ such column vectors, where no two column vectors are adjacent, and where the boundary condition is that
  • either we start with $\mathbf u$ and end with $\mathbf v$, or
  • either we start with $\mathbf w$ and end with $\mathbf w$.
Let $x_n$ and $y_n$ denote the number of such $2 \times (n+1)$ matrices. (Hence $a_n = x_n + y_n$.) But owing to the symmetry of the setup with $\mathbf u$, $\mathbf v$, $\mathbf w$, we could instead view $x_n$ and $y_n$ as the number of $2 \times (n+1)$ matrices for a fixed starting first column whose final column is the same/different. So we have the recursions \begin{align*} x_{n+1} &= x_n + y_n \\ y_{n+1} &= 2x_n. \end{align*}We also have that \[ 2x_n + y_n = 2^n \]which may either be proved directly from the recursions (using $x_0=1$ and $y_0=0$), or by noting the left-hand side counts the total number of sequences of $n+1$ column vectors with no restrictions on the final column at all (in which case there are simply $2$ choices for each of the $n$ columns after the first one). Thus, \begin{align*} a_{n+1} + a_n &= (x_{n+1} + y_{n+1}) + (x_n + y_n) \\ &= \left( (x_n + y_n) + 2x_n \right) + (x_n + y_n) \\ &= 2(2x_n + y_n) = 2^{n+1} \end{align*}as needed.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
fclvbfm934
759 posts
#42
Y by
Oof yes, you are absolutely right. Thanks for catching this! I patched up my solution upon reading your find, but it looks like I ended up doing essentially the same thing as your fix, with the exception of the redundant column as you point out. I think I even like your redundant column more than mine, to be honest.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Inconsistent
1455 posts
#43
Y by
For each point, give them an instruction sheet: it is either "jump 1 now, jump 2 after" or "jump 2 now, jump 1 after". Notice each point cannot be jumped twice, so two different instruction lists necessarily lead to different outcomes. Now point can be reached more than twice so this instruction list is sufficient. The only cases that don't fall into $a_n$ are when the last jump skips over the original point $A$. Let $A$ be preceded by $A'$, which is preceded by $A''$. In this case, there are two subcases:

First, if we reached $A'$ the first time around and moved one to $A$, then reached $A'$ the second time around and jumped over $A$. In this case, merging $A'$ into $A$ and removing the first jump reduces bijectively to the cases for $n - 1$ where we reach $A$ twice during the process.

Second, if we skipped $A'$ the first time around and the second time around we jumped over $A$. In this case, we always reach $A''$ in the first go around. Thus, if we merge $A$ into $A'$, endowing $A'$ with the initial action of $A$, then this bijects into the cases for $n - 1$ where we skip $A$ during the process by reach $A$ after the second loop.

Thus, since we have accounted for all cases, we have $a_{n-1} +a_n = 2^n$ as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
GrantStar
811 posts
#44
Y by
Huh, I kind of like this. Here's a brief sketch:

Let $s_n$ denote the number of sequences that hit A again. Recursing (lay it out in a line and take cases on where the two paths first meet) gives that $s_n = (1 + s_{n-2} + s_{n-3}+ \dots + s_1)$ or $s_n =  s_{n-1} + 2 s_{n-2}$.

Let $b_n$ be all other sequences. Thus there is a move $X$ from one neighbor of $A$ to the other. If the first jump is of length 2, cut out $X$ and that first jump, leaving us with a valid sequence on $n-2$ points, in $a_{n-2}$ ways. If the first jump is of length one, merge $A$ with its counterclockwise neighbor, and we get an $n-1$ sequence that vists itself. Thus $b_n = a_{n-2}+s_{n-1}$, so $a_n =  s_{n-1} + 2 s_{n-2} + a_{n-2} + s_{n-1}$. From these recursions the extraction follows.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
scannose
964 posts
#45
Y by
this problem was so painful i hate it

sketch (similar to #43):
label the points from 1 to n in clockwise order, with A being the point with label 1.
note that each sequence of moves can be expressed in a binary string of n digits, where the ith digit denotes whether the marker moves one or two moves when first reaching the ith point (for instance, a 0 in the third digit denotes that the marker moves to the fourth point when first landing on the third point, and vice versa). obviously, if a marker reaches a point twice, it will take the opposite move of what it did when it reached the point the first time

it is provable that the marker lands on each point at least once, which implies that any sequence of moves that lands on A after two cycles has an unique binary string representation of length n
on the contrary, any binary string of length n represents a sequence of moves that either lands on A after two cycles, or jumps from point n to point 2 after passing through A the second time.
clearly, the number of binary strings fulfilling the first scenario is equal to a_n, so it suffices to prove that the number of binary strings of length n fulfilling the second scenario is equal to a_n-1, or the number of binary strings of length n-1 that represent a successful sequence of moves

caseworking on the last two digits gives that for any binary string s of length n-2:
- the concatenated strings s01 and s10 always result in a successful sequence;
- exactly one of the strings s00 and s0 result in a successful sequence;
- and similarly, exactly one of the strings s11 and s1 result in a successful sequence.

this result directly implies a_(n-1) + a_n = 2^n, so we are done.
Z K Y
N Quick Reply
G
H
=
a