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

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 A Letter to MSM
Arr0w   23
N Sep 19, 2022 by scannose
Greetings.

I have seen many posts talking about commonly asked questions, such as finding the value of $0^0$, $\frac{1}{0}$,$\frac{0}{0}$, $\frac{\infty}{\infty}$, why $0.999...=1$ or even expressions of those terms combined as if that would make them defined. I have made this post to answer these questions once and for all, and I politely ask everyone to link this post to threads that are talking about this issue.
[list]
[*]Firstly, the case of $0^0$. It is usually regarded that $0^0=1$, not because this works numerically but because it is convenient to define it this way. You will see the convenience of defining other undefined things later on in this post.

[*]What about $\frac{\infty}{\infty}$? The issue here is that $\infty$ isn't even rigorously defined in this expression. What exactly do we mean by $\infty$? Unless the example in question is put in context in a formal manner, then we say that $\frac{\infty}{\infty}$ is meaningless.

[*]What about $\frac{1}{0}$? Suppose that $x=\frac{1}{0}$. Then we would have $x\cdot 0=0=1$, absurd. A more rigorous treatment of the idea is that $\lim_{x\to0}\frac{1}{x}$ does not exist in the first place, although you will see why in a calculus course. So the point is that $\frac{1}{0}$ is undefined.

[*]What about if $0.99999...=1$? An article from brilliant has a good explanation. Alternatively, you can just use a geometric series. Notice that
\begin{align*}
\sum_{n=1}^{\infty} \frac{9}{10^n}&=9\sum_{n=1}^{\infty}\frac{1}{10^n}=9\sum_{n=1}^{\infty}\biggr(\frac{1}{10}\biggr)^n=9\biggr(\frac{\frac{1}{10}}{1-\frac{1}{10}}\biggr)=9\biggr(\frac{\frac{1}{10}}{\frac{9}{10}}\biggr)=9\biggr(\frac{1}{9}\biggr)=\boxed{1}
\end{align*}
[*]What about $\frac{0}{0}$? Usually this is considered to be an indeterminate form, but I would also wager that this is also undefined.
[/list]
Hopefully all of these issues and their corollaries are finally put to rest. Cheers.

2nd EDIT (6/14/22): Since I originally posted this, it has since blown up so I will try to add additional information per the request of users in the thread below.

INDETERMINATE VS UNDEFINED

What makes something indeterminate? As you can see above, there are many things that are indeterminate. While definitions might vary slightly, it is the consensus that the following definition holds: A mathematical expression is be said to be indeterminate if it is not definitively or precisely determined. So how does this make, say, something like $0/0$ indeterminate? In analysis (the theory behind calculus and beyond), limits involving an algebraic combination of functions in an independent variable may often be evaluated by replacing these functions by their limits. However, if the expression obtained after this substitution does not provide sufficient information to determine the original limit, then the expression is called an indeterminate form. For example, we could say that $0/0$ is an indeterminate form.

But we need to more specific, this is still ambiguous. An indeterminate form is a mathematical expression involving at most two of $0$, $1$ or $\infty$, obtained by applying the algebraic limit theorem (a theorem in analysis, look this up for details) in the process of attempting to determine a limit, which fails to restrict that limit to one specific value or infinity, and thus does not determine the limit being calculated. This is why it is called indeterminate. Some examples of indeterminate forms are
\[0/0, \infty/\infty, \infty-\infty, \infty \times 0\]etc etc. So what makes something undefined? In the broader scope, something being undefined refers to an expression which is not assigned an interpretation or a value. A function is said to be undefined for points outside its domain. For example, the function $f:\mathbb{R}^{+}\cup\{0\}\rightarrow\mathbb{R}$ given by the mapping $x\mapsto \sqrt{x}$ is undefined for $x<0$. On the other hand, $1/0$ is undefined because dividing by $0$ is not defined in arithmetic by definition. In other words, something is undefined when it is not defined in some mathematical context.

WHEN THE WATERS GET MUDDIED

So with this notion of indeterminate and undefined, things get convoluted. First of all, just because something is indeterminate does not mean it is not undefined. For example $0/0$ is considered both indeterminate and undefined (but in the context of a limit then it is considered in indeterminate form). Additionally, this notion of something being undefined also means that we can define it in some way. To rephrase, this means that technically, we can make something that is undefined to something that is defined as long as we define it. I'll show you what I mean.

