# Recurrence, Relations (RR) and Cellular Automata (CA)

Added on - Sep 2019

Showing pages 1 to 2 of 4 pages

Recurrence, Relations (RR) and Cellular Automata(CA)1.Find a RR for the number of ways to climbnstairs if the allowed steps are 1 or 2 staircases.What are the initial conditions for this RR? Solve the problem. In how many ways can oneclimb 50 stairs?2.Find the fix points for the tent map. Theng(x) =aMin(x,1-x),0 ≤x≤1,0 ≤a≤2. Plot thelocation of the right fix point as function ofaandthe derivative there. When is this fix pointstable? Can you find a 2-cyclein the tent map?3.Consider the following 1D CA: A cell is black in next generation if and only if either of itneighbours, but not both, was black on the step before. What is the rule number? Do 5iterations using one black cell as seed.4.Consider the rule B25/S4. B denotes birth and S survival. Game of Life is B3/S23. What is therule number for B25/S4? Do 3 iterations for the first one. Note that we have up-downsymmetry. It is called a replicator. Do one iteration for the second one. It is called a photon.5.Use the inclusion-exclusion (IE) method to calculate the number of integers between 1 and60 that are coprime with 60. The primes 2, 3 and 5 are the prime factors in 60 since 60 = 22·3 · 5. The integers, i, that are coprime with 60 are not divisible with 2, 3 and 5 so GCD(i, 60) =1 for them. GCD stands for greatest common divisor. You can count them directly but hereyou have to use the IE-method.6.The girth of a graph G is the number of edges of the shortest cycle it is possible to find in Gand it is denoted g (G). Let, from now on, the graphs G have e = v + 1 For such graphs with v≥ 4 it is possible to show thatThe floor function [x] gives the largest integer ≤ x.a) Explain why in this type of graphs there must be at least two cycles. Draw a case where the cyclesare edge disjoint for v = 7 and e = 8.b) If the two cycles are edge disjoint what is the maximum girth in a graph with e = v+ 1?c) Draw a graph with maximal girth for v = 7 and e = 8

7.What is the maximal number of edges in a planar graph when the regions have degree 3 ormore? Use for example 2e =Σdeg(Ri) and Euler’s formula.b) Let G be a graph with 11 vertices and let G ̄ be its complement graph. G ̄ has the same 11vertices but the edges from K11that are not edges in G. Use the result in (a) above to showthat not both G and G ̄ can be planar.8.Consider passwords with three symbols. Allowed symbols are the 26 letters in the Englishalphabet and the ten digits 0 to 9. We put the following restrictions on the passwords:i) There must be both letters and digits.ii) There must be both upper- and lower-case letters.So K8k and 4zL are examples of allowed passwords. How many such passwords can beconstructed?9.Let X = {1, 2, 3, 4} and A = X × X. Define a relation R on A by (a, b)R(c, d) if and only if ab = cd.This relation, R, is an equivalence relation. Determine the equivalence classes.10.You have to buy 27 bagels. They are of four types: plain, onion, tomato and blueberry. Therestrictions are: At least three of each sort. Not more than five with onions. In how manyways can you do this?(a) Solve the problem with inclusion-exclusion method.(b) Give the generating function for the problem.11.Consider all the 4-digit numbers from 1000 to 9999.(a) How many of them have a strictly increasing or decreasing sequence? Two examples are3589 (strictly increasing) and 9760 (strictly decreasing). Strictly increasing means next digitto the right is greater than the previous one. Strictly decreasing means next digit to the rightis smaller than the previous one.(b) How many of them have an increasing or decreasing sequence? Two examples are 3556(increasing) and 6661 (decreasing). Increasing means next digit to the right is ≥ the previousone. Decreasing means next digit to the right is ≤ the previous one.12.The odd graph Ok, k is an integer ≥ 2, is defined in the following way:The vertices represent the subsets with k − 1 elements that can be obtained from a set with2k −1 elements. Two vertices are joined with an edge if and only if the correspondingsubsets are disjoint. O2is a triangle so it is isomorphic to C3.(a) Draw O3