Non geos are cool!

 Hi! I am posting 5 quick, cute and simple non-geo questions!
I have posted their solutions too. The level is probably a good  INMO level. Do try them! I actually gsolved 4 of them with PC! All of them are from AOPS's Old highschool Olympiad forum.

Problem1: In the following triangular table

$$0,~1,~~2\dots 1958$$

$$1,~~3,~~5\dots 3915$$

$$\dots \dots$$

each number (except for those in the upper row) is equal to the sum of the two nearest numbers in the row above. Prove that the lowest number is divisible by $1958$

Solution: I actually messed up the calculation a bit (posted at MSE), so thanks to everyone who helped me :)

Well, $1958$ surely isn't special. So let's prove for any $$a_1,a_2,a_3,\dots a_n$$ triangular table.

So we have $$a_1~~a_2~~a_3~~a_4\dots \dots~~a_n$$

$$\downarrow$$

$$(a_1+a_2)~~(a_2+a_3)~~(a_3+a_4)~~(a_4+a_5)\dots \dots ~~(a_{n-1}+a_n)$$

$$\downarrow$$

$$(a_1+2a_2+a_3)~~(a_2+2a_3+a_4)\dots\dots ~~( a_{n-2}+2a_{n-1}+a_n)$$

$$\downarrow$$

$$(a_1+3a_2+3a_3+a_4)~~(a_2+3a_3+3a_4+a_5)\dots \dots$$

$$\downarrow$$

$$(a_1+4a_2+6a_3+4a_4+a_5)~~ (a_2+4a_3+6a_4+4a_5+a_6)\dots$$

$$\downarrow$$

$$(a_1+5a_2+10a_3+10a_4+5a_5+a_6)\dots$$

$$\vdots$$

Now, we only care about the first term of each row. In the last row of the table, there is only one term.

Now, one can notice the pattern in the first terms, in general (proovable by induction) they are of the form $$(a_1+\binom{k}{1}a_2+\dots + \binom {k}{2}a_{k-1}+\binom{k}{k-1}a_k+a_{k+1}).$$

So the last row's term will be $$(a_1+\binom{n-1}{1}a_2+ \binom{n-1}{2}a_3+\dots + \binom{n-1}{n-2}a_{n-1}+a_n).$$

Then we have $a_1=0,n=1959.$

So we get $$\binom{1958}{1}1+ \binom{1958}{2}2+\dots + \binom{1958}{1957}1957 +  \binom{1958}{1958}1958 =2^{1958-1}1958.$$

Where we got the last line by using the property by differentiating $(1+x)^{1958}$ and then take $x=1.$

Problem2: There are $315$ marbles divided into three piles of $81, 115$ and $119$. In each move Ah Meng can either merge several piles into a single pile or divide a pile with an even number of marbles into $2$ equal piles. Can Ah Meng divide the marbles into $315$ piles, each with a single marble?

Solution: Note that, if we have $n$ numbers as the pile numbers with common $\gcd=d, d>2.$ So we have say $da_1,~da_2,\dots, da_n.$ 

Then whatever moves we make, the resultant pile numbers will be divisible by $d.$

For example, say we have a pile having $$115~~100~~100 \rightarrow 115,~~50,~~50,~~50,~~50$$

Then whatever move we do, we can atmost reach $$5,~~5\dots \dots,5~~5.$$

Now, note that $\gcd(81, 115+119=234)=9.$

So the pile number will always be divisible by $9.$ For this case we can't achieve pile numbers as $1,1,\dots 1$ $315$ times..

Now, note that $\gcd(115,81+119=200)=5.$

So the pile number will always be divisible by $5.$ For this case we can't achieve pile numbers as $1,1,\dots 1$ $315$ times..

Now, note that $\gcd(119,81+115=196)=7.$

Same reason.

Hence Ah Meng can not divide the marbles into $315$ piles, each with a single marble.

Problem3: Two players $A$ and $B$ take stones one after the other from a heap with $n \ge 2$ stones. $A$ begins the game and takes at least one stone, but no more than $n -1$ stones. Thereafter, a player on turn takes at least one, but no more than the other player has taken before him. The player who takes the last stone wins. Who of the players has a winning strategy?

Answer: When $n$ is not a perfect power of $2$ then $A$ wins. If $n$ is a perfect power of $2,$ then $B$ wins.

Solution: If there are an odd number of stones then $A$ wins. 

Because then $A$ takes $1$ stone and then $B$ is forced to take only $1$ stone. And then $A$ takes $1$ stone and so on. Since we have odd number of stones. $A$ will be the last person to take the stone, hence $A$ wins.

 Claim: If $v_2(n)=1,~~n\ne 2,$ then $A$ wins.