One example of making something undefined into something defined is the extended real number line, which we define as
\[\overline{\mathbb{R}}=\mathbb{R}\cup \{-\infty,+\infty\}.\]So instead of treating infinity as an idea, we define infinity (positively and negatively, mind you) as actual numbers in the reals. The advantage of doing this is for two reasons. The first is because we can turn this thing into a totally ordered set. Specifically, we can let $-\infty\le a\le \infty$ for each $a\in\overline{\mathbb{R}}$ which means that via this order topology each subset has an infimum and supremum and $\overline{\mathbb{R}}$ is therefore compact. While this is nice from an analytic standpoint, extending the reals in this way can allow for interesting arithmetic! In $\overline{\mathbb{R}}$ it is perfectly OK to say that,
\begin{align*}
a + \infty = \infty + a & = \infty, & a & \neq -\infty \\
a - \infty = -\infty + a & = -\infty, & a & \neq \infty \\
a \cdot (\pm\infty) = \pm\infty \cdot a & = \pm\infty, & a & \in (0, +\infty] \\
a \cdot (\pm\infty) = \pm\infty \cdot a & = \mp\infty, & a & \in [-\infty, 0) \\
\frac{a}{\pm\infty} & = 0, & a & \in \mathbb{R} \\
\frac{\pm\infty}{a} & = \pm\infty, & a & \in (0, +\infty) \\
\frac{\pm\infty}{a} & = \mp\infty, & a & \in (-\infty, 0).
\end{align*}So addition, multiplication, and division are all defined nicely. However, notice that we have some indeterminate forms here which are also undefined,
\[\infty-\infty,\frac{\pm\infty}{\pm\infty},\frac{\pm\infty}{0},0\cdot \pm\infty.\]So while we define certain things, we also left others undefined/indeterminate in the process! However, in the context of measure theory it is common to define $\infty \times 0=0$ as greenturtle3141 noted below. I encourage to reread what he wrote, it's great stuff! As you may notice, though, dividing by $0$ is undefined still! Is there a place where it isn't? Kind of. To do this, we can extend the complex numbers! More formally, we can define this extension as
\[\mathbb{C}^*=\mathbb{C}\cup\{\tilde{\infty}\}\]which we call the Riemann Sphere (it actually forms a sphere, pretty cool right?). As a note, $\tilde{\infty}$ means complex infinity, since we are in the complex plane now. Here's the catch: division by $0$ is allowed here! In fact, we have
\[\frac{z}{0}=\tilde{\infty},\frac{z}{\tilde{\infty}}=0.\]where $\tilde{\infty}/\tilde{\infty}$ and $0/0$ are left undefined. We also have
\begin{align*}
z+\tilde{\infty}=\tilde{\infty}, \forall z\ne -\infty\\
z\times \tilde{\infty}=\tilde{\infty}, \forall z\ne 0
\end{align*}Furthermore, we actually have some nice properties with multiplication that we didn't have before. In $\mathbb{C}^*$ it holds that
\[\tilde{\infty}\times \tilde{\infty}=\tilde{\infty}\]but $\tilde{\infty}-\tilde{\infty}$ and $0\times \tilde{\infty}$ are left as undefined (unless there is an explicit need to change that somehow). One could define the projectively extended reals as we did with $\mathbb{C}^*$, by defining them as
\[{\widehat {\mathbb {R} }}=\mathbb {R} \cup \{\infty \}.\]They behave in a similar way to the Riemann Sphere, with division by $0$ also being allowed with the same indeterminate forms (in addition to some other ones).
23 replies
Arr0w
Feb 11, 2022
scannose
Sep 19, 2022
k i Marathon Threads
LauraZed   0
Jul 2, 2019
Due to excessive spam and inappropriate posts, we have locked the Prealgebra and Beginning Algebra threads.

We will either unlock these threads once we've cleaned them up or start new ones, but for now, do not start new marathon threads for these subjects. Any new marathon threads started while this announcement is up will be immediately deleted.
0 replies
LauraZed
Jul 2, 2019
0 replies
k i Basic Forum Rules and Info (Read before posting)
jellymoop   368
N May 16, 2018 by harry1234
f (Reminder: Do not post Alcumus or class homework questions on this forum. Instructions below.) f
Welcome to the Middle School Math Forum! Please take a moment to familiarize yourself with the rules.

Overview:
[list]
[*] When you're posting a new topic with a math problem, give the topic a detailed title that includes the subject of the problem (not just "easy problem" or "nice problem")
[*] Stay on topic and be courteous.
[*] Hide solutions!
[*] If you see an inappropriate post in this forum, simply report the post and a moderator will deal with it. Don't make your own post telling people they're not following the rules - that usually just makes the issue worse.
[*] When you post a question that you need help solving, post what you've attempted so far and not just the question. We are here to learn from each other, not to do your homework. :P
[*] Avoid making posts just to thank someone - you can use the upvote function instead
[*] Don't make a new reply just to repeat yourself or comment on the quality of others' posts; instead, post when you have a new insight or question. You can also edit your post if it's the most recent and you want to add more information.
[*] Avoid bumping old posts.
[*] Use GameBot to post alcumus questions.
[*] If you need general MATHCOUNTS/math competition advice, check out the threads below.
[*] Don't post other users' real names.
[*] Advertisements are not allowed. You can advertise your forum on your profile with a link, on your blog, and on user-created forums that permit forum advertisements.
[/list]

Here are links to more detailed versions of the rules. These are from the older forums, so you can overlook "Classroom math/Competition math only" instructions.
Posting Guidelines
Update on Basic Forum Rules
What belongs on this forum?
How do I write a thorough solution?
How do I get a problem on the contest page?
How do I study for mathcounts?
Mathcounts FAQ and resources
Mathcounts and how to learn

As always, if you have any questions, you can PM me or any of the other Middle School Moderators. Once again, if you see spam, it would help a lot if you filed a report instead of responding :)

Marathons!
Relays might be a better way to describe it, but these threads definitely go the distance! One person starts off by posting a problem, and the next person comes up with a solution and a new problem for another user to solve. Here's some of the frequently active marathons running in this forum:
[list][*]Algebra
[*]Prealgebra
[*]Proofs
[*]Factoring
[*]Geometry
[*]Counting & Probability
[*]Number Theory[/list]
Some of these haven't received attention in a while, but these are the main ones for their respective subjects. Rather than starting a new marathon, please give the existing ones a shot first.

You can also view marathons via the Marathon tag.

