0
$\begingroup$

Given a positive integer $h$, define: $$A_h=[2^h,2^{h}-1]\big \{2^h-1+\sum_{i\in A}2^i \Big/ A\subset[0,h-1]\big \}$$ (this is in terms of binary expressions: the set of all numbers having exactly $h$ digits in their binary operations)

Given a tuple $(a_1,\cdots,a_n)$, an operation consists of replacing some $a_j$ by either $2a_j,2a_j+1$ or by $a_k$ with $a_k\neq a_j$.

My question:

What is the maximum number of operations which could transform $(0,0,0)$ to some element $(a,b,c)$ with $a,b,c\in A_h$ such that all integers appearing in the intermediates tuples are less then or equal $2^h-1$ and no tuple appears twice in the process.

Exemple

It's clear that we can transform $(0,0,0)$ into $(2^h,2^h,2^h)$ in $h+3$ operations: $$(0,0,0)\xrightarrow{a:=2a+1} (1,0,0)\xrightarrow{a:=2a}(2,0,0)----\cdots \xrightarrow{a:=2a}(2^h,0,0)\xrightarrow{b:=a}(2^h,2^h,0)\xrightarrow{c:=a}(2^h,2^h,2^h)$$ this process is valid because all intermediate tuples have elements less than or equal to $2^h$ and no tuple appears two times. But I'm interested of the worst case : what would be the very long sequence using the operation?

Result: when we use pairs $(a,b)$ instead of tuples we have the maximum number of operations is $\frac{(h+1)(h+2)}{2}-1$.


A graph theory reformulation of the problem Let : $$ A_h=[2^h,2^{h}-1]\ \ \ \ B_h=[0,2^h-1] \\ V_h=B_h^3$$

Given $x=(a,b,c), x'=(a',b',c')\in V_h^3$ we have $(x,x')\in E_h$ if and only if there exists a rearrangement $a_1,a_2,a_3$ of $a',b',c'$ such that $a_1=a,a_2=b',a_3\in \{2a_3,2a_3+1,a_1,a_2\}$

Question: what would be the maximum length of a path between $(0,0,0)$ and $A_h^3$

Note this is a reformulation of my problem: how to maximize the number of operations in a process

$\endgroup$
  • $\begingroup$ Can I add elementary number theory here? $\endgroup$ – Elaqqad Apr 1 '15 at 16:15
  • $\begingroup$ When you say "no element appears twice in the process" you mean twice the same tuple, or twice the same $a_k$? $\endgroup$ – wece Apr 2 '15 at 13:28
  • $\begingroup$ I mean twice the same tuple $\endgroup$ – Elaqqad Apr 2 '15 at 13:34
  • $\begingroup$ Can you give me some details for the result $(h+1)(h+2)/2-1$ for pairs. I fail to see how to do better that $2h+2$ (I believe it's impossible since with more operation one of the element is surely greater than $2^h$, no?) $\endgroup$ – wece Apr 2 '15 at 14:33
  • $\begingroup$ You can start by :$(0,0)$ then you do $a=2a+1$ so that you get $(1,0)$ now you can multiply by $2$ successively $h$ times so that you get $(2^h,0)$ and then you do : $b=2b+1$ so you will have $(2^h,1)$ and now you can reset $a$ by doing :$b=a$ then you will have $(1,1)$ and then you can go to $(2^h,1)$ another $h$ operations, and you can increase $b$ by $b=2b$ and you will have $(2^h,2)$ and you reset $a:=b$ so that $(2,2)$ and $\cdots$ this is the process I think that you forgot that you can do $a=b$ (and you can do also : $b=a$) $\endgroup$ – Elaqqad Apr 2 '15 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.