# Thread: Extracurricular Elementary Mathematics Marathon

1. ## Extracurricular Elementary Mathematics Marathon

Rules are as per the other marathons. Difficulty should be reasonable, and hints should be provided as deemed necessary. Use any "elementary" techniques, provided you state them, and if it's fairly advanced, outline a proof.

I'll start off simple.

$Find all integer pairs (x,y) that satisfy x^2 + 6xy + 8y^2 +3x +6y = 2$

Other things:

For the purposes of this thread, the set of all natural numbers excludes zero.

Vectors and elementary functions of any kind are allowed, but little to no calculus. (this one due to leehuan)

Define terms that the average person following this thread probably wouldn't know.

State any theorems/techniques that may help in solving the problem.

2. ## Re: Extracurricular Elementary Mathematics Marathon

Rules are as per the other marathons. Difficulty should be reasonable, and hints should be provided as deemed necessary. Use any "elementary" techniques, provided you state them, and if it's fairly advanced, outline a proof.

I'll start off simple.

$Find all integer pairs (x,y) that satisfy x^2 + 6xy + 8y^2 +3x +6y = 2$
$\noindent Note that the L.H.S. factorises into (x+2y)(x+4y+3). This can be motivated by writing the L.H.S. as x^2 + (6y+3)x+ \left(8y^2 + 6y\right), and factorising this quadratic in x. We want to write it as (x+\alpha)(x+\beta), where \alpha \beta = 8y^2 + 6y and \alpha + \beta = 6y+3. It is easy to see that we take \alpha = 2y,\beta = 4y+3.$

$\noindent So we have (x+2y)(x+4y+3)=2. Since x,y\in \mathbb{Z}, each bracketed term is an integer, so based on the factors of 2 being 2 and 1, we have the following four possibilities:$

$\noindent 1) x+2y=2 and x+4y+3 = 1$

$\noindent 2) x+2y=-2 and x+4y+3 = -1$

$\noindent 3) x+2y=1 and x+4y+3 = 2$

$\noindent 4) x+2y=-1 and x+4y+3 = -2.$

$\noindent In general, if(f) x+2y=a, then x=a-2y, so x+4y+3 =b\Longleftrightarrow a-2y+4y+3 = b \Longleftrightarrow 2y = b-a -3 \Longleftrightarrow y=\frac{b-a-3}{2}. This implies that y will be integral iff b-a is odd. This is the case in all the possibilities 1) to 4). So in 1), we have y=\frac{1-2-3}{2}=\frac{-4}{2}=-2, and x=2-2\times (-2) = 6.$

$\noindent In 2), we have y=\frac{-1-(-2)-3}{2}=\frac{-2}{2}=-1, so x=-2-2\times (-1) = 0.$

$\noindent In 3), we again have y=\frac{2-1-3}{2}=\frac{-2}{2}=-1, so x=-2-2\times (-1) = 0.$

$\noindent In 4), we again have y=\frac{-2-(-1)-3}{2}=\frac{-4}{2}=-2, so x=-2-2\times (-2) = 6.$

$\noindent So the solutions (x,y) are (6,-2) and (0,-1).$

3. ## Re: Extracurricular Elementary Mathematics Marathon

$\textbf{NEW QUESTION}$

$\noindent Let a and b be real numbers with a>1 and b\neq 0. Suppose that \frac{a}{b}=a^{3b} and ab=a^{b}. Find b^{-a}.$

4. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by InteGrand
$\textbf{NEW QUESTION}$

$\noindent Let a and b be real numbers with a>1 and b\neq 0. Suppose that \frac{a}{b}=a^{3b} and ab=a^{b}. Find b^{-a}.$
16

5. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by GoldyOrNugget
16
Correct!

6. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by InteGrand
$\textbf{NEW QUESTION}$

$\noindent Let a and b be real numbers with a>1 and b\neq 0. Suppose that \frac{a}{b}=a^{3b} and ab=a^{b}. Find b^{-a}.$
The answer, has already been posted, but here, we will prove uniqueness.

$\noindent \frac{a}{b} = (a^b)^3 = (ab)^3 = a^3b^3 \Leftrightarrow b^4 a^2 =1 \Leftrightarrow b^2 a = \pm 1 \\But a is a log-positive number, and b is the result of a real-valued exponentiation, so b is strictly non-negative, in the interval (0,1). Hence, the only true relation is b\sqrt{a} =1. By substitution of b, we have b^{-a} = a^{\frac{a}{2}}. Lastly, observe that the function y = x^{\frac{x}{2}} is injective on the interval (1,\infty). This is sufficient to prove the uniqueness of b^{-a}. \blacksquare$

7. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent Let p be an odd prime, a be coprime to p, and n be the smallest integer such that \\a^n \equiv 1 mod p \\ Show n|(p-1)$

Hint: Use Fermat's Little Theorem.

8. ## Re: Extracurricular Elementary Mathematics Marathon

The answer, has already been posted, but here, we will prove uniqueness.

$\noindent \frac{a}{b} = (a^b)^3 = (ab)^3 = a^3b^3 \Leftrightarrow b^4 a^2 =1 \Leftrightarrow b^2 a = \pm 1 \\But a is a log-positive number, and b is the result of a real-valued exponentiation, so b is strictly non-negative, in the interval (0,1). Hence, the only true relation is b\sqrt{a} =1. By substitution of b, we have b^{-a} = a^{\frac{a}{2}}. Lastly, observe that the function y = x^{\frac{x}{2}} is injective on the interval (1,\infty). This is sufficient to prove the uniqueness of b^{-a}. \blacksquare$
$\noindent It is probably easier to prove uniqueness (and get the actual answer) by just solving the given pair of simultaneous equations (fairly easy, just start by taking the log base a of both sides of each equation \ddot{\smile}.).$

9. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by InteGrand
$\noindent It is probably easier to prove uniqueness (and get the actual answer) by just solving the given pair of simultaneous equations (fairly easy, just start by taking the log base a of both sides of each equation \ddot{\smile}.).$
That doesn't prove uniqueness of b, it just restricts the value range of b to the solution interval without proof...

10. ## Re: Extracurricular Elementary Mathematics Marathon

Isn't this just the Advanced X2 Marathon ?

11. ## Re: Extracurricular Elementary Mathematics Marathon

That doesn't prove uniqueness of b, it just restricts the value range of b to the solution interval without proof...
$\noindent What do you mean? You find the actual value of b by solving the equations using reversible steps (since there turns out to be exactly one solution, b is unique). Taking logs of negative numbers though would be non-elementary so you'd maybe want to justify that b is positive first. This is easily done by looking at the given equation ab = a^b for example. The R.H.S. is positive, so ab must be positive, so b is positive as a is given to be positive.$

12. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by Drsoccerball
Isn't this just the Advanced X2 Marathon ?
No, it is unrestricted from the arbitrary bounds placed on it. I can't just post any Olympiad problem on there, but I can do so here.

13. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by Drsoccerball
Isn't this just the Advanced X2 Marathon ?
If this were my thread I would allow hyperbolic functions and elementary vector notation now, however probably a bit of guidance as to how they work as we haven't attended a lecture yet.

14. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by leehuan
If this were my thread I would allow hyperbolic functions and elementary vector notation now, however probably a bit of guidance as to how they work as we haven't attended a lecture yet.
Olympiad allows for that, but I've never seen it in good use. Except for vectors, those things are really useful for a good bunch of problems.

15. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent Let p be an odd prime, a be coprime to p, and n be the smallest integer such that \\a^n \equiv 1 mod p \\ Show n|(p-1)$

Hint: Use Fermat's Little Theorem.
p-1 = mn + r for non-negative integers m, r with r < n.

Then (a^r)(a^n)^m=a^(p-1)
=> a^r=1 (using FLT)

From the minimality of n, we must conclude r=0.

That is n|p-1.

16. ## Re: Extracurricular Elementary Mathematics Marathon

Solve the equation x^2+y^2+1=xyz over the positive integers.

Hint: First concentrate on determining what possibilities there are for z.

17. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by seanieg89
Solve the equation x^2+y^2=xyz over the positive integers.

Hint: First concentrate on determining what possibilities there are for z.
$\noindent Divide down xy without worry, as they are positive. Let q = \frac{x}{y} be a rational number. We now obtain a quadratic in terms of q,\; q^2 - qz +1 = 0. By the quadratic formula, the discriminant must be a perfect square for q to be rational. z^2 -4 = k^2 for some integer k. But the only valid integer solution for z is 2, which means the only possible value of z for our initial equation is 2. Finally, we have x^2 + y^2 = 2xy. But by the AM-GM inequality, this only happens if x=y. So (r,r,2) is the only solution for any positive integer r.$

18. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent Show that there must exist a non-empty subset in a set of n integers such that their sum is divisible by n.$

19. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent Show that there must exist a non-empty subset in a set of n integers such that their sum is divisible by n.$
Trivial for n=1.

Suppose the property holds for 1..n-1.

For general n, if their sum is divisible by n, then their sum mod n is 0. Take all elements mod n. If all elements mod n are 0, pick any subset. Otherwise, pick out an element x mod N which is nonzero mod n. 0 <= x < n. Of the remaining elements, take any n-x > 0 elements. These n-x elements have a subset divisible by n-x, so if we then add x to the subset, we have a subset with sum (n-x) + x = 0 mod N, so the subset is divisible by n.

20. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent Divide down xy without worry, as they are positive. Let q = \frac{x}{y} be a rational number. We now obtain a quadratic in terms of q,\; q^2 - qz +1 = 0. By the quadratic formula, the discriminant must be a perfect square for q to be rational. z^2 -4 = k^2 for some integer k. But the only valid integer solution for z is 2, which means the only possible value of z for our initial equation is 2. Finally, we have x^2 + y^2 = 2xy. But by the AM-GM inequality, this only happens if x=y. So (r,r,2) is the only solution for any positive integer r.$
Nice . I actually forgot a term on the LHS from the diophantine equation I was trying to remember though lol, try the edited problem too.

It is slightly harder, but not greatly so. The original hint still stands.

Repost for visibility:

Solve the equation:

$x^2+y^2+1=xyz$

over the positive integers.

Hint: Try to determine what z can be first.

21. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by seanieg89
Nice . I actually forgot a term on the LHS from the diophantine equation I was trying to remember though lol, try the edited problem too.

It is slightly harder, but not greatly so. The original hint still stands.

Repost for visibility:

Solve the equation:

$x^2+y^2+1=xyz$

over the positive integers.

Hint: Try to determine what z can be first.
$\noindent Part 1: Restricting z \\ Suppose (x,x,z) satisfies the equation with z \neq 3. This is impossible, since 2x^2 +1 = zx^2 \Leftrightarrow x^2 (z-2) = 1, which contradicts z\neq 3 So if z \neq 3 then x \neq y. The original equation can be re-arranged to yield (yz -x)^2 +y^2 +1 = (yz -x)yz. So If (x,y,z) is a solution, then (yz -x, y,z) is also a solution to the equation. This is valid, since x(yz -x) = xyz -x^2 = y^2 +1 > 0, which forces yz-x > 0. WLOG, let x>y, so x^2 > y^2 +1 > x(yz-x), which shows x>yz-x. This means that the new solution is smaller than our initial solution. But since x\neq y, this construction of ever smaller solutions can be done indefinitely, so we have an infinite sequence of decreasing positive integers, which is impossible. By Fermat's method of infinite descent, there can be no integer solutions if z \neq 3.$

$\noindent Part 2: Constructing solutions \\ By inspection, (1,1) is a solution to x^2 + y^2 + 1 = 3xy. Let (a,b) be a different solution. WLOG, suppose a>b. Exactly like above, rearranging the equation gives us b^2 + (3b-a)^2 + 1 = 3b(3b-a), which gives us a new solution, (b,3b-a). As b\neq 1, we have b^2 -1 > 0, and from the equation, b^2 -1 = a^2 - 3ab + 2b^2 = (a-b)(a-2b)>0, which shows a>2b \Leftrightarrow 3b-a b. It follows that all our infinite solutions can be obtained by applying this recurrence arbitrarily many times.$

$\noindent Following this, the solutions are, (1,1), (2,1), (5,2), (13,5), (34,13), (89,34), \cdots and by symmetry, (1,1), (1,2), (2,5), (5,13), (13,34), (34,89), \cdots . The recurrence relation that generates these solutions define the odd-indexed Fibonacci numbers with those exact initial numbers, so the general solutions to the equation are (1,1),(F_{2n-1},F_{2n+1}),(F_{2n+1},F_{2n-1}) \; \; \forall n \in \mathbb{N}$

22. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent Part 1: Restricting z \\ Suppose (x,x,z) satisfies the equation with z \neq 3. This is impossible, since 2x^2 +1 = zx^2 \Leftrightarrow x^2 (z-2) = 1, which contradicts z\neq 3 So if z \neq 3 then x \neq y. The original equation can be re-arranged to yield (yz -x)^2 +y^2 +1 = (yz -x)yz. So If (x,y,z) is a solution, then (yz -x, y,z) is also a solution to the equation. This is valid, since x(yz -x) = xyz -x^2 = y^2 +1 > 0, which forces yz-x > 0. WLOG, let x>y, so x^2 > y^2 +1 > x(yz-x), which shows x>yz-x. This means that the new solution is smaller than our initial solution. But since x\neq y, this construction of ever smaller solutions can be done indefinitely, so we have an infinite sequence of decreasing positive integers, which is impossible. By Fermat's method of infinite descent, there can be no integer solutions if z \neq 3.$