Think this list is incomplete or needs changes? Let the mods know and we'll take a look.
368 replies
jellymoop
May 8, 2015
harry1234
May 16, 2018
Inspired by m4thbl3nd3r
sqing   0
5 minutes ago
Source: Own
Let $ a,b,c>0 $ and $a+b+c=3$. Prove that$$a^3b+b^3c+c^3a+\frac{1419}{256}abc\le\frac{2187}{256}$$Equality holds when $ a=b=c=1 $ or $ a=0,b=\frac{9}{4},c=\frac{3}{4} $ or $ a=\frac{3}{4} ,b=0,c=\frac{9}{4} $
or $ a=\frac{9}{4} ,b=\frac{3}{4},c=0. $
0 replies
2 viewing
sqing
5 minutes ago
0 replies
a+b+c=3 inequality
jokehim   1
N 14 minutes ago by teomihai
Source: my problem
Problem. Given non-negative real numbers $a,b,c$ satisfying $a+b+c=3.$ Prove that $$\frac{1}{a+b+1}+\frac{1}{b+c+1}+\frac{1}{c+a+1}\le \frac{9}{ab+bc+ca+6}.$$Proposed by Phan Ngoc Chau
1 reply
1 viewing
jokehim
3 hours ago
teomihai
14 minutes ago
Interesting inequality
sqing   7
N 16 minutes ago by SunnyEvan
Source: Own
Let $ a,b> 0$ and $ a+b=1 . $ Prove that
$$ \frac{1}{a}+\frac{1}{b}\geq \frac{4+\frac{k}{16}}{1+ ka^3b^3}$$Where $32\geq  k>0 .$
Let $ a,b> 0$ and $ a+b=1 . $ Prove that
$$ \frac{1}{a}+\frac{1}{b}\geq \frac{4+\frac{k}{64}}{1+ ka^4b^4}$$Where $\frac{256}{3}\geq  k>0 .$
$$ \frac{1}{a}+\frac{1}{b}\geq \frac{5}{1+16a^3b^3}$$$$ \frac{1}{a}+\frac{1}{b}\geq \frac{6}{1+32a^3b^3}$$$$ \frac{1}{a}+\frac{1}{b}\geq \frac{5}{1+64a^4b^4}$$$$ \frac{1}{a}+\frac{1}{b}\geq \frac{\frac{16}{3}}{1+\frac{256}{3}a^4b^4}$$
7 replies
2 viewing
sqing
2 hours ago
SunnyEvan
16 minutes ago
Is this NT?
navi_09220114   1
N 18 minutes ago by mashumaro
Source: Malaysian IMO TST 2025 P11
Let $n$, $d$ be positive integers such that $d>\frac{n}{2}$. Suppose $a_1, a_2,\cdots,a_{d+2}$ is a sequence of integers satisfying $a_{d+1}=a_1$, $a_{d+2}=a_2$, and for all indices $1\le i_1<i_2<\cdots <i_s\le d$, $$a_{i_1}+a_{i_2}+\cdots+a_{i_s}\not\equiv 0\pmod n$$Prove that there exists $1\le i\le d$ such that $$a_{i+1}\equiv a_i \pmod n \quad \text{or} \quad a_{i+1}\equiv a_i+a_{i+2} \pmod n$$
Proposed by Yeoh Zi Song
1 reply
navi_09220114
3 hours ago
mashumaro
18 minutes ago
Mathcounts state iowa
iwillregretthisnamelater   12
N 3 hours ago by iwastedmyusername
Ok I’m a 6th grader in Iowa who got 38 in chapter which was first, so what are the chances of me getting in nats? I should feel confident but I don’t. I have a week until states and I’m getting really anxious. What should I do? And also does the cdr count in Iowa? Because I heard that some states do cdr for fun or something and that it doesn’t count to final standings.
12 replies
iwillregretthisnamelater
Mar 20, 2025
iwastedmyusername
3 hours ago
Factoring Marathon
pican   1437
N Today at 5:59 AM by aidan0626
Hello guys,
I think we should start a factoring marathon. Post your solutions like this SWhatever, and your problems like this PWhatever. Please make your own problems, and I'll start off simple: P1
1437 replies
pican
Aug 4, 2015
aidan0626
Today at 5:59 AM
Confirming a number theoretical result
OlympusHero   1
N Today at 5:14 AM by aidan0626
Prove that $a \cdot c^{-1}+b \cdot d^{-1} = (ad+bc) \cdot (cd)^{-1} \pmod n$ where $\gcd(c,n) = \gcd(d,n) = 1$.
1 reply
OlympusHero
Today at 5:10 AM
aidan0626
Today at 5:14 AM
How to convert base numbers directly without using base 10
DSL13   13
N Today at 5:08 AM by giratina3
I don't understand the topic of how you convert bases directly without going from base 10 to the base that I desire. How do I get from one base to another without the use of base 10?

I watched videos on it but I don't really get the idea.
13 replies
DSL13
Mar 11, 2021
giratina3
Today at 5:08 AM
Good Mocks for STate
Existing_Human1   1
N Today at 4:26 AM by giratina3
Hello Community!

I am wondering what are the best mocks for state, with solutions
1 reply
Existing_Human1
Yesterday at 11:52 PM
giratina3
Today at 4:26 AM
Mathcounts STRATEGIES
Existing_Human1   27
N Today at 4:23 AM by giratina3
Hello commuinty!

I am wondering what your strategies are for mathcounts. Please note I do not mean tips. These can be for all rounds, but please specify. BTW, this is for state, but it can apply to any competition.

Ex:
Team - sit in a specific order
Target - do the easiest first
Sprint - go as fast as possible

I just made up the examples, and you will probably have better strategies, so if you want to help out, please do
27 replies
Existing_Human1
Thursday at 7:27 PM
giratina3
Today at 4:23 AM
Problem of the week
evt917   36
N Today at 4:20 AM by giratina3
Whenever possible, I will be posting problems twice a week! They will be roughly of AMC 8 difficulty. Have fun solving! Also, these problems are all written by myself!

First problem:

$20^{16}$ has how many digits?
36 replies
evt917
Mar 5, 2025
giratina3
Today at 4:20 AM
Tam giác nội tiếp
chunchun.math.2010   1
N Today at 2:19 AM by aidan0626
Bài 1:Cho tam giác abc nội tiếp đường tròn (o), đường cao ad (d ∈ bc). qua a kẻ đường song song với bc cắt (o) tại t. chứng minh rằng dt đi qua trọng tâm của tam giác abc.
Bài 2: Cho tứ giác ngoại tiếp abcd. p là một điểm bất kì trên cd. j, k, l lần lượt là tâm đường tròn nội tiếp của các tam giác apb, apd, bpc. chứng minh rằng ∠ajk + ∠bjl = 180°.
1 reply
chunchun.math.2010
Today at 2:06 AM
aidan0626
Today at 2:19 AM
The daily problem!
Leeoz   2
N Yesterday at 10:06 PM by c_double_sharp
Every day, I will try to post a new problem for you all to solve! If you want to post a daily problem, you can! :)

Please hide solutions and answers, hints are fine though! :)

