For any two different real numbers and , we define to be the unique integer satisfying . Given a set of reals , and an element , we say that the [i]scales[/i] of in are the values of for with . Let be a given positive integer.
Suppose that each member of has at most different scales in (note that these scales may depend on ). What is the maximum possible size of ?
Solution
Given a set of real numbers, we want to determine the maximum possible size of given that each member has at most different scales in relation to the other elements of . The scale between two distinct elements and is defined as the unique integer such that .
We will determine such that the condition on the scales is satisfied. To maximize the number of elements in , we consider a strategy for constructing .
First, let's understand that for each element , the possible scales constrain the set of numbers such that . If has at most different scales in , it means that the differences can be classified into at most distinct ranges based on powers of 2:
Where are distinct integers. Now, let’s construct a set while respecting this condition.
A maximal strategy is to choose distances between successive elements in to respect distinct scales for each element. Consider an arrangement where each element is separated by uniform powers of 2:
- Start with the first element .
- The next element can satisfy any scale .
- Continue by selecting to satisfy , and so forth.
In this way, any new element requiring a new distinct scale will double the previous gap, leading to powers of 2 given by:
Thus, the number of elements will depend on the number of distinct powers of scales that can be combined. Specifically, since each distinct scale occupies one unit of scale space, the maximum is:
This maximum size occurs because with each doubling of scales, we can include one additional element into without violating the constraint of having at most distinct scales for any element.
Therefore, the final answer for the maximum possible size of the set is: