钱老六挖比特币不知其数

大酱风度
楼主 (文学峸)

话说钱老六数年如一日几乎天天都挖比特币。最开始的第一天他挖了1枚比特币,到第2000天时,他的会计太太问他刚开始的第2天挖了几枚比特币。钱老六挠了挠头说具体记不清了,但肯定多于两枚。当钱太再次追问时,钱老六掏出笔来写出了下面这个挖币公式:

然后,钱老六又数了数第2000天挖的枚数,发现和第1999天挖的枚数相差了7枚。问钱老六第二天挖了多少枚比特币?

 

k
kde235
挖了8枚?

用e[i]表示第i天的挖币数。 e[i]是一个整数(有可能小于0), 则如题所示

  e[i] = 2e[i-1] - e[i-2]
      or 2e[i-2] - e[i-1]
      
上式亦即
 
   e[i]-e[i-1] = e[i-1] - e[i-2]
             or  2(e[i-2] - e[i-1])
              
              
设 d[i] = e[i] - e[i-1], 则有

     d[i] = d[i-1]
         or (-2)*d[i-1]
        
可写成
     d[i] = (-2)^a[i] * d[i-1]    
     a[i] 为 1 或 0

因此  7 = d[2000]
       = (-2)^a[2000] * d[1999]
       = (-2)^a[2000] * (-2)^a[1999] * d[1998]
       = ...
       = (-2)^a[2000] * (-2)^a[1999] * ... * (-2)^a[3] * d[2]
       = (-2)^(a[2000]+a[1999]+...+a[3]) * d[2]
       = (-2)^k * d[2]
k为a[3],a[4],...a[2000]中等于1的个数
       
由此   7 = (-2)^k * d[2]
因为 7不含2因子,只可能k=0,d[2]=7
因此  e[2] = e[1] + d[2]
          = 1 + 7
          = 8

大酱风度
高,实在是高! 看透了题的实质和关键。

国家队水平。有真才实学,赞!

大酱风度
用整除概念的变形解法。。。

用e[i]表示第i天的挖币数。 e[i]是一个整数(有可能小于0), 则如题所示

 

  e[i] = 2e[i-1] - e[i-2]

      or 2e[i-2] - e[i-1]

      

上式亦即

 

   e[i]-e[i-1] = e[i-1] - e[i-2]

             or 2(e[i-2] - e[i-1])

              

              

设 d[i] = e[i] - e[i-1], 则有

 

     d[i] = d[i-1]

         or (-2)*d[i-1]

 如果从这一步,用如下reasoning如何?

因此: d[i-1]|d[i],

可得:d[1]|d[2]|d[3]|......|d[2000]

得: d[1]|d[2000]===>d[1]|+/- 7

d[1]=+/- 1 or +/-7

Only 7 works

e[2]=1+7=8

 

* 后来题中改成成了相差7, e[2] 大于2. 更broad, 一些。

===========================      

可写成

     d[i] = (-2)^a[i] * d[i-1]    

     a[i] 为 1 或 0

 

因此 7 = d[2000]

       = (-2)^a[2000] * d[1999]

       = (-2)^a[2000] * (-2)^a[1999] * d[1998]

       = ...

       = (-2)^a[2000] * (-2)^a[1999] * ... * (-2)^a[3] * d[2]

       = (-2)^(a[2000]+a[1999]+...+a[3]) * d[2]

       = (-2)^k * d[2]

k为a[3],a[4],...a[2000]中等于1的个数

       

由此 7 = (-2)^k * d[2]

因为 7不含2因子,只可能k=0,d[2]=7

因此 e[2] = e[1] + d[2]

          = 1 + 7

          = 8

k
kde235
用整除性质很好, 更简洁些。
大酱风度
各有千秋,实算得到的信息更多,更精细。

问题还可以扩展。

w
wxcfan123
请教两位大侠。

 

k
kde235
分析很好

关于相邻项奇偶性分析非常好,完全同意。 但不理解为何满足递推公式
  e[i+2]-e[i+1] = e[i+1]-e[i]      ----- (1)
的数列是第三项才开始有等差性质,我感觉应该是整个数列都等差。 以你给出的例子分析:
 1, 4, 7, 14, 21, ...

当i=2时, (1)式为
 e[4] - e[3] = e[3] - e[2]
在此数列中就是
 14  -  7   =   7  - 4
不成立

w
wxcfan123
递推公式的初始条件有两个,所以等差是从第三项开始的。而第三项只要满足 e[3] = 2e[2] - 1 的递推公式就行。

奇偶性则是一开始就有了。即,如果e[1],e[2]同为奇(偶),则项差为奇就不可能。

w
wxcfan123
看了一下两位的推理。递推公式中e[2], e[1]是独立变量。其差不应该纳入项差的计算中。
w
wxcfan123
奇偶分析仅对给出的项差是奇数成立。如改为偶数,例如8,那第二项会是9吗?还没有真正领会二位的推理。
k
kde235
有点绕:) 请问第四项需要满足递推公式吗? e[4] = ?
大酱风度
所提的问题非常好。初始条件确实是由头两项确定

但初始条件一旦确定,以后的数据结构也就确定了。这道题说第2000天与第1999天的差别,就是给出反推初始条件的条件(从当前反推过去)。

如果第一天是1,第二天是4(而不是8), 按题中给定的公式递推,第3天是7, 第4天是10 (而非14), 以此类推,第2000天和第1999天会相差3而不是7。和题意不符。

非常好的问题,促进思考,对问题更深入了一步。

大酱风度
“谈笑有鸿儒,往来无白丁”. 交流切磋,胜读十年。。。
w
wxcfan123
谢谢指正! 更正如下。第二项确实是8。算是第三种解法吧。

w
wxcfan123
只是主观的认为第二项不能确定。忘了这一点。见下面的更正。
大酱风度
好! 独辟蹊径,新思想,新解法。奇偶分析简化了许多事情。
万斤油
好玩的是,钱老六2000天中其实一天都没有卖过,他的第二个公式是怎么来的?
w
wxcfan123
复盘思考。

严格的说,因为递推公式只从第三项开始,上面的解法一,二只能推出d[4]|7或7=(-2)^k*d[4]. (题中的条件实际上是这个差可正可负)

以下还是要解关于e[2]和e[3]的方程。将有4种组合。

非常有意思的是,即使将7换成一个任意奇数k,由解法三,解方程

y=2x - 1;  y+k = 2y - x, 所得的解为 x = k+1.

即是,这个数列仍是从1 开始以k 为公差的等差数列。

题中的条件e[2]不等于2可以拿掉。

题中的条件中有可能e[2000]-e[1999]=-7. 对于奇数这个显然不可能。

但是,如果是偶数,这就有可能d[2000]=e[2000]-e[1999]<0.

 

 

大酱风度
第二个公式是打马虎眼,使问题复杂化一些。可以证明,第二个Scenario不存在。
大酱风度
第二项如果是8 (或其它合数), 问题要复杂一些。

第二项不一定是9, 虽然9是其中一个可能的解。