• 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
Mostra di più ( pagine)

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

• As ∆ν ∆ν ∆ν ∆ν approaches J, there will be more transitions of similar energy and thus our spectrum will start showing more signals than our simple analysis

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]

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

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

The experimental using CFR engine and using fuel gasoline in the market with blended bioethanol start from 5% -20% and analysis the relationship octane number after

Background and Objectives: Laparoscopic surgical ex- cision of bladder nodules has been demonstrated to be effective in relieving associated painful symptoms; the data are

III anno di corso / I course year (anno accademico / academic year ______2016/2017_____________) DENOMINAZIONE DEL CORSO / NAME OF THE COURSE DURATA / DURATION (in ore / in hours)

Il mio nuovo #romanzo #epicfantasy #Waylock - I principi di Shirien vi aspetta domani alla #libreria #librielibri di #Monza insieme alla #trilogia #urbanfantasy di #oltremondo e

Downloaded from https://academic.oup.com/mnras/article/469/Suppl_2/S550/4103552 by CIS Psicologia Biblioteca F.Metelli - Universita degli Studi di Padova user on 07

You are kindly asked to write, on the other sheet that you received, an integer number between 1 and 100 (extremes included).. I invite you not to discuss among you the choice that

Reduce the equation to canonical form, find the coordinates, with respect to the standard basis of V 2 , of the center/vertex and find the equations/equation of the symmetry

 Design and implement a Kalman filter providing an estimate of the population in each class, by using the input data u(t) and the measurements y(t)..  Plot the obtained estimates

You want to estimate the causal impact of cigarette price (p) and the log of the family income (y) on the smoking behaviour.. The ethnicity dummy variable w (1=white) is a

The biological fact is clear: an active living cell incapable of division can never be immortal, and if it cannot be replaced by other cells, then complex structures such as the

In questo senso, se maggiori evidenze di associazione rispetto ai fattori di sviluppo provengono dalla distinzione tra appartenenti ad un gruppo religioso e

Government Printing Office , Social Security Administration (US)..

Au total, les saints laïcs médiévaux originaires de Venise et vénérés dans cette ville sont peu nombreux – 5 au maximum avec Anna Michiel Giustiniani dont