# 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:

• Ee Poh Ong 10 days ago

I got 110. Don’t ask me how

• Sonal Kumari 3 months ago

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 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
With love and regards
Prabhat

• 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
With love and regards
Prabhat

• Pete Berg 3 months ago

Summon: Reccurence relations

• UbuntuLinux 3 months ago

Is it allowed to use code to solve this?

• 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 3 months ago +3

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 3 months ago +1

(DxMath keybord) on the play store and there are also greek letters and a lot of symbols

• Jan Von Schreibe 3 months ago

How do you write exponent and index on USclip ?

• 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 3 months ago

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

• 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 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 3 months ago

110

• Rishav Gupta 3 months ago +3

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 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 3 months ago

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

• 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 3 months ago +1

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

• Sudheer Thunga 3 months ago

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

• mark erena 3 months ago

@Sudheer Thunga how did you aproach it?

• Sudheer Thunga 3 months ago

Dude..I got a_5 as 15

• 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 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 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 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  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 3 months ago +1

This is such a cool problem..!!

• 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 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 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 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  3 months ago +2

Yes! =)

• Sudheer Thunga 3 months ago +2

@LetsSolveMathProblems a_3=6

• Sudheer Thunga 3 months ago

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

• 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 3 months ago

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

• 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 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.

• 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 3 months ago +2

Ok, thank you. I'll correct it

• LetsSolveMathProblems  3 months ago +3

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

• 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 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  3 months ago +1

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

• Cobalt314 3 months ago +1

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