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

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

Ee Poh Ong10 days agoI got 110. Don’t ask me how

Sonal Kumari3 months agoMy 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 Ghasa3 months agoWow 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 Ghasa3 months agoNow 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 Berg3 months agoSummon: Reccurence relations

UbuntuLinux3 months agoIs it allowed to use code to solve this?

Jaleb3 months agoFor 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 C3 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 C3 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 Schreibe3 months agoHow do you write exponent and index on USclip ?

Daniel Flores3 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 #breakthrough3 months agohey u got any tips for quickly learning matlab?

I need it for a class in statistics

Serengeti Ghasa3 months agoI 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

Allaizn3 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 Empeigne3 months ago110

Rishav Gupta3 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

Pranjal Das3 months agoWhat is your study technic?

Rishav Gupta3 months agoInclusion Exclusion Principle

Sudheer Thunga3 months agoWhat is IEP?

batman rules3 months agoI 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 rat3 months agoMy answer is 7.69

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

mark erena3 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 erena3 months ago^{+1}@Sudheer Thunga I'm sorry... But don't give up

Sudheer Thunga3 months ago@mark erena I am very sorry my solution is wrong😭😭

mark erena3 months ago@Sudheer Thunga how did you aproach it?

Sudheer Thunga3 months agoDude..I got a_5 as 15

Sudheer Thunga3 months agoFirst 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 Thunga3 months agoThis is wrong...but I don't want to delete it ,so people don't make the same mistakes like this

alonamaloh3 months agoThe 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

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

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

Sudheer Thunga3 months ago^{+1}This is such a cool problem..!!

Erin Cobb3 months ago073

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 Cobb3 months agoThe 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 Cobb3 months agoIf 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 erena3 months agoMy 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

LetsSolveMathProblems3 months ago^{+2}Yes! =)

Sudheer Thunga3 months ago^{+2}@LetsSolveMathProblems a_3=6

Sudheer Thunga3 months ago@LetsSolveMathProblems Now I understand what is required!!!!😁😁

LetsSolveMathProblems3 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 Thunga3 months ago@LetsSolveMathProblems And my last and final confirmation is 00100 considered part of a_5

Benjamin Wang3 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

attyfarbuckle3 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 erena3 months agoThe 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 erena3 months ago^{+2}Ok, thank you. I'll correct it

LetsSolveMathProblems3 months ago^{+3}The sum should be a positive integer because every a_n is a positive integer.

LetsSolveMathProblems3 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 Ghasa3 months agoDear 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

LetsSolveMathProblems3 months ago^{+1}@Cobalt314 It does not. On the other hand, "0001" and "1001" contain "001" as a substring.

Cobalt3143 months ago^{+1}A clarification question: does 1 contain 001 as a substring?