The first problem is:
[quote=March 21st Problem]Alice flips a fair coin until she gets 2 heads in a row, or a tail and then a head. What is the probability that she stopped after 2 heads in a row? Express your answer as a common fraction.[/quote]
2 replies
Leeoz
Yesterday at 10:01 PM
c_double_sharp
Yesterday at 10:06 PM
Really Nasty MathCounts Problem
ilikemath247365   17
N Yesterday at 9:58 PM by BS2012
2019 MathCounts National Sprint #29

How many of the first $100,000$ positive integers have no single-digit prime factors?


Side note: Just HOW are they supposed to solve this in like 5 minutes?
17 replies
ilikemath247365
Mar 14, 2025
BS2012
Yesterday at 9:58 PM
primitive polyominoes
N.T.TUAN   28
N Mar 20, 2025 by quantam13
Source: USAMO 2007
An animal with $n$ cells is a connected figure consisting of $n$ equal-sized cells[1].

A dinosaur is an animal with at least $2007$ cells. It is said to be primitive it its cells cannot be partitioned into two or more dinosaurs. Find with proof the maximum number of cells in a primitive dinosaur.

(1) Animals are also called polyominoes. They can be defined inductively. Two cells are adjacent if they share a complete edge. A single cell is an animal, and given an animal with $n$ cells, one with $n+1$ cells is obtained by adjoining a new cell by making it adjacent to one or more existing cells.
28 replies
N.T.TUAN
Apr 26, 2007
quantam13
Mar 20, 2025
primitive polyominoes
G H J
Source: USAMO 2007
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
N.T.TUAN
3595 posts
#1 • 5 Y
Y by Adventure10, Mango247, and 3 other users
An animal with $n$ cells is a connected figure consisting of $n$ equal-sized cells[1].

A dinosaur is an animal with at least $2007$ cells. It is said to be primitive it its cells cannot be partitioned into two or more dinosaurs. Find with proof the maximum number of cells in a primitive dinosaur.

(1) Animals are also called polyominoes. They can be defined inductively. Two cells are adjacent if they share a complete edge. A single cell is an animal, and given an animal with $n$ cells, one with $n+1$ cells is obtained by adjoining a new cell by making it adjacent to one or more existing cells.
This post has been edited 1 time. Last edited by phxu, Mar 27, 2016, 8:39 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
t0rajir0u
12167 posts
#2 • 5 Y
Y by Adventure10, Mango247, dragon888, MS_asdfgzxcvb, and 1 other user
A primitive $n$-saur can have at most $4n-3$ cells.

Consider a cross formation consisting of a center cell and four extensions of length $n-1$. Of any partitioning of this animal, one partition contains the center cell. The other partitions can have length at most $n-1$, so this animal is $n$-primitive.

Pick an $n$-subanimal out of a primitive $n$-saur that minimizes the number of animals into which the other cells are divided, and consider the remaining cells. If there are more than $3(n-1)$ of them, and they divide themselves into $3$ or less animals, one of them must have at least $n$ cells, contradiction. If they divide themselves into $4$ or more animals, these animals must be attached to the $n$-subanimal at at least two distinct cells (since a cell can only have three free edges for $n > 1$), so it is possible to create another $n$-subanimal by combining one of the other animals with it and removing some cells around the location where the others are attached. This produces an $n$-subanimal such that the other cells are divided into less animals; contradiction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
epitomy01
240 posts
#3 • 2 Y
Y by Adventure10, Mango247
Another solution (I hope it is correct):
The construction is same.
Now say we have a primitive animal with $ 4n-2$ cells, that cannot be divided into two animals, each with at least $ n$ cells.
Going downwards from the top of animal, we can divide the animal into rows. Suppose the animal has $ k$ rows, and the $ i$-th row has $ a_{i}$ cells.
If $ n \leq a_{1} + ... + a_{i} \leq 3n-2$ for some value of $ i$, cutting horizontally between the $ i$-th and $ i+1$-th rows would give two animals, each with at least $ n$ cells. Contradiction.
Thus $ a_{1} + ... + a_{i} \leq n-1$, or $ a_{1} + ... + a_{i} \geq 3n-1$. From this, clearly we have for some value of $ i$ that: $ a_{1} + ... + a_{i-1} \leq n-1$ and $ a_{1} + ... + a_{i} \geq 3n-1$, so $ a_{i} \geq 2n$ for some $ i$.
Now consider the $ i$-th row. Since it has at least $ 2n$ cells, divide the animal vertically in the middle of this string of horizontal cells. Now we have two animals, each with at least $ n$ cells. Contradiction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MellowMelon
5850 posts
#4 • 9 Y
Y by Adventure10, sixoneeight, mathleticguyyy, Spectator, vsamc, dragon888, Scilyse, OronSH, ihatemath123
epitomy, do I misunderstand your solution, or is this shape a counterexample to your argument?

X _ X X X
X _ X _ _
X X X X X
_ _ X _ X
X X X _ X


One of your claims was that splitting between the $ i$th and $ i+1$th row splits the animal into to two new ones, right? Here, splitting the animal between the 1st and 2nd rows creates three new animals, not two.

Your argument was basically my solution, except that you have to do more than just use rows. I couldn't get it to work without turning the animal into a graph, and then into a tree.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
t0rajir0u
12167 posts
#5 • 1 Y
Y by Adventure10
Graph theory was apparently the most natural way to approach this. In particular, I believe a nice solution I read considered a minimal spanning tree (which appears to be essentially what I did in my solution).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
epitomy01
240 posts
#6 • 1 Y
Y by Adventure10
Quote:
One of your claims was that splitting between the ith and i+1th row splits the animal into to two new ones, right? Here, splitting the animal between the 1st and 2nd rows creates three new animals, not two.
Yes, sorry that is a flaw in my proof.
Could you post your proof using graph theory? I don't understand how to fix my proof.
Also, what is a spanning tree?
This post has been edited 1 time. Last edited by epitomy01, Dec 6, 2007, 5:04 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MellowMelon
5850 posts
#7 • 2 Y
Y by Adventure10, Mango247
Here's a sketch of my proof. We don't get our individual problem scores back, but I estimate based on my total score and my solution quality for each problem that this was scored as a $ 6/7$.

