Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "SANSKAR'S OG PROBLEMS"

(→‎Solution 1 by ddk001 (Casework))
m
 
(35 intermediate revisions by 3 users not shown)
Line 1: Line 1:
−
Hi, this page is created by ...~ SANSGANKRSNGUPTA This page contains exclusive problems made by me myself. I am the creator of these OG problems. What OG stands for is a secret! Please post your solutions with your name.
+
Hi, this page is created by ...~ SANSGANKRSNGUPTA This page contains exclusive problems made by me myself. I am the creator of these OG problems. What OG stands for is a secret! Please post your solutions with your name. I will release the Official solutions(can be one or more) by me after the problem has been solved.
 
If you view this page please increment the below number by one:   
 
If you view this page please increment the below number by one:   
−
       <math>02</math>
+
       <math>03</math>
  
 
==Problem 1==
 
==Problem 1==
 
Let <math>\overline{ab}</math> be a 2-digit [[positive integer]] satisfying <math>\overline{ab}^2=a! +b!</math>. Find <math>a+b</math> .
 
Let <math>\overline{ab}</math> be a 2-digit [[positive integer]] satisfying <math>\overline{ab}^2=a! +b!</math>. Find <math>a+b</math> .
−
==Solution 1 by ddk001 (Casework)==
+
 
 +
==Solution 1 (Tedious Casework)==
 
'''Case 1: <math>a>b</math>'''
 
'''Case 1: <math>a>b</math>'''
  
Line 58: Line 59:
 
To simplify future calculations, note that
 
To simplify future calculations, note that
  
−
<cmath>a!=\overline{ab}^2-b!=(10a+1)^2-1=100a^2+20a=10a(a+2)</cmath>.  
+
<cmath>a!=\overline{ab}^2-b!=(10a+1)^2-1=100a^2+20a=10a(10a+2)</cmath>.  
  
 
For <math>a=5</math>, this does not hold.
 
For <math>a=5</math>, this does not hold.
Line 64: Line 65:
 
For <math>a=6</math>, this does not hold.
 
For <math>a=6</math>, this does not hold.
  
−
For <math>a=7</math>, this does not hold.
+
For <math>a=7</math>, this does hold. Hence, <math>(a,b)=(7,1)</math> is a solution.  
  
 
For <math>a=8</math>, this does not hold.
 
For <math>a=8</math>, this does not hold.
Line 72: Line 73:
 
Hence, there is no positive integers <math>a</math> and <math>b</math> between <math>1</math> and <math>9</math> inclusive such that <math>a!+b!=\overline{ab}^2</math>.
 
Hence, there is no positive integers <math>a</math> and <math>b</math> between <math>1</math> and <math>9</math> inclusive such that <math>a!+b!=\overline{ab}^2</math>.
  
−
'''Case 2:<math>a=b</math>'''
+
'''Case 2: <math>a=b</math>'''
 +
 
 +
For this case, we must have
 +
 
 +
<cmath>(11a)^2=\overline{ab}^2=a!+b!=2a! \implies 11|a!</cmath>
 +
 
 +
which is impossible if a is a integer and <math>1 \le a \le 9</math>.
 +
 
 +
'''Case 3: <math>a<b</math>'''
 +
 
 +
In this case, we have
 +
 
 +
<cmath>\overline{ab}^2=a! +b!=(1+b \cdot (b-1) \cdot \dots \cdot (a+1)) \cdot a! \implies a!|\overline{ab}^2=(10a+b)^2</cmath>.
 +
 
 +
If <math>a \ge 5</math>, we must have
 +
 
 +
<cmath>10|a!|\overline{ab}^2=(10a+b)^2 \implies 10|(10a+b)^2=100a^2+20ab+b^2 \implies 10|b \implies b=0 \implies 10|a!+b!</cmath>
 +
 
 +
which is impossible since <math>10|a!</math> and <math>b!=1</math>.
 +
 
 +
Hence, <math>a \le 4</math>.
 +
 
 +
'''Subcase 3.1: <math>b>a=1</math>'''
 +
 
 +
<cmath>(10+b)^2=1+b!</cmath>
 +
 
 +
Testing cases, we can see that there is no such <math>b</math>.
 +
 
 +
'''Subcase 3.2: <math>b>a=2</math>'''
 +
 
 +
<cmath>(20+b)^2=2+b!</cmath>
 +
 
 +
Testing cases, we can see that there is no such <math>b</math>.
 +
 
 +
'''Subcase 3.3: <math>b>a=3</math>'''
 +
 
 +
