Like Father Like Son... (or Like Grandson?)

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Like Father Like Son... (or Like Grandson?)

G H J

Reveal topic tags

Coprime integers

L

G H BBookmark kLocked kLocked NReply

Source: Turkey TST 2025 P4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

82 posts

#1 h Mar 18, 2025, 6:09 AM

Y by

Let $a,b,c$ be given pairwise coprime positive integers where $a>bc$ . Let $m<n$ be positive integers. We call $m$ to be a grandson of $n$ if and only if, for all possible piles of stones whose total mass adds up to $n$ and consist of stones with masses $a,b,c$ , it's possible to take some of the stones out from this pile in a way that in the end, we can obtain a new pile of stones with total mass of $m$ . Find the greatest possible number that doesn't have any grandsons.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

429 posts

hakN

#2 h Mar 18, 2025, 5:20 PM • 1 Y

Y by sevket12

The answer is $abc$ . Notice if $abc$ has a grandson $t$ , then $abc = a + a + \dots + a = b + b + \dots + b = c + c + \dots + c \implies abc \mid t$ , contradiction.

Let $n > abc$ and choose $v \le bc$ such that $av \equiv n \pmod{bc}$ and let $n - av = bcd$ for $d\ge 1$ . We claim $av$ is a grandson of $n$ , concluding the proof.

Let $n = xa + yb + zc$ . We can assume $x < v$ as otherwise clearly $av$ is obtainable. Let us also assume $n = xa + yb + z'c + kbc$ with $z' < b$ and $k\ge 1$ . Now if $y + ck < cd$ , then $xa+yb+zc=n\le (v-1)a+(cd-1)b+(b-1)c = n - a - b + bc - c < n$ by the given condition $a > bc$ , contradiction. Otherwise, $y + ck \ge cd$ , and we then have $av = n - bcd$ is obtainable, as desired.

This post has been edited 1 time. Last edited by hakN, Mar 18, 2025, 5:21 PM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

170 posts

#3 h Yesterday at 10:49 AM

Y by

This one was really tough... Much harder than the P2 of Day 1.

I claim the answer is $abc$ . Notice that $abc=a+\ldots+a=b+\ldots+b=c+\ldots+c$ , so the grandson of $abc$ must be divisible by $a$ , $b$ and $c$ , and since they are coprime, by $abc$ . But the grandson also must be smaller than the number itself, so $abc$ can't have a grandson.

Now let $N>abc$ , and let $1 \leq t \leq bc$ be such that $at \equiv N \pmod {bc}$ . I claim that $at \leq abc < N$ is a grandson of $N$ . By Chicken McNuggets there exist $x,y \in \mathbb{N}$ such that $bx+cy=a$ . Now let $N=au+bv+cw$ be any representation of $N$ . Until $v<x$ or $w<y$ we replace $(u,v,w)$ by $(u+1,v-x,w-y)$ . Note that this can not make any value appear in the set of the possible sizes of new piles after removal. Now WLOG $v<x$ , then $bv<bx<bx+cy=a$ . If $u \geq t$ , we are done by removing everything except $t$ stones with mass $a$ . Now suppose $u \leq t-1$ , then $au+bv<a(t-1)+a=at$ , and $N \equiv at \pmod b$ , so we can take $u$ stones with mass $a$ , $v$ stones with mass $b$ and add stones with mass $c$ until the total mass becomes $at$ . Thus $at$ is a grandson of $N$ .

This post has been edited 1 time. Last edited by atdaotlohbh, Yesterday at 10:50 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a