Turn the animal into a graph, then into a tree. Prove or state as well-known that there is a vertex with degree 1, and start there. Mark that vertex 1. Now go along vertices, increasing the number by 1 each time (so 1,2,3...), until you reach a vertex with more than degree 2. Go towards the vertex that is joined to more vertices; i.e. the subgraph created by splitting it off from the vertex you're at now is of the greatest size. For this vertex, count up all of the vertices on the other paths you did not take, and in addition to adding 1, also add the total you just computed.

You can prove that if you ever write down a number in between $ 2008$ and $ n - 2007$ (where $ n$ is the size of the animal), there is a way to partition the animal into two dinosaurs. (I believe I lost my point from not stating this proof) Then by using the fact that the maximum degree of any vertex is 4, you can prove that a number in this interval must be assumed if $ n > 8025$, and you're done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JBL
16123 posts
#8 • 2 Y
Y by Adventure10, Mango247
epitomy01 wrote:
Also, what is a spanning tree?

Search engines are your friend. Any connected graph $ G$ contains a spanning tree $ T$, a tree such that $ V(T) = V(G)$ and $ E(T) \subset E(G)$. ($ V$ = the set of vertices of, $ E$ = the set of edges of.)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
SkinnySanta
215 posts
#9 • 5 Y
Y by arandomperson123, Adventure10, Mango247, panche, 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.
junioragd
314 posts
#10 • 2 Y
Y by Adventure10, Mango247
The answer is 4*n-3.Now,for example,pick an animal with center cell and n-1 cells from each direction.Now,lets prove we can partitate 4*n-2.We do this by simple induction on n.For n=1,2 is obvious.Now,we pick a subanimal with 4*n-6 cells(it is obvious we can do this) and from the inductive hypothesis we have that this can be partioned in two subanimals with n-1 cells or more.Now,if both of them have more than n-1,we are done,so we suppose they don't.Now,we add 4 cells.Now,if some of them touches an animal with n-1,we are finished,so suppose not.Now,the subanimal must be adjacent to the bigger subanimal at least at one cell,so if we pick that cell,it can partitate the bigger subanimal into at most 3 parts an the bigger subanimal now has 3*n-2 cells(cause the 4 we added must form a subanimal with it by assumption),so there exist one with n cells and the rest is a one subanimal,so we are done
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
efang
593 posts
#11 • 1 Y
Y by Adventure10
Optimal construction is shown above

To show that $4n-2$ doesn't work, put the n-saur onto the coordinate plane and place all the cells as integer coordinates and draw edges between adjacent cells. In this case, a connected graph is a partition and if 2 disjoint subgraphs would represent 2 different partitions.

We say 2 cells are connected if there is a path between them that doesn't go through the origin. Consider the set of cells which are connected to $\{(-1,0), (1,0), (0,1), (0,-1)\}$ (It is possible that a cell is connected to more than one of these, and it is also possible that one of the cells in this set is not actually on the n-saur and thus its connected set has size 0).

By the pigeonhole principle, one of these sets has $n-1$ points. WLOG let that set be the connected points of $(1,0)$. The connected set of $(1,0)$ and the point $(1,0)$ create an n-saur with at least $n$ points. This is because there exists some path from (1,0) to every point in this set and thus every point in this set can get to any other point in this set by going through (1,0), thus creating a connected graph/partition

The rest of the points not in the connected set of $(1,0)$ form a partition because they could not have been adjacent to a point in the connected set of $(1,0)$ or else they would be in that set.

If there are less than $n$ points remaining, then we employ the greedy algorithm on the connected set of $(1,0)$. First, we choose $(1,0)$. And then we choose all points adjacent to $(1,0)$ and then all points adjacent to those adjacent points et cetera until we get another $n$-saur.
This post has been edited 1 time. Last edited by efang, Dec 29, 2016, 9:11 PM
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
#12 • 2 Y
Y by Adventure10, Mango247
Is this solution correct?
We show that $4n-2$ does not work.
Mark one random square with at most three neighbors. Consider the following process:
1. Consider the last marked square. There are at most three "new" neighbours (other than the one already considered previously), so the unmarked squares can be categorized into three different connected "routes." Since there are at most $n$ marked squares currently ($(n-1)+1$), there are $3n-2$ squares yet to be marked, so one of the routes will have at least $n$ squares. Mark all of the squares that are not in that route. Thus, after this, there are always exactly two connected pieces and the unmarked one is a dinosaur.
2. If there are at least $n$ marked squares now, we are done since the marked square figure is connected and the unmarked figure is connected and a dinosaur
3. Mark the square in the unmarked route adjacent to the square we just processed
This post has been edited 1 time. Last edited by MathPanda1, Mar 6, 2017, 5:08 PM
Reason: Fixed solution
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
#13 • 2 Y
Y by Adventure10, Mango247
Does anyone know if my solution is correct? At first, I had another solution, but found an error, so I am wondering if there is still an error that I overlooked. Thank you so much for all your help! All advice is much appreciated :)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
trumpeter
3332 posts
#14 • 1 Y
Y by Adventure10
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
rocketscience
466 posts
#15 • 3 Y
Y by guptaamitu1, Adventure10, signifance
Let $k=2007$. The answer is $4k-3$. The construction is to take a central cell and append four rods, each consisting of $k-1$ cells, to the four sides of the central cell.

Now we show that all dinosaurs with $V \ge 4k-2$ cells are not primitive. Transfer the problem to graph theory terms: form a spanning tree $T$ to represent the dinosaur, where cells are vertices and shared sides are edges. We wish to bipartition $T$ by removing an edge such that both resulting subtrees have at least $k$ vertices.

Let $v \in T$ be any vertex. Consider any neighbor $w$ of $v$, and define $S_{v, w}$ as the largest subtree containing $w$ but not $v$; we say $S_{v, w}$ is a branch emanating from $v$. We say $S_{v, w}$ is small if it has fewer than $k$ vertices, large if it has greater than $V-k$ vertices, and medium otherwise. Our goal is to find a $v$ with a neighbor $w$ such that $S_{v, w}$ is medium, since we can then take the bipartition $\{S_{v, w}, T \setminus S_{v, w}\}$.

