Challenge 81: Can You Count the Number of 001 and 100?

Share
Embed
  • Published on Feb 21, 2019
  • Congratulations to Avi Uday, Benjamin Wang, aby p, Arun Bharadwaj, Andre Ben, Jaleb, 張惟淳, Serengeti Ghasa, Varun Shah, and mstmar for successfully solving the last week's math challenge question! Avi Uday was the first person to solve the question.
    Welcome, everyone! LetsSolveMathProblems presents one weekly math challenge problem every Wednesday (continental U.S. time). To participate, please comment your proposed answer and explanation below (or discuss potential solutions with other viewers), keeping in mind that your comment should be left unedited to win the recognition prize. Up to the first ten people with correct solutions are recognized in the next challenge video. The solution to a challenge problem is posted as a separate video the following Wednesday.
    For more Weekly Math Challenges:
    usclip.net/p/PLpoKXj-PWCbaDXYHES37_zX4O-kCWxguM

Comments • 60

  • Ee Poh Ong
    Ee Poh Ong 10 days ago

    I got 110. Don’t ask me how

  • Sonal Kumari
    Sonal Kumari 3 months ago

    My answer is 122
    Consider the following cases for n>3 :-
    Case1: when the series starts with 00 it must end with 00
    This can be done in 2^(n-4) ways
    Case2: when the series starts with any of 01 or 10 or 11 then it must end with any of 01 or 10 or 11(not necessary respectively). This can be done in 3×3×2^(n-4)=9×2^(n-4) ways.
    Therefore no of ways for n>3 is 2^(n-4)+9×2^(n-4)= 10×2^(n-4) =5×2^(n-3) ways
    By hit and trial we can find that
    a_1=2
    a_2=4
    a_3=6
    Therefore total no of ways= 2+4+6+ 5(2^1 + 2^2 +...+2^9) =5122.
    Therefore the req ans is 122.

  • Serengeti Ghasa
    Serengeti Ghasa 3 months ago

    Wow what a super challenge I m till working on it the answer is 692
    I was confused to take zero times occurrence of 001and 100
    Up to a₄ the possible nos are 0,1,00,01,10,11,000,010,011,101,
    110,111,1001,1010,1011,0101,1101,0110,1110,0111,1111 the sum is 7032
    For a₅ to a₁₂
    if the last digit are 001,010,011,101,110 and 111 then the left two place must be 01,10 and 11 so the occurrence of these nos would be 3 time of
    2⁷+2⁶+2⁵+2⁴+2³+2²+2¹+2⁰=255
    I.e. 765
    So by summing these nos we found 765(001+010+011+101+110+111)
    =765×344= 263160 the last three digit is 160
    For nos ending with 100 the last two place must be 00 so the possibility is
    2⁷+2⁶+2⁵+2⁴+2³+2²+2¹+2⁰=255
    The sum bring 255×100 =25500
    The last three digit 500
    So adding all those we get
    032+160+500=792
    So the answer is 792
    With love and regards
    Prabhat

  • Serengeti Ghasa
    Serengeti Ghasa 3 months ago

    Now I fully understand the question the answer is 650
    I was confused to take zero times occurrence of 001and 100 now I m clear.
    Up to a₃ the possible nos are 0,1,00,01,10,11,000,010,011,101,
    110,111 the sum is 366
    For a⁴ to a₁₂
    if the last digit are 001,010,011,101,110 and 111 the in the left two place one place must be occupy by 1 so the occurrence of these nos would be
    2⁸+2⁷+2⁶+2⁵+2⁴+2³+2²+2¹+2⁰=511
    So by summing these nos we found 511(001+010+011+101+110+111)
    =511×344= 175784 the last three digit is 784
    For nos ending with 100 the last two place must be 00 so the possibility is
    2⁷+2⁶+2⁵+2⁴+2³+2²+2¹+2⁰=255
    The sum bring 255×100 =25500
    The last three digit 500
    So adding all those we get
    366+784+500=1650
    So the answer is 650
    With love and regards
    Prabhat

  • Pete Berg
    Pete Berg 3 months ago

    Summon: Reccurence relations

  • UbuntuLinux
    UbuntuLinux 3 months ago

    Is it allowed to use code to solve this?

  • Jaleb
    Jaleb 3 months ago

    For the first few cases we can count manually:
    a_1 = 2 for cases of 0, and 1.
    a_2 = 4 for 00, 01, 10, 11
    a_3 = 6 as it works for all cases but 001 and 100
    Next for cases where n > 3, make note a_n only counts series in the following forms:
    00....00
    01...10
    01...1
    1...10
    1...1
    Any other acceptable number can be placed into the 5 cases given. Note this is true because 001 and 100 will show up an equal number of times when there is a 1 on either side of a string of 0s. For the case of 00...00 this is not the same case, but will still give an acceptable case no matter how many 1s you place in the rest of the number.

    With this we fill in the ... with any arrangement of 0s or 1s. Thus, we get the following:
    00....00
    having 2^(n-4) solutions
    01...10
    having 2^(n-4) solutions
    01...1
    having 2^(n-3) solutions
    1...10
    having 2^(n-3) solutions
    1...1 having 2^(n-2) solutions
    Adding these solutions gives a_n = 2^(n-1)+2^(n-3)

    Taking the sum of this series gives: a_1 + a_2 + a_3 + sum_4^12 a_n
    = 2+4+6+sum_4^12 (2^(n-1)+2^(n-3)) = 5122.
    Or 122 is our final answer.

  • Nicola C
    Nicola C 3 months ago +3

    The answer is 122.
    Let's write the string in a general form.
    xx...(n-4 digits)xx
    We will examine 3 different cases:
    -the string begins with a 1: then the string can't end with a 00, because every time there is a sequence of 2 or more 0s, before there is a 1, because the sequence starts with a 1 and after it there must be a 1, otherwise the string would have more 100 than 001.
    If it ends with 00 there is one extra 100 and we don't count those.
    The number of these strings is 3*2ⁿ⁻³.
    -the string begins with 01:
    it is the same as before: the first one to appear will be a 100 sequence, whenever a 00 sequence appears, therefore it can't end with 00.
    The number of these sequences is 3*2ⁿ⁻⁴.
    -the string begins with 00:
    this time is the opposite, because the first time a 1 appears, there will be a 001 sequence and after that a 100 if there is a 00 and so on.
    So it must end with 00 this time, otherwise there would be an extra 001.
    The number of this strings is 2ⁿ⁻⁴.
    So
    aₙ=3*2ⁿ⁻³+4*2ⁿ⁻⁴=3*2ⁿ⁻³+2ⁿ⁻².
    We must still calculate a₁,₂,₃ by hand but that's not difficult: they are 2, 4 and 6 respectively.
    So the final answer is 2+4+6+6*511+4*511≡12+110≡122 mod 1000 and we are done.

    • Nicola C
      Nicola C 3 months ago +1

      @Jan Von Schreibe I have downloaded a special keyboard
      (DxMath keybord) on the play store and there are also greek letters and a lot of symbols

    • Jan Von Schreibe
      Jan Von Schreibe 3 months ago

      How do you write exponent and index on USclip ?

  • Daniel Flores
    Daniel Flores 3 months ago +3

    I got 122 after 1 minute of writing some code into matlab, good luck to anyone who is trying to analytically find the solution.

    • Atharva #breakthrough
      Atharva #breakthrough 3 months ago

      hey u got any tips for quickly learning matlab?
      I need it for a class in statistics

  • Serengeti Ghasa
    Serengeti Ghasa 3 months ago

    I think the answer is 268
    At first look I couldn't understand the question . So my first answer was wrong as I m not familiar with string and binary process.
    After doing some combinatory calculation I found as follow
    Last three digit up to a₁₂
    001 is 766 number
    010 is 382 number
    011 is 382 number
    100 is 502 number
    101 is 190 number
    111 is 190 number
    So we (766×1)+(382×10)+(382×11)+ (502×100)+(190×101)+(190×111) =*268
    So I think 268 might be the answer
    With love and regards
    Prabhat Ku Sahu
    Singhijuba S Rampur Sonepure
    Odisha India 767045

  • Allaizn
    Allaizn 3 months ago +1

    I got the sum to be 5122, which means that the questions answer is 122.
    To get this number, I strategically counted all the substrings that fulfill the condition. This is done by first categorizing all binary strings, and then counting all the substrings within the valid categories:
    Note that we almost always can shorten strings by removing 1s or 0s without changing their validity (i.e. valid strings stay valid, invalid strings stay invalid): if the string contains "11", we can remove one of those 1s while maintaining validity. Similarly "000" can be shorten to "00". These two transformations reduce the strings to consider to just those with single 1s, single 0s or double 0s, e.g. "010010101".
    Note that we can furthermore remove 0s if they're not at the very beginning or the very end. Being somewhere in the middle means that we have a "1001" or "101" substring. Removing a zero from the former results in the latter and does not change the validity of the string, since it reduces both the number of "001" & "100" substrings by precisely 1. Removing the 0 from the latter doesn't change the number of "001" or "100" substrings either and is thus also safe to remove. The result is that all internal zeros vanish, and thus only leading and trailing zeros remain, along with multiple 1s in the middle, which can then be collapsed into a single one by the above rules.
    This greatly collapsed the number of categories, and we end up with the following few:
    - "0", "1", "01", "10", "001", "010", "100", "0100", "0010" and "00100"
    Of these, only the following contain valid strings:
    - "0/00", "1", "01", "10", "010" and "00100"
    Given n, we're able to calculate a_n by considering each of these categories individually, and then summing all the amounts to get the final value of a_n:
    - "0/00" always contains exactly 1 element, which is the string of n 0s (it's actually two categories under the above rules: "0" & "00", but we can easily collapse them since only one of them can be non-empty for a fixed n)
    - "1" contains all strings starting and ending with a 1. Note that all such strings are valid: the above rules are bidirectional, and it's clear that we're allowed to add both 1s and 0s however we like. The number of such substrings is 2^(n-2) for n>=2 and 1 for n=1.
    - "01" this category constains all strings starting with a "01" and ending with "1". The smallest such string is "01", but "011" is also in it. Starting from "011" it's clear that we can expand into any string (as seen in the "1" category), which means that this category contains all strings of the (n-1)-"1" category prepended with "0". Their number is thus 2^(n-3) for n>=3, 1 for n=2 and 0 for n=1.
    - "10" is similar to "01", but instead of prepending "0", we append "0" instead. Their number is again 2^(n-3) for n>=3, 1 for n=2 and 0 for n=1.
    - "010" follows a similar route, but instead prepend & append a "0" to all (n-2)-"1" strings. Their number is thus 2^(n-4) for n>=4, 1 for n=3 and 0 for n=4 we get the total to be 1 + 2^(n-2)+2^(n-3)+2^(n-3) + 2^(n-4) + 2^(n-4)-1 = 2^(n-4)*(2^2+2^1+2^1+2^0+2^0) = 10*2^(n-4)
    The series of a_n is thus { 2, 4, 6, 10, 20, 40, 80, 160, 320, 640, 1280, 2560, ... } whose first 12 terms sum to 5122, whose last 3 digits are 122

  • Michael Empeigne
    Michael Empeigne 3 months ago

    110

  • Rishav Gupta
    Rishav Gupta 3 months ago +3

    The answer is 122
    The sereis is unbalanced only when either of 2 sides contains 00 for n>3
    Thus the total no of ways in which the string is not good (by IEP)
    =(2^n-2)+(2^n-2)-(2^n-4)-(2^n-4)=(2^n-1)-(2^n-3)
    =(2^n-3)(3)
    Thus total no of good strings of length n are
    (2^n)-(2^n-3)=5×(2^n-3)
    a_1=2
    a_2=4
    a_3=6
    Thus sum=
    5×(2+2^2.......2^9)+12
    =(10×511)+12
    =5110+12
    =5122

  • batman rules
    batman rules 3 months ago

    I am trying to get cases there are three cases of occurrences of the substrings on whether how much they overlap 001 and 100 have spaces between them or 00100 or 1001

  • obese rat
    obese rat 3 months ago

    My answer is 7.69
    I got this by doing something and doing that and getting an answer!

  • mark erena
    mark erena 3 months ago +2

    My awnser is 122.
    a_1=2, a_2= 4, a_3=6 If the leading zeros are counting
    If n>3 I think I found a formula for the number of strings. It's 2^n-4 *10 and the sum evaluates to 10(1+2+2^2+...+2^8)+12= 10(2^9-1)+12= 10(512-1)+12= 10*511+12=5122 Thus 122

    • mark erena
      mark erena 3 months ago +1

      @Sudheer Thunga I'm sorry... But don't give up

    • Sudheer Thunga
      Sudheer Thunga 3 months ago

      @mark erena I am very sorry my solution is wrong😭😭

    • mark erena
      mark erena 3 months ago

      @Sudheer Thunga how did you aproach it?

    • Sudheer Thunga
      Sudheer Thunga 3 months ago

      Dude..I got a_5 as 15

  • Sudheer Thunga
    Sudheer Thunga 3 months ago

    First off..let's try out some parts
    So,
    a_1=2(You see 0 and 1 both have 0 substrings of 001 and 100)
    Doing some trial and error,
    I found out,
    a_1=2
    a_2=4
    a_3=6
    a_4=10
    a_5=15
    Now anybody would understand the sequence...It is the triangular numbers
    So let me define it for n>2 ,
    a_n=(n(n+1))/2
    So adding all the numbers I get
    (1+3+6+...78) +2
    So using the formula for sum of n triangular numbers.=n(n+1)(n+2)/6
    I get the answer to be 366
    So the required answer was the last three digits to be 366

    • Sudheer Thunga
      Sudheer Thunga 3 months ago

      This is wrong...but I don't want to delete it ,so people don't make the same mistakes like this

  • alonamaloh
    alonamaloh 3 months ago

    The sum is 5122, so the answer is "122". I computed the sum with this C++ code using g++:

    #include
    unsigned num001(unsigned x, unsigned n) {
    unsigned not_x = x ^ ((1u 2) & (not_x >> 1) & x;
    return __builtin_popcountl(matches);
    }
    unsigned num100(unsigned x, unsigned n) {
    unsigned not_x = x ^ ((1u 2) & (not_x >> 1) & not_x;
    return __builtin_popcountl(matches);
    }
    unsigned a(unsigned n) {
    unsigned count = 0;
    for (unsigned x = 0, end = 1u

    • alonamaloh
      alonamaloh 3 months ago +1

      @LetsSolveMathProblems Oh, sure. If you have never used C or C++, this program can be quite daunting.

      The section called `main' simply adds up a(1)+a(2)+...+a(12) and prints the result. The section called `a' loops over the numbers 0, 1, ..., (2^n)-1, which is an enumeration of all strings of length n if you interpret them in base 2, and it counts for how many of them the number of instances of "001" is equal to the number of instances of "100". Those two quantities are defined in the sections called "num001" and "num100" respectively, which work almost identically and are written in a tricky way. I'll describe how `num100' works, and the other one is analogous. I take the input number x and I define not_x to be the number you obtain when you flip the lowest n bits (ones become zeros and zeros become ones). Now I use the operator `>>' to shift these numbers and the operator `&' to select those bits that satisfy the condition "this bit is not set, the bit to my left is not set and the bit two spaces to my left is set". Finally the function `__builtin_popcountl' is something g++ provides to count how many bits satisfy the condition.

      It's a very brute-force approach to the problem, and I should have thought of Serengeti Ghasa's solution. But given how small the problem is, I knew this program would run very quickly, so I just took this as a bit-manipulation programming challenge.

    • LetsSolveMathProblems
      LetsSolveMathProblems  3 months ago

      I personally do not know C++. Could you post a short description of the algorithm(s) you used in the program?

  • Sudheer Thunga
    Sudheer Thunga 3 months ago +1

    This is such a cool problem..!!

  • Erin Cobb
    Erin Cobb 3 months ago

    073
    I'm assuming substrings can overlap, that is if A=#001 and B=#100, then 1001 has A=B=1. Further, I'm assuming binary strings must start with 1 (unless it's a string of length 1,which may be a single 0).
    Given these conditions, the only way that strings can become unbalanced is if the last two digits are 0. In that case, there's a 100 without a matched 001.
    So, a_1 is a special case, since it can have a single 0. So, a_1=2, a_2=2, a_n=3*2^(n-1)/4=3*2^(n-3)
    Let i=n-3
    4+3*sum_i=0^9(2^n)=4+3*1023=3073
    So 073?

    • Erin Cobb
      Erin Cobb 3 months ago

      The way I counted the cases, if strings must start with 1, they have the form 1...xx where xx=00 fails, and xx=01,10,11 succeed so 3/4. If strings may start with 0, they have the form xx...xx. Where 1000,0100,1100,0011,0010,0001 fail and the other 10 succeed, 10/16=5/8.

    • Erin Cobb
      Erin Cobb 3 months ago

      If the strings can start with 0, then they are unbalanced if one side xor the other starts with 00. For that, you'd get a_1=2,a_2=4,a_n=5*2^n/8=5*2^(n-3)
      4+5*1023=5119
      So 119

  • mark erena
    mark erena 3 months ago

    My awnser is 117.
    a_1=2, a_2= 2, a_3=3
    If n>3 I think I found a formula for the number of strings. It's 2^n-4 *10 and the sum evaluates to 10(1+2+2^2+...+2^8)+7
    7= 10(2^9-1)+7= 10(512-1)+7= 10*511+7=5117 Thus 117

    • LetsSolveMathProblems
      LetsSolveMathProblems  3 months ago +2

      Yes! =)

    • Sudheer Thunga
      Sudheer Thunga 3 months ago +2

      @LetsSolveMathProblems a_3=6

    • Sudheer Thunga
      Sudheer Thunga 3 months ago

      @LetsSolveMathProblems Now I understand what is required!!!!😁😁

    • LetsSolveMathProblems
      LetsSolveMathProblems  3 months ago +1

      a_3 is actually not 0 because, for example, 101 satisfies our requirement. 101 contains zero 100 and zero 001, so it contains the same number of 100 and 001 (zero = zero). As for your second question, the answer is yes: 00100 is considered part of a_5 because it contains the same number of 100 and 001 (namely, one of each).

    • Sudheer Thunga
      Sudheer Thunga 3 months ago

      @LetsSolveMathProblems And my last and final confirmation is 00100 considered part of a_5

  • Benjamin Wang
    Benjamin Wang 3 months ago +1

    Actually now that I’ve thought about it, it’s much more complicated than I had originally envisaged. The expressions I’m working with are not nice, and it’s 2a.m now. Here’s my idea:
    Let b_n = the number of binary strings of length n = 2^n
    Let A = the substring 001, B = 100.
    Let s_n,k = strings of length n that have exactly k A’s and k B’s as substrings
    We want the sum of s_k, clearly only need to consider 0

  • attyfarbuckle
    attyfarbuckle 3 months ago +4

    My guess is 122:
    Define a clump of zeros to be any group of 2 or more.
    If an integer b has m distinct clumps of zeros then there are m occurrences of 100 unless b begins with 00, in which case there are m - 1.
    So for 12 digit numbers there are 2560 counting strings, because either both ends are 00 or neither.
    n-digit numbers have 10*2^(n - 4) for n ≥ 4.
    Adding these up gives 10*511 + 6 + 4 + 2.
    Hence the answer.

  • mark erena
    mark erena 3 months ago

    The sum evaluates to 425.333
    The number of posibile binary strings that contain equally many times 001 and 100 is (n^2-1)*2/3 because it can not start with 001 so the sum evaluates to 2*638/3= 425.3333

    • mark erena
      mark erena 3 months ago +2

      Ok, thank you. I'll correct it

    • LetsSolveMathProblems
      LetsSolveMathProblems  3 months ago +3

      The sum should be a positive integer because every a_n is a positive integer.

  • LetsSolveMathProblems
    LetsSolveMathProblems  3 months ago +4

    * This video was reuploaded because the previous version contained a confusing problem statement that used "consecutive substrings" to denote "substrings" (even though the word "substring" by itself already implies consecutiveness). The reupload occurred before any correct solutions were posted.

    • Serengeti Ghasa
      Serengeti Ghasa 3 months ago

      Dear let's solve maths problem Sir,
      I m extremely sorry to delete my first comment. Before giving my answer I read about string and substring in Wikipedia as this is a new concept for me because I was a Art's student 20 year ago. After giving my first answer something strike in my mind that I couldn't generalize the proper methods . Then I gave my 2nd comment but accidentally deleted the 1st comment.
      With love and regards

    • LetsSolveMathProblems
      LetsSolveMathProblems  3 months ago +1

      @Cobalt314 It does not. On the other hand, "0001" and "1001" contain "001" as a substring.

    • Cobalt314
      Cobalt314 3 months ago +1

      A clarification question: does 1 contain 001 as a substring?