$A$ starts with taking $2$ stones. Now, $B$ won't take $1$ stone, because then $A$ will get odd stones, and we know having odd stones means we can win. Hence $B$ will take $2$ stones. Since $v_2(n)=1,$ we know that $A$ will be the last person to take the stone.

 Claim: If $v_2(n)=2,n\ne 4$ then $A$ wins

$A$ starts with taking $4$ stones. Now, $B$ knows that if $A$ gets a stones with $v_2(n)=0,1;$ $A$ wins. Hence $B$ will take $4$ stones and will try to maintain $v_2(n)=2.$ But then we know $n=4k,~k\ne 1$ odd. Hence, $A$ will win.

So this gives induction vibes. 

Claim:  If $n$ not a perfect power of $2,$ $A$ wins. We prove it using induction.

Consider $v_2(n).$ For $v_2(n)=0,1,2$ $A$ wins. Suppose $A$ wins for $v_2(n)=0,1,\dots k.$

Now we will show that $A$  wins for $v_2(n)=k+1\implies n=2^{k+1}\cdot m,~~m>1$ is odd. 

$A$ will subtract $2^{k+1}.$ $B$ knows that $A$ will win if $A$ has $v_2(n)<k+1.$ Hence $B$ will try to maintain $v_2(n)=k+1.$ So $B$ subtarcts $2^{k+1}.$ And then again $A$ subtracts $2^{k+1}$ and so on. But $A$ will win since $m>1$ is odd. 

And we are done.

 Claim: When $n$ is a perfect power of $2.$ Then $B$ wins.

If $n=2^k,$ $A$ has to take less than $2^{k-1}$ stones because if not in the next move $B$ can take everything. 

But then whatever $A$ takes, $B$ will receive a "non-perfect power of $2$" number of stones. Which we know is a winnable situation. So $B$ wins.

Problem4: Find all natural numbers n with the following property : there exists a permutation $(i_1,i_2,\ldots,i_n)$ of the numbers $1,2,\ldots,n$ such that, if on the circular table there are $n$ people seated and for all $k=1,2,\ldots,n$ the $k$-th person is moving $i_k$ places in the right, all people will sit on different places.

Solution: We claim that only odd $n$ satisfy the condition.

Claim: Odd $n$ work.

Let $(i_1, i_2, \ldots, i_n)$ = $(1,2, \ldots, n)$. Let us denote the initial positions of $n$ persons by $(1, 2, \ldots, n)$

Then the final positions are $(1+1, 2+2, \ldots, n +n)$. So if we prove that all elements of the set $2\cdot {1,2, \ldots, n}$ are distinct. 

Since $gcd(n,2) = 1$ for odd $n$, so the elements of set will be unique and from $1$ to $n$, which satisfy the condition.

Claim: Even n don't work 

Suppose not then we must have 

$$\{1 + i_1, 2 + i_2, \ldots, n + i_n\} \equiv \{1, 2, \ldots, n\} \pmod{n}$$

$$\implies \sum_{j = 1}^n i_j \equiv 0 \pmod{n}$$

Let $n = 2k$

$$\implies k(2k+1) \equiv 0 \pmod{2k}$$

Since $gcd(2k, 2k+1) = 1$

$$\implies k \equiv 0 \pmod{2k}$$

Which is clearly false. 

Problem5: Find all triples $(x, y, z)$ such that $x, y, z, x - y, y - z, x - z$ are all prime positive integers.

Solution: We claim that $(x,y,z) = (7, 5, 2)$ is the only solution.

Clearly, by the question statement $x > y > z$

 Claim: $z = 2$

If all the 3 variables are odd, then their pairwise difference must be even, i.e. 2, as it is the only even prime.

$$\implies x = y+2,\enspace y = z+2, \enspace x = z+2$$

$$x = z + 4 = z+ 4$$

which is not possible. 

 One of them is $2$, since $z$ is smallest and $2$ is the smallest prime $\implies z = 2$

Now, $x-2, x, x+2$ must be all prime as per the question. 

Since $x \equiv 1, 2 \pmod{3}$

 $\implies$ one of $x-2$, $x$, $x+2$ must be divisible by 3.

$$\implies x - 2 = 3 \implies x = 5$$

$$\implies y = 7$$

$$\implies (x,y,z) = (7,5,2)$$

Yeaaahhh.. This is it for this week. Now, I am taking a break from Olys (till 20th), since I have quite a nice heavy backlog in school and jee! And we have a test at 20, which I am going to fail massively.

Speaking about the school, CBSE 10 results came and I got 95.66%. I think I could have got better marks in IT though but nvm I am happy with what I got!

Also although I am taking a break, I have already prepared the things needed for the next blogpost (hehehe).

So yeah! If you like this type of content then follow the blog! Maybe visit weekly once. Actually, the email subscription isn't working :(.

See you soon,
Sunaina 💜