Let us start by picking any $v \in T$. If $v$ has a medium branch, we are done, so assume otherwise. As $1 \le \deg v \le 4$, not all of $v$'s branches can be small, since that would imply that $|T| \le 4(k-1) + 1 < V$. Also note that $v$ cannot have two or more large branches; hence, $v$ has exactly one large branch. This observation is the basis for our algorithm:
  • Let $w$ be the neighbor of $v$ such that $S_{v,w}$ is large. Then, $w$ has a branch $S_{w,v}$ consisting of $v$ appended to all of $v$'s small branches, meaning $S_{w,v}$ has at least $1$ more vertex than the largest small branch of $v$. Also note that $S_{w,v}$ has at most $3(k-1) + 1 = 3k-2 \le V-k$ vertices. Thus, $S_{w,v}$ is either medium or small.
  • If $S_{w,v}$ is medium, we're done. If $S_{w,v}$ is small, forget $v$ and consider $w$ instead. Repeat these two steps with $w$ playing the role of $v$.
In this manner, we move from vertex to vertex until we find a medium branch for the first time. At every step of the way, the size of the largest small branch of our vertex in consideration increases by at least $1$, and that branch never overshoots $V-k$ vertices, so this algorithm must terminate when we find a medium branch.
This post has been edited 1 time. Last edited by rocketscience, Jan 6, 2020, 7:15 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
stroller
894 posts
#16
Y by
Hmm, how do we know each "cell" has exactly 4 edges with the current wording? :read:
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
WAit_Mng
67 posts
#17
Y by
stroller wrote:
Hmm, how do we know each "cell" has exactly 4 edges with the current wording? :read:

A cell is a unit square if I understood it correctly, so the maximum degree of the vertices is 4.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jeteagle
480 posts
#18 • 1 Y
Y by kevinmathz
Define a thing as an animal that is not a dinosaur.
Define an animal with size n if it consists of n equal-sized cells.

We will prove the broader case of when n is the size of a dinosaur, the answer is $4n-3.$

Construction: cross of tiles. very ez to prove

Proving the maximum: We will prove by contradiction. Let’s say for some $n>\ge 2$ ($n = 1$ is obvious) there is an arrangement of at least $4n-2$ cells such that it cannot be partitioned into $2$ primitive dinosaurs. Let the maximum number of cells be $m$. It is obvious that we can have at least $1$ dinosaur in these $4n-2$ cells.

Consider a dinosaur such that when removed, it creates the biggest thing. We can assume the dinosaur has size $n$ to maximize the size of the animal. If this biggest thing has size $x$ where $x < n-1$, we, then we can add cells to this thing to increase its size to $n-1$, and we would have created an animal with more than m cells. To prove this won’t make an animal that can be partitioned into two dinosaurs, if we can, then we see that this added cell must have been added to one of these dinosaurs, which means before we added it, it had a size of $n-1$, which is greater than $x$, a contradiction (we assumed $x$ to be the biggest thing that could be created). Therefore, this thing must have size $n-1.$

We now see that we are left with at least $2n-1$ cells that aren’t included in the dinosaur or this thing. We can just assume it is $2n-1$ for now since we are proving with contradiction. If we remove the dinosaur again temporarily, we see that these $2n-1$ cells are all distributed among things. If one of these things were a dinosaur, then we would have a contradiction. Therefore, if these $2n-1$ cells are distributed among $2$ things, then by the Pigeonhole Principle, we would have an animal with at least $n$ cells, making it a dinosaur.

Define a used cell as a cell that is part of the dinosaur, call it dinosaur $1$, that is adjacent to this $n-1$ sized thing.

This means we must have these $2n-1$ cells distributed among $3$ things. Now consider a used cell. If we remove this cell from the dinosaur and add it to the $n-1$ sized thing. The $n-1$ sized thing is now a dinosaur, and the dinosaur is now a thing. However, dinosaur $1$ was connected to at least $3$ things, each with size at least $1.$ This means when we remove this cell, we can also remove a cell that is part of one of these things that is adjacent to one of the dinosaur’s cells, which means this will for $2$ dinosaurs, a contradiction.

However, to prevent this, if we remove this cell from dinosaur $1,$ it could also be connected to other things too, not only the $n-1$ sized thing. This means for dinosaur $1$ to not be able to “steal” one of the things cells, the things must be connected to the dinosaur at this cell and only this cell. However, each cell only has $4$ sides. One of the sides is already connected to one of the sides of the dinosaur. Another side is also connected to the $n-1$ sized thing. Therefore, there are only $2$ sides left with at least $3$ things to be adjacent to. By the Pigeonhole Principle, one of the things will not be connected to dinosaur $1$ at this cell, a contradiction.

Therefore, we cannot have a $4n-2$ celled animal, as all of them will be able to be partitioned into $2$ dinosaurs. This means $4n-3$ is the answer.


Very messy drawing:
Attachments:
This post has been edited 1 time. Last edited by jeteagle, Nov 6, 2020, 12:02 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IAmTheHazard
5000 posts
#20 • 1 Y
Y by centslordm
Devilish for amo 1/4 but pretty cool

