Consider a function such that for every integer , there are at most pairs of integers for which and . Is it possible that for some integer , there are more than integers such that and ?
Proposed by David Yang
Consider a function such that for every integer , there are at most pairs of integers for which and . Is it possible that for some integer , there are more than integers such that and ?
Proposed by David Yang
1. Definitions and Setup:
- An integer is bad if .
- A pair of integers is bad if .
- A pair of integers is awful if at least one of or is bad and is also bad.
2. Interval Consideration:
- Fix an arbitrary and consider the interval .
- Slightly tweak the definition of awful to require .
3. Counting Awful Pairs:
- For every bad , any with must be either bad or awful.
- Since for any there are at least such pairs (actually , but we use for simplicity), if we have bad integers in , then there are at least awful pairs.
4. Bounding the Number of Bad Integers:
- It follows that there's some bad integer that's in at least awful pairs.
- Since every awful pair generates a different bad integer as its sum, we have:
Simplifying this inequality:
Solving the quadratic inequality:
5. **Conclusion for Small :**
- For small (say, ), we actually need for all , which implies is linear over .
- Thus, falls in the first interval (since it's zero), and if at some point we transition between being in the first interval to the second interval for , we have to increase by more than 2 by discrete continuity, which is impossible.
6. Final Conclusion:
- Therefore, stays in the first interval, so there are at most bad numbers in (actually way less), as desired.