$\noindent Part 2: Constructing solutions \\ By inspection, (1,1) is a solution to x^2 + y^2 + 1 = 3xy. Let (a,b) be a different solution. WLOG, suppose a>b. Exactly like above, rearranging the equation gives us b^2 + (3b-a)^2 + 1 = 3b(3b-a), which gives us a new solution, (b,3b-a). As b\neq 1, we have b^2 -1 > 0, and from the equation, b^2 -1 = a^2 - 3ab + 2b^2 = (a-b)(a-2b)>0, which shows a>2b \Leftrightarrow 3b-a b. It follows that all our infinite solutions can be obtained by applying this recurrence arbitrarily many times.$

$\noindent Following this, the solutions are, (1,1), (2,1), (5,2), (13,5), (34,13), (89,34), \cdots and by symmetry, (1,1), (1,2), (2,5), (5,13), (13,34), (34,89), \cdots . The recurrence relation that generates these solutions define the odd-indexed Fibonacci numbers with those exact initial numbers, so the general solutions to the equation are (1,1),(F_{2n-1},F_{2n+1}),(F_{2n+1},F_{2n-1}) \; \; \forall n \in \mathbb{N}$
Well done .

23. ## Re: Extracurricular Elementary Mathematics Marathon

Originally Posted by GoldyOrNugget
Trivial for n=1.

Suppose the property holds for 1..n-1.

For general n, if their sum is divisible by n, then their sum mod n is 0. Take all elements mod n. If all elements mod n are 0, pick any subset. Otherwise, pick out an element x mod N which is nonzero mod n. 0 <= x < n. Of the remaining elements, take any n-x > 0 elements. These n-x elements have a subset divisible by n-x, so if we then add x to the subset, we have a subset with sum (n-x) + x = 0 mod N, so the subset is divisible by n.
I don't think this is quite right? Just because the sum of a subset is divisible by n-x, it doesn't necessarily mean that the sum is n-x mod N? Or have I misinterpreted what you're saying?

Here's what I had. Suppose that a_i are the elements of the set. Now, consider the sums b_i=a_1+a_2+....+a_i. If one of b_1,b_2.. b_n is 0 mod n, that set has sum divisible by n. If not, then by the pigeon hole principle, two of these are of the same class mod n. Suppose that these two are b_m and b_n, (n>m). Then, b_n-b_m has 0 mod n.

$\noindent Show that in any arbitrarily long sub-interval of the natural numbers, there exists a sub-interval containing no prime numbers.\\Hence, show that in any sub-interval of n elements, there will always be a sub-interval containing k prime numbers for all \pi(n) > k > 0, where \pi(n) is the prime counting function, which denotes the number of primes less than or equal to n.$

$\noindent Discrete Intermediate Value Theorem: \\ For all \{a,b\} \in \mathbb{Z}, \; a
I think we need a bit of clarification here, \pi (3)= 2, but we can definitely have subintervals of length 3 which contain no prime numbers. For instance 20,21,22 is such an interval, and none of the three are prime numbers.

24. ## Re: Extracurricular Elementary Mathematics Marathon

Yes, there can be sub-intervals of length "n" with no prime numbers. however, you must prove this for all n.

And the second part is less straightforward, but still doable. The upper bound is always pi(n), because that is the maximum number of prime numbers in any sub-interval of the natural numbers of length n
?

In my previous post, I was addressing the second part of your question, not the first (I suppose I should've mentioned this). Basically, in your question you claim that if we have a subinterval of length n (has n elements), then there must exist a subinterval containing k primes for all k which exceeds 0 but is bounded by pi(x). In my previous post, I provided a counter example to this claim, showing how there exists a subinterval of length 3, but within the subinterval which I specifically mentioned (20,21,22) there is no subinterval which contains any primes. According to your question, within the subinterval (20,21,22), there should exist a subinterval which contains 1 prime and also another subinterval which contains 2 primes. Obviously, that's not true in this example.

Also, the first part of your question doesn't quite make sense either. For instance, the elements 2 and 3 form a subinterval of length 2, and clearly any subinterval within this subinterval must contain a prime. Thus your claim is false.

So this is why I'm asking for a clarification, as the question in its current wording isn't true.

25. ## Re: Extracurricular Elementary Mathematics Marathon

$\noindent Show that there exist arbitrarily long sub-intervals of the natural numbers that contain no primes.\\Hence, show that amongst the natural numbers, there will always be a sub-interval of length n containing k prime numbers for all \pi(n) \geq k \geq 0, where \pi(n) is the prime counting function, which denotes the number of primes in the interval (1,n).$

$\noindent Discrete Intermediate Value Theorem: \\ For all \{a,b\} \in \mathbb{Z}, \; azz

Page 1 of 4 123 ... Last

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•