<cmath>(30+b)^2=3+b!</cmath>
 +
 
 +
Testing cases, we can see that there is no such <math>b</math>.
 +
 
 +
'''Subcase 3.4: <math>b>a=4</math>'''
 +
 
 +
<cmath>(40+b)^2=4+b!</cmath>
 +
 
 +
Testing cases, we can see that there is no such <math>b</math>.
 +
 
 +
We see that <math>(a,b)=(7,1) \implies a+b=\boxed{008}</math>. <math>\blacksquare</math> ~[[Ddk001]]
 +
 
 +
==Solution 2 (Official)==
 +
 
 +
<math>\overline{ab}^2=a! +b!</math>
 +
cleary square of a positive double-digit integer is either 3-digit or 4-digit as it ranges between <math>100(10^{2})</math> and <math>9801(99^{2})</math>.
 +
 
 +
This means both <math>a</math> and <math>b</math> are less than or equal to 7 as any <math>factorial</math> greater than 7! exceeds 9999.
 +
 
 +
Now at least one of <math>a</math> or <math>b</math> must be greater than or equal to 5 or else the maximum possible value of LHS is 4!+4!=48<100
 +
also, both <math>a</math> and <math>b</math> can't be greater than or equal to 5 as if they were so. The unit digit of LHS would be zero but the unit digit of RHS would be either 5,6 or 9.
 +
 
 +
Hence, one of <math>a</math> and <math>b</math> is greater than or equal to 5 and the other is less than 5. this means the unit digit of RHS is the unit digit of a factorial which is less than 5.
 +
 
 +
Hence unit digit of RHS is 0,1,2, 6 or 4. 0,2,4 and 6 are rejected as follows:-
 +
 
 +
'''1'''. 2 can't be the unit digit of a perfect square.
 +
 
 +
'''2'''. If 6 is the unit digit of OF LHS this means one of the numbers is 3( as only 3! has the unit digit 6) and also this would mean that <math>b</math> is either 4 or 6. This directly means that 36 and 34 are the only cases to be tested. 34 can't be as both the digits are less than 5 and 36 clearly doesn't satisfy
 +
 
 +
'''3'''. If 0 is the unit digit of LHS then 50 60 70 are the only cases (as one of the digits is greater than or equal to 5) that don't satisfy
 +
 
 +
'''4'''. If 4 is the unit digit of LHS this means one of the numbers is 4( as only 4! has the unit digit 4) and also this would mean that <math>b</math> is either 2 or 8. This directly means that 42 and 48 are the only cases to be tested. 42 can't be as both the digits are  less than 5 and 48 can't also as one of the digits is 8
 +
 
 +
Hence, the unit digit of LHS must be 1 for which <math>b</math>=1 or 9(rejected). This means 51 61 and 71 are the only cases to be tried now
 +
which is really very easy to calculate and get 71 as the only possible solution to the problem and
 +
 
 +
thus, our answer is 7+1=<math>\boxed{008}</math>.~ SANSGANKRSNGUPTA
 +
 
 +
==Solution 3 (Official and Fastest)==
 +
 
 +
<math>\overline{ab}^2=a! +b!</math>
 +
cleary square of a positive double-digit integer is either 3-digit or 4-digit as it ranges between <math>100(10^{2})</math> and <math>9801(99^{2})</math>.
 +
 
 +
This means both <math>a</math> and <math>b</math> are less than or equal to 7 as any <math>factorial</math> greater than 7! exceeds 9999.
 +
 
 +
Now at least one of <math>a</math> or <math>b</math> must be greater than or equal to 5 or else the maximum possible value of LHS is 4!+4!=48<100
 +
also, both <math>a</math> and <math>b</math> can't be greater than or equal to 5 as if they were so. The unit digit of LHS would be zero but the unit digit of RHS would be either 5,6 or 9.
 +
 
 +
Hence, one of <math>a</math> and <math>b</math> is greater than or equal to 5 and the other is less than 5. Also, RHS is a perfect square, so it must be 0 or 1 <math>(mod 4)</math>
 +
 
 +
Hence the number less than 5 can be either 0, 1, or 4 because 2! and 3! are 2 <math>(mod 4)</math>
 +
If it is 0, then the unit digit of RHS is 1 meaning <math>b</math> is 1 or 9 both of which aren't possible as 9>7 and the number less than 5 is 0, not 1.
 +
 
 +
If it is 4, then the unit digit of RHS is 4 meaning <math>b</math> is either 2 or 8 both of which aren't possible as 8>7 and the number less than 5 is 4 not 2.
 +
 
 +
