Maths Olympiad Prep

Library / /140 of 144

Combinatorics Difficulty 8.9 Shortlist Find the answer

For any two different real numbers xx and yy, we define D(x,y)D(x,y) to be the unique integer dd satisfying 2dxy<2d+12^d\le |x-y| < 2^{d+1}. Given a set of reals F\mathcal F, and an element xFx\in \mathcal F, we say that the [i]scales[/i] of xx in F\mathcal F are the values of D(x,y)D(x,y) for yFy\in\mathcal F with xyx\neq y. Let kk be a given positive integer.

Suppose that each member xx of F\mathcal F has at most kk different scales in F\mathcal F (note that these scales may depend on xx). What is the maximum possible size of F\mathcal F?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Given a set F\mathcal{F} of real numbers, we want to determine the maximum possible size of F\mathcal{F} given that each member xFx \in \mathcal{F} has at most kk different scales in relation to the other elements of F\mathcal{F}. The scale D(x,y)D(x,y) between two distinct elements xx and yy is defined as the unique integer dd such that 2dxy<2d+12^d \leq |x-y| < 2^{d+1}.

We will determine F|\mathcal{F}| such that the condition on the scales is satisfied. To maximize the number of elements in F\mathcal{F}, we consider a strategy for constructing F\mathcal{F}.

First, let's understand that for each element xFx \in \mathcal{F}, the possible scales D(x,y)D(x,y) constrain the set of numbers yFy \in \mathcal{F} such that yxy \neq x. If xx has at most kk different scales in F\mathcal{F}, it means that the differences xy|x-y| can be classified into at most kk distinct ranges based on powers of 2:

2d1xy1<2d1+1,2d2xy2<2d2+1,,2dkxyk<2dk+1. 2^{d_1} \leq |x-y_1| < 2^{d_1+1}, \quad 2^{d_2} \leq |x-y_2| < 2^{d_2+1}, \dots, \quad 2^{d_k} \leq |x-y_k| < 2^{d_k+1}.

Where d1,d2,,dkd_1, d_2, \ldots, d_k are distinct integers. Now, let’s construct a set F\mathcal{F} while respecting this condition.

A maximal strategy is to choose distances between successive elements in F\mathcal{F} 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 x1x_1.
- The next element x2x_2 can satisfy any scale 2d12^{d_1}.
- Continue by selecting x3x_3 to satisfy 2d22^{d_2}, 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:

x2x1=2d1,x3x2=2d2,x4x3=2d3, |x_2 - x_1| = 2^{d_1}, \quad |x_3 - x_2| = 2^{d_2}, \quad |x_4 - x_3| = 2^{d_3}, \ldots

Thus, the number of elements F|\mathcal{F}| 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 F|\mathcal{F}| is:

F=2k. |\mathcal{F}| = 2^k.

This maximum size occurs because with each doubling of scales, we can include one additional element into F\mathcal{F} without violating the constraint of having at most kk distinct scales for any element.

Therefore, the final answer for the maximum possible size of the set F\mathcal{F} is:
2k. \boxed{2^k}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.