Replace $2007$ with $n$; the answer is $4n-3$. As a construction, consider a cross with a center cell and four "arms" each $n-1$ long. If this animal is partitioned, the partition containing the center cell has at least $3n-2$ cells, so the other partitions have length at most $n-1$. As such this animal is primitive.
Now it suffices to show that no $4n-2$-cell dinosaur is primitive. Suppose otherwise, and consider a "semi-maximal path" $P=c_1,\ldots,c_k$ along the cells of the dinosaur $D$that is, a path that cannot be made longer by "naively" adding cells to its start or end. Upon removing this path from $D$ there should remain some number (possibly zero) of connected components. For each of these components, let its "anchor" be one of its cells that is adjacent to $P$ (pick arbitrarily).
Define a sequence of animals $a_0,\ldots,a_k \subseteq D$, starting with $a_0=\emptyset$. To construct the rest, "walk" from $c_1$ to $c_k$, and upon entering a cell $c_i$ set $a_i$ equal to the union of $a_{i-1},c_i$, and whatever connected components are anchored to $c_i$. Note that $a_k=D$ and
$$0=|a_0|<|a_1|<\cdots<|a_{k-1}|<|a_k|=|D|=4n-2.$$Further, as $P$ is "semi-maximal" we actually have $|a_1|=1$ and $|a_{k-1}|=4n-3$.
Now, it is clear that for all $i$, we can partition $D$ into the two possibly empty animals $a_i$ and $D \setminus a_i$that is, both of these are connected figures. Because we can't have both of these be dinosaurs by assumption, there must exist some $2 \leq i \leq n-1$ with
$$|a_{i-1}|\leq n-1 \text{ and } |a_i|\geq (4n-2)-(n-1)=3n-1.$$Note that $i=1$ and $i=n$ fail because of their known values.
By definition, this means that the connected components anchored to $c_i$ must have total size at least $(3n-1)-(n-1)-1=2n-1$. On the other hand, there are only two possible edges to which a connected component could possibly be anchored to $c_i$, as the other two are "occupied" by $c_{i-1}$ and $c_{i+1}$. It then follows that there are at most two connected components anchored to $c_i$, and therefore one of them must contain at least $n$ cells. Let this connected component be $C$; then $D \setminus C$ is an animal, being connected "through" $P$, which also contains $3n-2\geq n$ cells, so we can partition $D$ into the dinosaurs $C$ and $D \setminus C$, contradiction. As such, $D$ cannot exist, so every $4n-2$-cell dinosaur is non-primitive. $\blacksquare$
This post has been edited 2 times. Last edited by IAmTheHazard, Feb 11, 2022, 2:27 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Number1048576
91 posts
#21
Y by
Please could someone check this as it feels too short.
solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
th1nq3r
146 posts
#22
Y by
The following lemma kills the problem. Construct the tree with a base vertex of degree $4$ and with four length $2007$ paths.

Lemma: There is some vertex $v$ so that $G - v$ does not leave behind any dinosaurs.

Proof: Assume that for every vertex $v \in V(G)$, $G - v$ leaves behind dinosaurs. Then we have that if we consider the base of this tree, then we have at most four components for which aren't dinosaurs. A contradiction. $\square$

Hence we have the four components give us $4(n - 1)$ vertices and adding back the base of the tree gives us $4(n - 1) + 1$ total vertices. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cj13609517288
1869 posts
#23
Y by
Let $n=2007$. The answer is $4n-3$, achieved by a "+" shape where there are $n-1$ cells sticking out of the middle in all four directions. We will now prove that $4n-2$ doesn't work, so assume FTSOC that there is a primitive dinosaur of size $4n-2$.

View an animal as a graph where the cells are the nodes and the edges are whether the two cells are orthogonally connected. Note that each node has degree at most $4$. Now arbitrarily remove edges until the graph is a tree. Clearly, any solution on the tree must work on the original graph.

Now consider any leaf node in the tree, say $A$. Consider the longest path starting from $A$ in the tree(if there are multiple, choose any), and say it ends at $B$, which must be a leaf node. Let this path have length $k$, and let the path be $AP_1P_2\dots P_{k-1}B$. Define $P_0=A$ and $P_k=B$. Now let $f(x)$ be the number of nodes dangling off the path not including $P_x$(the ones that would be not connected to something in the path if $P_x$ were removed from the tree and all of its edges were removed), plus one(for $P_x$), at $P_x$. Also, define
\[g(x)=f(0)+f(1)+\dots+f(x).\]
Now consider the least $m$ such that $g(m)\ge n$. If $g(m)\le 3n-2$ we already have a contradiction by deleting the edge between $P_m$ and $P_{m+1}$, so we must have $g(m)\ge 3n-1$. But $g(m-1)\le n-1$ by definition, so
\[2n=(3n-1)-(n-1)\le g(m)-g(m-1)=f(m).\]Therefore, by pigeonhole, there must be some tree dangling off of $P_m$ that has size at least $n$, contradiction.
This post has been edited 2 times. Last edited by cj13609517288, May 1, 2023, 1:23 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
thdnder
194 posts
#24
Y by
Let $n = 2007$.

The answer is $4n - 3$. The construction is same as above.

Now we'll prove that the primitive dinosaur has at most $4n - 3$ edges. Let $G$ be a our primitive dinosaur and let $v$ be a cell in $G$. Let $v_{1}, \dots, v_{k}$ be neighbors of $v$. Define a vertex $u$ is $i$-good if there exist path $v$ to $u$ passing through vertex $v_{i}$. Let $A_{i}$ be a set of $i$-good vertices. For some $i$, if $|A_{i}| \geq n$, then $A_{i}$ is dinosaur and the rest of cells form a dinosaur, a contradiction. So the number of cell in $G$ not exceeds $1 + \sum_{i=1}^{k}|A_{k}| \leq 1 + 4(n - 1) = 4n - 3$. This completes proof. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cursed_tangent1434
551 posts
#25
Y by
We solve the more general case. An animal with at least $k$ cells is known as a k-nimal. Now, we claim that the maximum number of cells in a primitive $k-$nimal is $4k-3$.

Consider a $k-$nimal with its cells in the shape of its cross with $k-1$ cells in each of the arms. This gives a total of $4k-3$ cells, and any set of $k$ cells in this configuration must pass through the center square implying that only one such set of cells exists (For any animal with less than $4k-3$ cells simply remove an adequate number of cells of the arms).

Now, look at this animal with $n$ cells as a simple connected graph $G$, where each vertex represents a cell and each edge between two vertices represents two cells being adjacent. Then, we know there exists a spanning tree $T$ of this graph. Then, we have the following (kinda) well known result.

Claim : Let $T$ be a tree and $v$ be any vertex of $T$. Let $v_1,v_2,\dots,v_m$ be the vertices adjacent to $v$. Let $T_i$ be the tree which contains $v_i$ which is obtain upon deleting the edge $vv_i$.Then, let $f(v)=\max_{i=1}^m|V(T_i)|$. Let $\Delta>1$ be the maximum degree among all vertices of $T$. Then, there exists a vertex $v$ such that
\[\frac{n-1}{\Delta} \leq f(v) \leq \frac{(\Delta -1)(n-1)}{\Delta} \]
Proof : Let $d$ be the degree of some vertex. The left inequality clearly follows from Pigeonhole Principle as,
\[f(v) \geq \frac{n-1}{d} \geq \frac{n-1}{\Delta}\]Now, to see why the right inequality must be true, consider the vertex $v$ such that $f(v)$ is minimum. Suppose $f(v) \geq \frac{(\Delta-1)(n-1)}{\Delta}+1$. Let $v_i$ be the neighbour of $v$ with $|T_i| \geq \frac{(\Delta-1)(n-1)}{\Delta}+1$. Then, clearly the tree containing $v$ after removing $v_iv$ contains at most $n - \frac{(\Delta -1)(n-1)}{\Delta}-1 = \frac{n-1}{\Delta}$. Now, if the tree $T_j$ which attains the maximum of $f(v_i)$ contains $v$, then $f(v_i) \leq \frac{n-1}{\Delta} \leq \frac{(\Delta -1)(n-1)}{\Delta}$ (with equality holding if and only if $\Delta=2$ in which case the result is obvious anyways). Thus, this violates the minimality of $f(v)$. If $T_j$ does not contain $v$ on the other, hand $f(v_i)=f(v)-1<f(v)$ again violating the minimality. Thus, our assumption must have been false and indeed, the required inequality holds.

Now, note that if the given inequality is true, the spanning tree $T$ of our graph contains two vertices $v,v_i$ such that when we delete edge $vv_i$ we have two trees such that the larger of them, has length at least $\frac{n-1}{\Delta}$ and the smaller has length at least $n-\frac{(\Delta -1)(n-1)}{\Delta} = \frac{n-1}{\Delta}$. Thus, $T$ and indeed $G$ contain two vertex-disjoint connected subgraphs containing at least $\lceil{\frac{n-1}{\Delta}}\rceil$. Thus, for all $n\geq 4k-2$, we have two vertex-disjoin connected subgraphs such that each has at least
\[\lceil{\frac{n-1}{\Delta}}\rceil \geq \lceil{\frac{4k-2-1}{4}}\rceil \geq k\]thus implying that it includes two $k-$nimals. Thus, such an animal cannot be primitive and we are done.
This post has been edited 2 times. Last edited by cursed_tangent1434, Dec 23, 2023, 12:18 PM
Reason: latex issues
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Blast_S1
352 posts
#26
Y by
Answer is $8025$, which is attained with a $+$ shape with one central square and $2006$ squares in each branch.

To show that $n \ge 8026$ is bad, we apply the spanning tree reduction stuff. Take an edge $uv$ that minimizes the difference between the number of vertices in the two components induced by its removal. If one of the components, without loss of generality say the one containing $u$, has at most $k \le 2006$ vertices, then we can find another edge incident to $v$ such that its removal from the original tree induces a component with between $k + 1$ and $n - k - 1$ edges, and blah blah blah minimality wrong done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ihatemath123
3439 posts
#28
Y by
Replacing $k$ with $2007$, the answer is $4k-3 = 8025$, obtained by gluing four $2006 \times 1$ rectangles onto the edge of a unit square.

Suppose we have an animal with $4k-2$ cells – we will partition this animal into two dinosaurs. Color one cell of the animal black, and the rest of the cells white. Each second, we find a white square adjacent to a black square, and color the white square black. If the white squares still form an animal, we continue, but our main concern is if they don't: by coloring this one square black, the white squares may be split into up to three animals. If, at the moment, $x \leq k$ squares are colored black, then $4k-2-x$ squares are colored white, so one of the two/three white animals has an area of at least
\[\left \lceil \frac{4k-2-x}{3} \right \rceil \geq \left \lceil \frac{3k-2}{3} \right \rceil = k.\]Keep this animal white, and shade everything else black. This process can be repeated until at least $k$ squares are colored black.
This post has been edited 2 times. Last edited by ihatemath123, Aug 30, 2024, 12:32 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mathandski
720 posts
#29
Y by
Subjective Rating (MOHs)
Please contact westskigamer@gmail.com if there is an error with my solution for cash bounties by 3/18/2025.

"We show that, even with these cuts forcibly made, we can still decompose the animal into dinosaurs."

Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
aidan0626
1759 posts
#30
Y by
epitomy, do I misunderstand your solution, or is this shape a counterexample to your argument?

X _ X X X
X _ X _ _
X X X X X
_ _ X _ X
X X X _ X

very interesting counterexample
This post has been edited 1 time. Last edited by aidan0626, Mar 12, 2025, 3:56 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
quantam13
97 posts
#31
Y by
The answer is $4(n-1)+1$ where we replace $2007$ by $n$.

The conclusion will in fact hold in any graph where each vertex had degree at most $4$. Consider a primitive dinosaur's graph $G$ and consider its spanning tree $T$.

Claim: There is some vertex $v\in T$ such that $T\setminus v$ leaves behind no dinosaurs
Proof of claim: This is not so hard to see, we assume that its false, consider the results of the removal of two neighbouring vertices removal and we do some casework to get a contradiction by using the acyclicity of $T$. $\square$

Now to finish with the bound, consider the vertex whose removal leaves behind no dinosaurs. In the $4$ remaining connected components, there must be atmost $n-1$ vertices, so we get that there can be atmost $4(n-1)+1$ vertices, as desired.

But the equality case is direct from the proof of bound. Just consider the case when there is a central vertex and $4$ non touching branches extending from it, each with length $n-1$. This works since each dinosaur in this graph must pass through the central vertex so there cant be 2 that partition the graph. The proof of bound also shows that all such primitive dinosaurs are of this form. End of story. $\blacksquare$
This post has been edited 1 time. Last edited by quantam13, Mar 20, 2025, 4:26 AM
Reason: line breaks
Z K Y
N Quick Reply
G
H
=
a