If it is 1 then the unit digit of RHS is 1 implying <math>b</math> is either 9(rejected 9>7) or 1. This means <math>b</math> is 1,
 +
this means 51 61 and 71 are the only cases to be tried
 +
 
 +
which is very easy to calculate and get 71 as the only possible solution to the problem and
 +
 
 +
thus, our answer is 7+1=<math>\boxed{008}</math>.~ SANSGANKRSNGUPTA
 +
 
 +
==Problem 2==
  
−
==Problem2 ==
 
 
For any [[positive integer]] <math>n</math>, <math>n</math>>1 can <math>n!</math> be a [[perfect square]]? If yes, give one such <math>n</math>. If no, then prove it.
 
For any [[positive integer]] <math>n</math>, <math>n</math>>1 can <math>n!</math> be a [[perfect square]]? If yes, give one such <math>n</math>. If no, then prove it.
 +
 +
==Problem 3==
 +
 +
Let <math>N</math> be a [[positive integer]] in <math>base</math> 10 such that the last 3 digits of any positive integral power of <math>N</math> are the same.
 +
 +
Find the sum of all possible values of the last 3 digits of <math>N</math>.
 +
 +
==Problem 4==
 +
Find all [[natural numbers]] such that their square is the sum of the factorials of their digits. (Advanced version of Problem 1)
 +
==Problem 5==
 +
Define the following [[function]] on <math>\mathbb{Z}</math>: <cmath>f(n)=\begin{cases} n+1 & 2\nmid n, \\ \frac{n}{2} & 2\mid n.\end{cases}</cmath>.
 +
 +
Sanskar says that, for any [[positive integer]] <math>n</math>, the sequence <math>\{n,f(n),f(f(n)),f(f(f(n))),\ldots\}</math>  is eventually in constant loop(i.e. after a term all the next terms in the sequence are repeating in a certain period ) Is Sanskar right? Justify your answer with proof.
 +
 +
==Solution1( Using strong induction and Fastest)==
 +
For any positive integer <math>n</math>, the second or third number in the sequence will always be less than <math>n</math>.
 +
Let us assume that every positive integer in <math>[1,k]</math> will reach <math>1</math> in its sequence.
 +
The number <math>k+1</math> will reach a number less than it , that is some positive integer in <math>[1,k]</math> and every positive integer in <math>[1,k]</math> will reach <math>1</math>. Therefore, <math>k+1</math> will also reach <math>1</math>.
 +
This is true for <math>k=2</math>, therefore for k=3,...
 +
If <math>k=1</math>, the sequence has already reached <math>1</math>.
 +
Therefore all positive integers <math>n</math> will reach <math>1</math>.
 +
After reaching <math>1</math> , the next number will be <math>f(1)=2</math> and the next <math>=f(2)=1</math>
 +
Therefore the sequence will finally be <math>1,2,1,2,...</math>
 +
Therefore Sanskar is right. ~ mathenthusiast73
 +
 +
==Problem 6==
 +
Find all [[integers]] <math>x</math> such that <math>{x}^{11}</math>+<math>{x}^{10}</math>+1 is a [[prime]].
 +
==Problem 7==
 +
Consider a grid(<math>n \times n</math>) of evenly spaced points for <math>n\geq 3</math>. Let  <math>f(n)</math>  denote the maximum number <math>r</math> such that the <math>r</math> points can be colored in such a way that no 4 of them are concyclic. (i.e no 4 of the points lie on a circle).\\
 +
Find <math>f(3)+f(4)+\dots+f(11)</math>.

Latest revision as of 11:04, 27 June 2024

Hi, this page is created by ...~ SANSGANKRSNGUPTA This page contains exclusive problems made by me myself. I am the creator of these OG problems. What OG stands for is a secret! Please post your solutions with your name. I will release the Official solutions(can be one or more) by me after the problem has been solved. If you view this page please increment the below number by one: 

      $03$

Problem 1

Let $\overline{ab}$ be a 2-digit positive integer satisfying $\overline{ab}^2=a! +b!$. Find $a+b$ .

Solution 1 (Tedious Casework)

Case 1: $a>b$

In this case, we have

\[\overline{ab}^2=a! +b!=(1+a \cdot (a-1) \cdot \dots \cdot (b+1)) \cdot b! \implies b!|\overline{ab}^2=(10a+b)^2\].

If $b \ge 5$, we must have

\[10|b!|\overline{ab}^2=(10a+b)^2 \implies 10|(10a+b)^2=100a^2+20ab+b^2 \implies 10|b \implies b=0\]

