• Non ci sono risultati.

Find the numberxn of bit strings of lengthn in which the number of 00 substrings is equal to the number of11 substrings

N/A
N/A
Protected

Academic year: 2021

Condividi "Find the numberxn of bit strings of lengthn in which the number of 00 substrings is equal to the number of11 substrings"

Copied!
1
0
0

Testo completo

(1)

Problem 11424

(American Mathematical Monthly, Vol.116, March 2009) Proposed by E. Deutsch (USA).

Find the numberxn of bit strings of lengthn in which the number of 00 substrings is equal to the number of11 substrings.

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

A bit strings of length n is an ordered collection of 1 ≤ m ≤ n blocks each of length br+ 1 ≥ 1 of consecutive 0’s and 1’s alternated. Hence

m

X

r=1

br= n − m.

Since that the number of 00 substrings in a string of br+ 1 consecutive 0’s is equal to br, in order to compute xn we have to count two times (the first block can be of 0’s or 1’s) the number of non-negative integers solutions of

⌈m/2⌉

X

j=1

b2j−1=

⌊m/2⌋

X

j=1

b2j= n − m 2 where (n − m)/2 is an integer. Therefore

xn= 2 X n − m even

(n − m)/2 + ⌈m/2⌉ − 1

⌈m/2⌉ − 1

(n − m)/2 + ⌊m/2⌋ − 1

⌊m/2⌋ − 1



= 2

 n − 2

⌊n/2⌋ − 1

 .



Riferimenti

Documenti correlati

This paper reports an experimental study of transient natural convection heat and mass transfer between two large cylindrical reservoirs connected through a short

Two families of non-overlapping coercive domain decomposition methods are proposed for the numerical approximation of advection dominated advection-di usion equations and

[r]

For positive integer n and i ∈ {0, 1}, let D i (n) be the number of derangements on n elements whose number of cycles has the same parity

[r]

To drill a cube is to partition it into 27 congruent subcubes and remove the closed central cube along with the 6 remaining subcubes sharing a face with that cube, resulting in a

[r]

For every layer the algorithm determines the best species tree structure, by comparing the number of crossing in the default conguration with the number of crossings after