Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For non negative integers $x,y,z$ define the following operation

$$(x,y,z) \to (x-1,y-1,z) \to (x-2,y-1,z-1) \to (x-2,y-2,z-2) \to (x-3,y-3,z-2) \to \cdots. $$

Continue the above process when at least two cells become zero. Also please don't consider the coordinate which already becomes zero.

For example $(2,2,1) \to (1,1,1) \to (0,1,0)$.

$$(3,1,2) \to (2,0,2) \to (1,0,1) \to (0,0,0).$$

Now function $f(x,y,z)$ is the number of such operation. So $f(2,2,1)=2$, $f(3,1,2)=3$.

I want to find $\sum_{x,y,z=0}^a f(x,y,z)$ as a function of $a$. I also try to generalize the above operation for $n$ coordinates and find $\sum_{x_1,x_2,\ldots, x_n=0}^a f(x_1,x_2,\ldots, x_n)$.

Please help me.

The following algorithm would better explain my problem. Let $x,y,z$ are variables.

t=0

for a=0 to m

for b=0 to m

for c=0 to m

s=$x^ay^bz^c$

s_0=0

while(s $\neq$ s_0){ s_0=s

        if xy divides s{

           s=s/xy

           t=t+1}

        if xz divides s{

           s=s/xz

           t=t+1        }

        if yz divides s{

           s=s/yz

           t=t+1  }

  }

I want to find t.

share|improve this question
1  
I don't see how that defines an operation; it's ambiguous what to do when you apply $\rightarrow$ for 3 arbitrary natural numbers. Maybe define it as a triplet of operations, which don't need their own symbol. Just subtract $(1,1,0)$, then $(1,0,1)$, etc. –  Eric Tressler Aug 6 '13 at 1:37
    
Yes, each time subtract (1,1,0), (1,0,1) and (0,1,1) sequentially, skip if any one of the corresponding cell is already 0, stop if two cells are zero. –  user46185 Aug 6 '13 at 1:45
    
@user46185 Then put this explanation in the body of the question! –  Matemáticos Chibchas Aug 6 '13 at 3:15
    
I changed a bunch of instances of $(2,2,1)->(1,1,1)$ to $(2,2,1)\to(1,1,1)$. That is standard usage. –  Michael Hardy Aug 6 '13 at 4:58
1  
@user46185 That explains why my answer isnt exactly what you want. I was using the full cycle substracting $(1,1,0), (1,0,1),(0,1,1),(1,1,0)$ and so on, using a given vector even if it was used on only one coordinate. –  Jean-Sébastien Aug 6 '13 at 18:25

2 Answers 2

up vote 1 down vote accepted

Given $v=(x_1,x_2,x_3)\in\mathbb N^3$, we define $r=r_v=\min\{x_1,x_2,x_3\}$ and $i=i_v=\min\{j: x_j=r\}$. The maximum number of times that you can apply the three "processes" $(1,1,0),(1,0,1), (0,1,1)$ together on $v$ (that is, without skipping) is the greatest $k=k_v$ such that

$$\min\bigl\{x_1-2(k-1),x_2-2(k-1),x_3-2(k-1)\bigr\}\geq2$$

(reason: the triple $\bigl(x_1-2(k-1),x_2-2(k-1),x_3-2(k-1)\bigr)$ corresponds to the penultimate possible application of all the three processes), that is $r-2(k-1)\geq2$, and so $k$ is the greatest integer such that $k\leq r/2$. Therefore $k=\lfloor r/2\rfloor$.

Let $w=v-2k\cdot(1,1,1)$. If $r$ is even, then $w$ has its $i$-th entry equal to $0$. Therefore exactly two of the three processes $(1,1,0),(1,0,1),(0,1,1)$ cannot be used anymore, and the remaining process can be applied exactly $\min\{x_j-2k:j\ne i\}$ times until obtaining another entry equal to $0$ (reason: this remaining process, when applied, subtracts $1$ from each entry different from the $i$-th entry). This shows that

$$f(v)=3k+\min\{x_j-2k: j\ne i\}=k+\min\{x_j: j\ne i\},\ \text{if}\ r\ \text{is even}\,.$$

If $r$ is odd, then $x_j-2k=1$ whenever $x_j=r$ and $x_j-2k>1$ otherwise. We consider the following cases (recall the definition of $i$):

$\boldsymbol{i=1:}$

In this case we can apply the process $(1,1,0)$ to $w=(1,x_2-2k,x_3-2k)$, obtaining the triple $(0,x_2-2k-1,x_3-2k)$. From now on the only available process is $(0,1,1)$, which can be applied precisely $\min\{x_2-2k-1,x_3-2k\}$ times until obtaining another entry equal to $0$. Summarizing, we get