, but this contradicts the original assumption of $b \ge 5$, so hence we must have $b \le 4$.

With this in mind, we consider the unit digit of $\overline{ab}^2$.

Subcase 1.1: $a>b=1$

In this case, we have that

\[a! \equiv \overline{ab}^2-b! \equiv (10a+1)^2-1 \equiv 0 \pmod{10} \implies 10|a! \implies a \ge 5\].

There is no apparent contradiction here, so we leave this as it is.

Subcase 1.2: $a>b=2$

In this case, we have that

\[a! \equiv \overline{ab}^2-b! \equiv (10a+2)^2-2 \equiv 2 \pmod{10} \implies a! \equiv 2 \pmod{10} \implies a=2\].

This contradicts with the fact that $a>b$, so this is impossible.

Subcase 1.3: $a>b=3$

In this case, we have that

\[a! \equiv \overline{ab}^2-b! \equiv (10a+3)^2-6 \equiv 3 \pmod{10}\].

However, this is impossible for all $a$.

Subcase 1.4: $a>b=4$

In this case, we have that

\[a! \equiv \overline{ab}^2-b! \equiv (10a+4)^2-24 \equiv 2 \pmod{10}\].

Again, this yields $a=2$, which, again, contradicts $a>b$. $\square$

Hence, we must have $b=1$.

Now, with $b$ determined by modular arithmetic, we actually plug in the values.

To simplify future calculations, note that

\[a!=\overline{ab}^2-b!=(10a+1)^2-1=100a^2+20a=10a(10a+2)\].

For $a=5$, this does not hold.

For $a=6$, this does not hold.

For $a=7$, this does hold. Hence, $(a,b)=(7,1)$ is a solution.

For $a=8$, this does not hold.

For $a=9$, this does not hold.

Hence, there is no positive integers $a$ and $b$ between $1$ and $9$ inclusive such that $a!+b!=\overline{ab}^2$.

Case 2: $a=b$

For this case, we must have

\[(11a)^2=\overline{ab}^2=a!+b!=2a! \implies 11|a!\]

which is impossible if a is a integer and $1 \le a \le 9$.

Case 3: $a<b$

In this case, we have

\[\overline{ab}^2=a! +b!=(1+b \cdot (b-1) \cdot \dots \cdot (a+1)) \cdot a! \implies a!|\overline{ab}^2=(10a+b)^2\].

If $a \ge 5$, we must have

\[10|a!|\overline{ab}^2=(10a+b)^2 \implies 10|(10a+b)^2=100a^2+20ab+b^2 \implies 10|b \implies b=0 \implies 10|a!+b!\]

which is impossible since $10|a!$ and $b!=1$.

Hence, $a \le 4$.

Subcase 3.1: $b>a=1$

\[(10+b)^2=1+b!\]

Testing cases, we can see that there is no such $b$.

Subcase 3.2: $b>a=2$

\[(20+b)^2=2+b!\]

Testing cases, we can see that there is no such $b$.

Subcase 3.3: $b>a=3$

\[(30+b)^2=3+b!\]

Testing cases, we can see that there is no such $b$.

Subcase 3.4: $b>a=4$

\[(40+b)^2=4+b!\]

Testing cases, we can see that there is no such $b$.

We see that $(a,b)=(7,1) \implies a+b=\boxed{008}$. $\blacksquare$ ~Ddk001

Solution 2 (Official)

$\overline{ab}^2=a! +b!$ cleary square of a positive double-digit integer is either 3-digit or 4-digit as it ranges between $100(10^{2})$ and $9801(99^{2})$.

This means both $a$ and $b$ are less than or equal to 7 as any $factorial$ greater than 7! exceeds 9999.

Now at least one of $a$ or $b$ must be greater than or equal to 5 or else the maximum possible value of LHS is 4!+4!=48<100 also, both $a$ and $b$ can't be greater than or equal to 5 as if they were so. The unit digit of LHS would be zero but the unit digit of RHS would be either 5,6 or 9.

Hence, one of $a$ and $b$ is greater than or equal to 5 and the other is less than 5. this means the unit digit of RHS is the unit digit of a factorial which is less than 5.

Hence unit digit of RHS is 0,1,2, 6 or 4. 0,2,4 and 6 are rejected as follows:-

1. 2 can't be the unit digit of a perfect square.

2. If 6 is the unit digit of OF LHS this means one of the numbers is 3( as only 3! has the unit digit 6) and also this would mean that $b$ is either 4 or 6. This directly means that 36 and 34 are the only cases to be tested. 34 can't be as both the digits are less than 5 and 36 clearly doesn't satisfy

