MathDB

3

Part of 1998 Argentina National Olympiad

Problems(1)

no of sequences of type 1 is equal to number of sequences of type 2

Source: Argentina 1998 OMA L3 p3

5/13/2024
Given two integers m≥2m\geq 2 and n≥2n\geq 2 we consider two types of sequences of length m⋅nm\cdot n formed exclusively by 00 and 11
TYPE 1 sequences are all those that verify the following two conditions:
∙\bullet akak+m=0a_ka_{k+m} = 0 for all k=1,2,3,...k = 1, 2, 3, ... ∙\bullet If akak+1=1a_ka_{k+1} = 1, then kk is a multiple of mm.
TYPE 2 sequences are all those that verify the following two conditions:
∙\bullet akak+n=0a_ka_{k+n} = 0 for all k=1,2,3,...k = 1, 2, 3, ... ∙\bullet If akak+1=1a_ka_{k+1} = 1, then kk is a multiple of nn.
Prove that the number of sequences of type 1 is equal to the number of sequences of type 2.
combinatoricsnumber theory