$$f(v)=3k+1+\min\{x_2-1,x_3\}-2k=k+1+\min\{x_2-1,x_3\},\ \text{if}\ x_1\leq x_2,x_3\,.$$

$\boldsymbol{i=2:}$

We have $x_2<x_1$ and $x_2\leq x_3$, and $w=(x_1-2k,1,x_3-2k)$. We can apply process $(1,1,0)$, obtaining $(x_1-2k-1,0,x_3-2k)$. Now the only available process is $(1,0,1)$, which can be applied $\min\{x_1-2k-1,x_3-2k\}$ times until obtaining another entry equal to $0$. Therefore we have

$$f(v)=3k+1+\min\{x_1-1,x_3\}-2k=k+1+\min\{x_1-1,x_3\},\ \text{if}\ x_2<x_1\ \text{and}\ x_2\leq x_3\,.$$

$\boldsymbol{i=3:}$

In this case $x_3<x_1,x_2$ and $w=(x_1-2k,x_2-2k,1)$, so it is possible to apply both processes $(1,1,0)$ and $(1,0,1)$, obtaining the triple $(x_1-2k-2,x_2-2k-1,0)$, and now we apply process $(1,1,0)$ exactly $\min\{x_1-2k-2,x_2-2k-1\}$ times until obtaining another entry equal to $0$. Therefore

$$f(v)=3k+2+\min\{x_1-1,x_2\}-2k-1=k+1+\min\{x_1-1,x_2\},\ \text{if}\ x_3<x_1,x_2\,.$$

Given $a\in\mathbb N$, it remains to split the set $T=\{(x_1,x_2,x_3)\in\mathbb N^3: x_1,x_2,x_3\leq a\}$ into disjoint sets corresponding to the four cases considered above (and some subcases). Since we want to evaluate $S=\sum_{v\in T}f(v)$, we will successively add the values according to the emerging cases.

  • If we want $r=r_v$ to be even, then first we choose $t$ such that $0\leq2t\leq a/2$ and define $r_v=2t$, and so $k=\lfloor r/2\rfloor=t$. Now we consider several options:

    • If we want the minimum attained exactly once, then we have $3$ choices for the value of $i$ such that $r=x_i$, and necessarily we must have $r=2t<a$, which is equivalent to $t\leq\lfloor(a-1)/2\rfloor$. The other two entries can be equal, say, to $m\in\{2t+1,\dots,a\}$, so in this case we have $f(v)=k+\min\{x_j:j\ne i\}=t+m$. Consequently these cases contribute

      $$3\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{m=2t+1}^a(t+m)\tag{$I$}$$

      to the value of $S$. On the other hand, if we want the other two entries to be different, then we must have $2t<a-1$ in advance, that is $t\leq\lfloor(a-2)/2\rfloor=\lfloor a/2\rfloor-1$. Also, we have $2$ choices for the coordinate attaining that "intermediate" minimum, with value $m\in\{2t+1,\dots,a-1\}$, and finally we choose the remaining entry in the set $\{m+1,\dots,a\}$. These cases contribute

      $$3\cdot2\sum_{t=0}^{\lfloor\frac a2\rfloor-1}\sum_{m=2t+1}^{a-1}\sum_{j=m+1}^a(t+m)=6\sum_{t=0}^{\lfloor\frac a2\rfloor-1}\sum_{m=2t+1}^{a-1}(a-m)(t+m)\tag{$II$}$$ to the value of $S$.

    • Now, if we want the minimum to be attained exactly twice, then first we choose the corresponding two coordinates, which can be made into $\binom32=3$ ways, and we choose the value of the remaining entry in the set $\{2t+1,\dots,a\}$ (again, we must have $r=2t<a$ from the beginning, that is $t\leq\lfloor(a-1)/2\rfloor$). Note that in this case $\min\{x_j:j\ne i\}$ is equal to $\boldsymbol{2t}$. These cases contribute

      $$3\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{m=2t+1}^{a-1}\sum_{j=m+1}^a(t+2t)=9\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}t\sum_{m=2t+1}^{a-1}(a-m)\tag{$III$}$$

      to the value of $S$.

    • Finally, the case of all entries equal contributes (in this case we have $2t\leq a$, that is $t\leq\lfloor a/2\rfloor$)

      $$\sum_{t=0}^{\lfloor\frac a2\rfloor}(t+2t)=\frac32\,\biggl\lfloor\frac a2\biggr\rfloor\,\Biggl(\,\biggl\lfloor\frac a2\biggr\rfloor+1\Biggr)\tag{$IV$}$$ to the value of $S.\\[1cm]$

  • Now we consider the case $r$ odd. Then $r$ must be of the form $r=2t+1$, with $t\in\mathbb N$ such that $2t+1\leq a$, that is $t\leq\lfloor(a-1)/2\rfloor$. In this case $k=\lfloor r/2\rfloor=t$. Pay attention to the splitting of the innermost sums because of the minimum function that appears in their summands.

    • If $i=1$, then both $x_2$ and $x_3$ must be chosen in the set $\{2t+1,\dots,a\}$. The contribution for the value of $S$ is then equal to

      $$\begin{align*} &\,\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{x_3=2t+1}^a\sum_{x_2=2t+1}^a\bigl(t+1+\min \{x_2-1,x_3\}\bigr)\\ =&\,\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{x_3=2t+1}^a\Biggl[\,\sum_{x_2=2t+1}^{x_3}(t+1+x_2-1)\ \ +\,\sum_{x_2=x_3+1}^a(t+1+x_3)\,\Biggr]\,.\tag{$V$} \end{align*}$$

    • If $i=2$, then $x_1\in\{2t+2,\dots,a\}$ and $x_3\in\{2t+1,\dots,a\}$. The contribution for the value of $S$ is then equal to

      $$\begin{align*} &\,\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{x_3=2t+1}^a\sum_{x_1=2t+2}^a\bigl(t+1+\min \{x_1-1,x_3\}\bigr)\\ =&\,\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{x_3=2t+1}^a\Biggl[\,\sum_{x_1=2t+2}^{x_3}(t+1+x_1-1)\ \ +\,\sum_{x_1=x_3+1}^a(t+1+x_3)\,\Biggr]\,.\tag{$VI$} \end{align*}$$

    • If $i=3$, then both $x_1$ and $x_2$ must be chosen in the set $\{2t+2,\dots,a\}$. The contribution for the value of $S$ is then equal to

      $$\begin{align*} &\,\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{x_2=2t+2}^a\sum_{x_1=2t+2}^a\bigl(t+1+\min\{x_1-1,x_2\}\bigr)\\ =&\,\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{x_2=2t+2}^a\Biggl[\,\sum_{x_1=2t+2}^{x_2}(t+1+x_1-1)\ \ +\,\sum_{x_1=x_2+1}^a(t+1+x_2)\,\Biggr]\,.\tag{$VII$} \end{align*}$$