3. If 0 is the unit digit of LHS then 50 60 70 are the only cases (as one of the digits is greater than or equal to 5) that don't satisfy

4. If 4 is the unit digit of LHS this means one of the numbers is 4( as only 4! has the unit digit 4) and also this would mean that $b$ is either 2 or 8. This directly means that 42 and 48 are the only cases to be tested. 42 can't be as both the digits are less than 5 and 48 can't also as one of the digits is 8

Hence, the unit digit of LHS must be 1 for which $b$=1 or 9(rejected). This means 51 61 and 71 are the only cases to be tried now which is really very easy to calculate and get 71 as the only possible solution to the problem and

thus, our answer is 7+1=$\boxed{008}$.~ SANSGANKRSNGUPTA

Solution 3 (Official and Fastest)

$\overline{ab}^2=a! +b!$ cleary square of a positive double-digit integer is either 3-digit or 4-digit as it ranges between $100(10^{2})$ and $9801(99^{2})$.

This means both $a$ and $b$ are less than or equal to 7 as any $factorial$ greater than 7! exceeds 9999.

Now at least one of $a$ or $b$ must be greater than or equal to 5 or else the maximum possible value of LHS is 4!+4!=48<100 also, both $a$ and $b$ can't be greater than or equal to 5 as if they were so. The unit digit of LHS would be zero but the unit digit of RHS would be either 5,6 or 9.

Hence, one of $a$ and $b$ is greater than or equal to 5 and the other is less than 5. Also, RHS is a perfect square, so it must be 0 or 1 $(mod 4)$

Hence the number less than 5 can be either 0, 1, or 4 because 2! and 3! are 2 $(mod 4)$ If it is 0, then the unit digit of RHS is 1 meaning $b$ is 1 or 9 both of which aren't possible as 9>7 and the number less than 5 is 0, not 1.

If it is 4, then the unit digit of RHS is 4 meaning $b$ is either 2 or 8 both of which aren't possible as 8>7 and the number less than 5 is 4 not 2.

If it is 1 then the unit digit of RHS is 1 implying $b$ is either 9(rejected 9>7) or 1. This means $b$ is 1, this means 51 61 and 71 are the only cases to be tried

which is very easy to calculate and get 71 as the only possible solution to the problem and

thus, our answer is 7+1=$\boxed{008}$.~ SANSGANKRSNGUPTA

Problem 2

For any positive integer $n$, $n$>1 can $n!$ be a perfect square? If yes, give one such $n$. If no, then prove it.

Problem 3

Let $N$ be a positive integer in $base$ 10 such that the last 3 digits of any positive integral power of $N$ are the same.

Find the sum of all possible values of the last 3 digits of $N$.

Problem 4

Find all natural numbers such that their square is the sum of the factorials of their digits. (Advanced version of Problem 1)

Problem 5

Define the following function on $\mathbb{Z}$: \[f(n)=\begin{cases} n+1 & 2\nmid n, \\ \frac{n}{2} & 2\mid n.\end{cases}\].

Sanskar says that, for any positive integer $n$, the sequence $\{n,f(n),f(f(n)),f(f(f(n))),\ldots\}$ is eventually in constant loop(i.e. after a term all the next terms in the sequence are repeating in a certain period ) Is Sanskar right? Justify your answer with proof.

Solution1( Using strong induction and Fastest)

For any positive integer $n$, the second or third number in the sequence will always be less than $n$. Let us assume that every positive integer in $[1,k]$ will reach $1$ in its sequence. The number $k+1$ will reach a number less than it , that is some positive integer in $[1,k]$ and every positive integer in $[1,k]$ will reach $1$. Therefore, $k+1$ will also reach $1$. This is true for $k=2$, therefore for k=3,... If $k=1$, the sequence has already reached $1$. Therefore all positive integers $n$ will reach $1$. After reaching $1$ , the next number will be $f(1)=2$ and the next $=f(2)=1$ Therefore the sequence will finally be $1,2,1,2,...$ Therefore Sanskar is right. ~ mathenthusiast73

Problem 6

Find all integers $x$ such that ${x}^{11}$+${x}^{10}$+1 is a prime.

Problem 7

Consider a grid($n \times n$) of evenly spaced points for $n\geq 3$. Let $f(n)$ denote the maximum number $r$ such that the $r$ points can be colored in such a way that no 4 of them are concyclic. (i.e no 4 of the points lie on a circle).\\ Find $f(3)+f(4)+\dots+f(11)$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=SANSKAR%27S_OG_PROBLEMS&oldid=221164"