2019年3月27日 星期三

訓練數學感 208 ─ 有幾個數列符合?

https://4rdp.blogspot.com/2019/03/208.html

有一數列,其項數共 19 項,首項及末項皆為 0,其它每項目不是 0 就是 1,數列各項沒有連續兩個 0,也沒有連續三個 1,請問滿足這些條件的數列有幾個?


我喜歡這類比較不抽象的數學題材,這題也是 2018 AMC 10 的考題之一。

12 則留言:

  1. 另一種表達方式:
    從65537到131071這些數字中,找出如下要求的數列,
    1,在每連續的四個數中,中間的兩個數必須至少有一個存在
    2,該數字也不能被寫成2^a+2^b+……+2^n+7x的形式(a……n為1-17的正整數,x為自然數)

    回覆刪除
    回覆
    1. 謝謝老師指出另外思考的方法,第一種限制可以理解,但是第二種就不易理解了。

      刪除
    2. 二進制中,111表示成十進制就是7。
      連續的三個1換成十進制就一定能被7整除。

      刪除
    3. 從65537開始範圍太大,從87381開始更好。
      剛好是101010……互相間隔開。
      然後開始逐個嘗試:
      1、遇到00的情況就跳到01
      2、遇到0111的情況就跳到1000
      最後數到有65個。
      -
      https://drive.google.com/file/d/1NxBx3oPPiDMuyNo86WJIviqb4hUO_gP9/view?usp=sharing
      運行宏Module1.rdp208

      刪除
    4. 目前我想到的也是用程式暴力搜尋,用 Python 寫一個。

      刪除
    5. Python 計數總數 114

      n = 0
      for x in range(65537, 131072):
      sr = bin(x)
      if sr.find("00") != -1:
      print(x, n)
      continue
      if sr.find("111") != -1:
      print(x, n)
      continue
      n += 1
      print(sr, n)

      刪除
    6. if sr.find("00") != -1:
      print(x, n)
      在之後加上類似這樣的會比較快(我不懂python,下面這段是偽代碼)
      else: n+=2^[16-sr.find("00")]-1
      -----------------------------------------------------------
      if sr.find("111") != -1:
      print(x, n)
      這段後面也要加,要變動一下
      else: n+=2^[15-sr.find("111")]-1
      ---------------------------------
      跳過那些明顯不可能的數字,會快不少

      刪除
    7. 嗯,可以再修改程式加速搜尋,留給有興趣的朋友修改。

      刪除
    8. 汪先生,我還是只找到65個
      不如把找到的答案都列出來對比一下,看有沒有重復的。

      刪除
    9. 87381
      87387
      87403
      87405
      87467
      87469
      87477
      87723
      87725
      87733
      87765
      87771
      88747
      88749
      88757
      88789
      88795
      88917
      88923
      88939
      88941
      92843
      92845
      92853
      92885
      92891
      93013
      93019
      93035
      93037
      93525
      93531
      93547
      93549
      93611
      93613
      93621
      109227
      109229
      109237
      109269
      109275
      109397
      109403
      109419
      109421
      109909
      109915
      109931
      109933
      109995
      109997
      110005
      111957
      111963
      111979
      111981
      112043
      112045
      112053
      112299
      112301
      112309
      112341
      112347

      刪除
    10. 老師,我的答案是
      87381 0b10101010101010101 1
      87382 0b10101010101010110 2
      87386 0b10101010101011010 3
      87387 0b10101010101011011 4
      87402 0b10101010101101010 5
      87403 0b10101010101101011 6
      87405 0b10101010101101101 7
      87466 0b10101010110101010 8
      87467 0b10101010110101011 9
      87469 0b10101010110101101 10
      87477 0b10101010110110101 11
      87478 0b10101010110110110 12
      87722 0b10101011010101010 13
      87723 0b10101011010101011 14
      87725 0b10101011010101101 15
      87733 0b10101011010110101 16
      87734 0b10101011010110110 17
      87765 0b10101011011010101 18
      87766 0b10101011011010110 19
      87770 0b10101011011011010 20
      87771 0b10101011011011011 21
      88746 0b10101101010101010 22
      88747 0b10101101010101011 23
      88749 0b10101101010101101 24
      88757 0b10101101010110101 25
      88758 0b10101101010110110 26
      88789 0b10101101011010101 27
      88790 0b10101101011010110 28
      88794 0b10101101011011010 29
      88795 0b10101101011011011 30
      88917 0b10101101101010101 31
      88918 0b10101101101010110 32
      88922 0b10101101101011010 33
      88923 0b10101101101011011 34
      88938 0b10101101101101010 35
      88939 0b10101101101101011 36
      88941 0b10101101101101101 37
      92842 0b10110101010101010 38
      92843 0b10110101010101011 39
      92845 0b10110101010101101 40
      92853 0b10110101010110101 41
      92854 0b10110101010110110 42
      92885 0b10110101011010101 43
      92886 0b10110101011010110 44
      92890 0b10110101011011010 45
      92891 0b10110101011011011 46
      93013 0b10110101101010101 47
      93014 0b10110101101010110 48
      93018 0b10110101101011010 49
      93019 0b10110101101011011 50
      93034 0b10110101101101010 51
      93035 0b10110101101101011 52
      93037 0b10110101101101101 53
      93525 0b10110110101010101 54
      93526 0b10110110101010110 55
      93530 0b10110110101011010 56
      93531 0b10110110101011011 57
      93546 0b10110110101101010 58
      93547 0b10110110101101011 59
      93549 0b10110110101101101 60
      93610 0b10110110110101010 61
      93611 0b10110110110101011 62
      93613 0b10110110110101101 63
      93621 0b10110110110110101 64
      93622 0b10110110110110110 65
      109226 0b11010101010101010 66
      109227 0b11010101010101011 67
      109229 0b11010101010101101 68
      109237 0b11010101010110101 69
      109238 0b11010101010110110 70
      109269 0b11010101011010101 71
      109270 0b11010101011010110 72
      109274 0b11010101011011010 73
      109275 0b11010101011011011 74
      109397 0b11010101101010101 75
      109398 0b11010101101010110 76
      109402 0b11010101101011010 77
      109403 0b11010101101011011 78
      109418 0b11010101101101010 79
      109419 0b11010101101101011 80
      109421 0b11010101101101101 81
      109909 0b11010110101010101 82
      109910 0b11010110101010110 83
      109914 0b11010110101011010 84
      109915 0b11010110101011011 85
      109930 0b11010110101101010 86
      109931 0b11010110101101011 87
      109933 0b11010110101101101 88
      109994 0b11010110110101010 89
      109995 0b11010110110101011 90
      109997 0b11010110110101101 91
      110005 0b11010110110110101 92
      110006 0b11010110110110110 93
      111957 0b11011010101010101 94
      111958 0b11011010101010110 95
      111962 0b11011010101011010 96
      111963 0b11011010101011011 97
      111978 0b11011010101101010 98
      111979 0b11011010101101011 99
      111981 0b11011010101101101 100
      112042 0b11011010110101010 101
      112043 0b11011010110101011 102
      112045 0b11011010110101101 103
      112053 0b11011010110110101 104
      112054 0b11011010110110110 105
      112298 0b11011011010101010 106
      112299 0b11011011010101011 107
      112301 0b11011011010101101 108
      112309 0b11011011010110101 109
      112310 0b11011011010110110 110
      112341 0b11011011011010101 111
      112342 0b11011011011010110 112
      112346 0b11011011011011010 113
      112347 0b11011011011011011 114

      刪除
    11. 啊,看到自己錯在哪,不能是偶數,65個正解。

      刪除