I used Mathematica to evaluate $S=(I)+\cdots+(VII)$. It is very convenient to separate the cases $a$ even and $a$ odd; otherwise the resulting formulas are very nasty because of the integer part, and not illuminating at all.

For $a=2b$ we obtain

$$S=5b+4b^2+\frac{19}2\,b^3+\frac{23}2\,b^4$$

and for $a=2b+1$ ($b\geq0$) we obtain

$$S=4+\frac{37}2\,b+\frac{71}2\,b^2+\frac{65}2\,b^3+\frac{23}2\,b^4\,.$$

In both cases above we have $b=\lfloor a/2\rfloor$, so modulo integer part, your desired sum is a polynomial in $a$ of degree $4$ with leader coefficient $\dfrac{23}{32}$ (and modulo mistakes, of course!!!).

share|improve this answer
    
Thank you so much. –  user46185 Aug 30 '13 at 4:02

Edit: It seems that OP doesn't want to use a vector, say $(1,1,0)$ if it can't substract from two coordinate. This answer is based on the use of the cyclic $(1,1,0)\to(1,0,1)\to(0,1,1)\to(1,1,0)\to \cdots$ and doesn't skip a particular vector if it can't substract from two coordinates, but rather just ignore the already zero position and substract from the other.

This ain't going to be pretty, plus I was pretty tired while doing it so there may be some errors. Assuming that by $\sum_{x,y,z=0}^a $ you mean that $x=0..n, y=0..n, z=0..n$ then I believe we have as follow.

Note that to get $f(x,y,z)$, it is sufficient to know when the middle value goes to zero. You should be able to see that if $x=n$ then it gets to zero at step $$ F_1:=\frac{3}{2}\,n-\frac{3}{4}-\frac{1}{4}\, \left( -1 \right) ^{n}. $$ This is a fancy way to express the $n$th number that is not divisible by $3$. It comes from the fact that for every step divisible by $3$ we do not remove a unit at $x$. Similarly, we define $$ F_2:=\frac{3}{2}\,n-\frac{1}{4}+\frac{1}{4}\, \left( -1 \right) ^{n}, \\ F_3:=\frac{3}{2}\,n+\frac{1}{4}-\frac{1}{4}\, \left( -1 \right) ^{n}, $$ which are respectively the $n$th number that isn't $2\mod 3$ and $1\mod 3$. Now we distinguish multiple cases.

Case $1$ is when $x=y=z$. In this case there are

