Factor sums of integers

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

Factor sums of integers

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

1562 posts

Aopamy

#1 h Feb 23, 2023, 3:13 AM

Y by

Let $n$ be a positive integer. A positive integer $k$ is called a benefactor of $n$ if the positive divisors of $k$ can be partitioned into two sets $A$ and $B$ such that $n$ is equal to the sum of elements in $A$ minus the sum of the elements in $B$ . Note that $A$ or $B$ could be empty, and that the sum of the elements of the empty set is $0$ .

For example, $15$ is a benefactor of $18$ because $1+5+15-3=18$ .

Show that every positive integer $n$ has at least $2023$ benefactors.

Z K Y

The post below has been deleted. Click to close.

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

577 posts

#2 h Apr 22, 2025, 3:56 PM

Y by

Bump! This was Australia AMO 2023 Problem 7

Z K Y

The post below has been deleted. Click to close.

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

701 posts

#3 h Apr 22, 2025, 5:08 PM

Y by

We will in fact prove that every integer has infinitely many benefactors. Firstly, let us define a positive integer $k$ to be a good number if for any $u\leq \sigma(k):=\sigma(D_k)$ there is a set $A\subseteq D_k$ with $u=\sigma(A)$ (where $\sigma(A)$ denotes the sum of the set $A$ and $D_k$ denotes the set of (positive) divisors of $k$ ).
In general we have that if $k$ is good, then $k$ is a benefactor of $n$ if and only if $n\in k+2\mathbb Z\cap [-\sigma(k),\sigma(k)]$ . This is because in general if $D_k=A\sqcup B$ , then $n=\sigma(B)-\sigma(A)=\sigma(D_k)-\sigma(A)-\sigma(A)=\sigma(k)-2\sigma(A)$ .
So, to prove our final result, it suffices to prove that there are infinitely many good numbers $k$ with $\sigma(k)$ even and infinitely many good numbers $k$ with $\sigma(k)$ being odd.
To prove this, pick $k=3\cdot 2^m$ or $k=2^m$ respectively (with $m\geq 1$ ). In the second case we can clearly write in base $2$ any integer in $[0,2^{m+1}-1]$ using a sum of distinct powers of two each of which is at most $2^m$ , as wanted. In the first case, we can write any $0\leq u\leq \sigma(k)=(3+1)(2^{m+1}-1)=4(2^{m+1}-1)$ as $u=3a+b$ with $0\leq a,b\leq 2^{m+1}-1$ (here we must use that $m\geq 1$ ), and then we can again write $a$ and $b$ in binary as before.
So, for any $m\geq 1$ we have that $k=3\cdot 2^m$ and $k=2^m$ are both good numbers with even (respectively odd) divisor sums, and thus we are done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a