6
$\begingroup$

We are given a set $A = \{1,2,3 \:...\:256 \}$. I'm obliged to find such A', so:

  • $A' \subset A$
  • A' has the maximal possible cardinality
  • A' contains no elements x,y which satisfy the following equality: $x = 2y$

I came up with some thoughts, but I'm not sure that my answer is correct, and I'm sure that the task could be solved in a more mathematically beautiful style.

My reasoning was the following:
1. First, pick up all odd numbers from set A. It makes 128 elements. 2. Then, pick all even numbers, which are large enough to not comply with the equation $x = 2y$. They are $\{130, 132\:...\: 256\}$. It adds 64 elements.
3. Then we note, that half of those 64 elements could be divided by 2 and some odd number from set A'. So we should only use those elements from previous step, which comply x div 4 = 0.
4. Also, we can include some even numbers, which are small enough to not have and greater match. They are $\{2, 4\:...\: 64\}$. We have to skip every second of them, to not create new matches. It gives us another 16: $\{4,8,12\:...\: 64\}$. Though, we have skip every second of them again, since they build pairs with themselves. It's 8 now: $\{4,12\:...\: 32\}$
5. Thus, we have 128 + 32 + 8 = 168, which is the maximal cardinality of A'.

I believe this solution lacks proof of maximality. So I would appreciate if you guys could prove my solution correct or erroneous or suggest more mathematically advanced way of approaching this problem (for example, I tried to look at elements of A as sequences of 8 bits, but it didn't help me much).

$\endgroup$
8
  • 1
    $\begingroup$ Is y an element of A or A'? $\endgroup$ Commented Mar 11, 2014 at 9:13
  • $\begingroup$ @PhilipHoskins I rewrote question to be clearer. A' should be such a subset, so for any two elements x and y $x,y \in A'$ following exression never true: $x=2y$ $\endgroup$ Commented Mar 11, 2014 at 9:16
  • $\begingroup$ Ah, that makes things a bit more complicated. You could add 4 to A' and that would be admissible. This spoils the maximality of the set you constructed. $\endgroup$ Commented Mar 11, 2014 at 9:17
  • $\begingroup$ @PhilipHoskins You are right. I see it now. $\endgroup$ Commented Mar 11, 2014 at 9:20
  • $\begingroup$ Take the upper half of $A$. $\endgroup$ Commented Mar 11, 2014 at 9:29

4 Answers 4

Reset to default
7
$\begingroup$

I would split $A$ into subsets $A_0,\ldots,A_8$ where $A_i$ contains all numbers in $A$ with exactly $i$ powers of 2 in its factorization. Then $A_{i+1} \subset 2A_i$ and since the sets diminish in size the maximal subset would be $A_0\cup A_2\cup\ldots\cup A_8$.

$\endgroup$
3
$\begingroup$

for some odd number $X$ in $A$, consider the sequence $X, 2X, 4X, 8X...$ The rule that no element can be twice another is equivalent to saying that we can take at most every second element from any such sequence. The only question then is whether to start at $X$ or $2X$. If the sequence has an even number of elements it doesn't matter, but otherwise we will get one more number by starting at $X$.

def greatest_subset(): result = [] for i in range(1, 256, 2): while i <= 256: result.append(i) i *= 4 return result

$\endgroup$
2
$\begingroup$

With use of Marc's helpful answer, I wrote a Python implementation in order to get the actual value of A's cardinality. We got 171, so my original analytical solution in the question body was wrong.

def find_max_cardinality_subset(): As ={} for i in range(0,9): ai = [] divisor = pow(2,i) for x in range(0, 257): if x % divisor == 0 and (x / divisor) % 2 != 0: ai.append(x) As[i] = ai all = 0 for i in range(0,9, 2): all += len(As[i]) print("it totals:", all)
$\endgroup$
1
$\begingroup$

I think by only rooting off the first observation that the odd subset [1,3,5,7...255] satisfies the initial condition, one can iteratively extract additional even elements from A based solely on the condition that they would hold no conflict with x=2y from A' already generated. My math formalism is terrible, I know. But this should answer the question.

  1. {1,3,5,7...255} : 128 elements : Total 128

then 4*(subset 1) excluding those that go beyond the 256 limit 2. {4,12,20,28...1020} - {260,268...1020} : 128 - 96 = 32 elements : Total 160

then 4*{subset 2} excluding those that go beyond the 256 limit 3. {16,48,80...1008} - {272,304...1008} : 32 - 24 = 8 elements : Total 168

then 4*(subset 3) excluding those that go beyond the 256 limit 4. {64,192..960} - {320,448...960} : 8 - 6 = 2 elements : Total 170

The last remaining element that still fits within the limit is 4*64 = {256} Capping the total at 171. Feels a bit like brute force, but it works.

$\endgroup$
2
  • $\begingroup$ You might be interested to know that this is exactly what Marc's answer proposes, just rephrased in plainer language (for instance Marc's $A_0$ corresponds to your initial odd subset, and $A_8$ is your $\{256\}$). $\endgroup$ Commented Mar 11, 2014 at 15:35
  • $\begingroup$ On closer observation, I agree. I originally assumed his method didn't exclude odd powered multiples of two, but it actually does so elegantly. $\endgroup$ Commented Mar 11, 2014 at 16:29

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.