\begin{equation} 1/4\,\sum _{n=1}^{a}F_2=1/4\,\sum _{n=1}^{a}6\,n-1+ \left( -1 \right) ^{n}=\frac{1}{8}\, \left( -1 \right) ^{a}-\frac{1}{8}+\frac{1}{2}\,a+\frac{3}{4}\,{a}^{2}. \end{equation} This is due to the fact that we must eliminate $2$ of them, and the second one will always come from the $y$ position.

Case $2$ is when $x=y,x\neq z$. In this case, we have $$ \frac{1}{4}\,\sum _{y=1}^{a} \left( \sum _{n=1}^{y-1}6\,n-1+ \left( -1 \right) ^{n}+\sum _{n=y+1}^{a}6\,n-3- \left( -1 \right) ^{n} \right) +\frac{1}{4}\,\sum _{y=1}^{a}6\,y-3- \left( -1 \right) ^{y}=\frac{3}{4}a^3+\frac{1}{4}a^2+\frac{1}{8}(-1)^{a+1}a-\frac{3}{8}a+\frac{1}{8}+\frac{1}{8}(-1)^{a+1}. $$ The first outer sum deals with the cases $(x,x, z>0)$ and the second one with $(x,x,0)$. Under the first sign, we split into two sums depending on $x<y$ (first inner sum) or $x>y$. In a similar fashion, we get for $(x,y,x),(y,x,x)$ the fonctions $$ \frac{1}{8}{\frac {a \left( 18{a}^{2} \left( -1 \right) ^{2a}+13 \left( -1 \right) ^{2a+1}- \left( -1 \right) ^{3a}+55 \left( -1 \right) ^{a+1}+108 \left( -1 \right) ^{a+1}{a}^{4}+172 \left( -1 \right) ^{a}{a}^{2}+8 \left( -1 \right) ^{a}a-75+40a+410{a}^{2} -48{a}^{3}-564{a}^{4}+216{a}^{6} \right) }{ \left( 5+ \left( -1 \right) ^{a}-6{a}^{2}+4a \right) \left( 5+ \left( -1 \right) ^{a }-6{a}^{2} \right) }} $$ (This is the only one Maple couldn't simplify neatly... it may have a mistake, I'll double check tomorrow) and $$ \frac{3}{4}\,{a}^{3}+\frac{3}{4}{a}^{2}+\frac{1}{8}\, \left( -1 \right) ^{a}a-\frac{1}{8}\,a+\frac{1}{8}\, \left( -1 \right) ^{a}-\frac{1}{8}. $$ Finally, for $(x,y,z)$ where none are the same, we split again in $6$ cases... I'll put the case $x<y<z$ here and then the sum of all those $6$ subcases. So for $x<y<z$ we get $$ \sum _{x=0}^{a-2} \left( \sum _{n=x+1}^{a-1} \left( \sum _{z=n+1}^{a}{ \it F_2} \right) \right)=\frac{1}{48}\left( 6\,{a}^{3}-2\,{a}^{2}-6\,a-1+3\, \left( -1 \right) ^{a+1 } \right) a $$ The outer sum sums over the possible value for $x$, the middle sum deals with the second minimum, in this case $y$, and the inner sums counts how many time we need to have $F_2$. For example with $a=3$, we want to have for $x<y<z$ the combinations $(0,1,2),(0,1,3),(0,2,3),(1,2,3)$. Note that when $y=1$ we count $F_2(n) a-n= 3-1=2 times, which is done by the inner sum.

I'll leave as an exercice the job of adding all those to get your desired value.

share|improve this answer
    
Thank you so much. I observe that Case 1 matches perfectly. For example when a=3, value would be 8. But for x =y and x \neq z, theoretical value will be 22 although actual value is 20. –  user46185 Aug 6 '13 at 16:24
    
@user46185 I get 22 by brute force counting. Forgetting the one that starts with 2 zeroes already, we have $(1,1,2),(1,1,3),(2,2,3),(1,1,0)(2,2,0),(3,3,0),(2,2,1),(3,3,1),(3,3,2),$ which fade respectively in $1,1,3,1,2,4,2,4,4$ for a total of $22$. –  Jean-Sébastien Aug 6 '13 at 17:05
    
Please note that f(3,3,0) should be 3 not 4. As (3,3,0) -> (2,2,0) -> (1,1,0) ->(0,0,0). –  user46185 Aug 6 '13 at 17:49
    
Will you kindly give me some idea for the exact problem? It seems function may be of the form ra^3 + ... For me, finding r is sufficient. –  user46185 Aug 6 '13 at 19:07
    
@user46185 I haven't given thought on how your skip condition would affect the function. Where did you encouter this problem? Perhaps some context would help –  Jean-Sébastien Aug 6 '13 at 19:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.