91Ó°ÊÓ

Let \(a, b \in \mathbf{Z}^{+}\)where \(a \geq b\). Prove that \(\operatorname{gcd}(a, b)=\) \(\operatorname{gcd}(a-b, b)\)

a) Consider an \(8 \times 8\) chessboard. It contains sixty-four \(1 \times 1\) squares and one \(8 \times 8\) square. How many \(2 \times 2\) squares does it contain? How many \(3 \times 3\) squares? How many squares in total? b) Now consider an \(n \times n\) chessboard for some fixed \(n \in \mathbf{Z}^{+} .\)For \(1 \leq k \leq n\), how many \(k \times k\) squares are contained in this chessboard? How many squares in total?

Prove that for all \(n \in \mathbf{Z}^{+}, n>4 \Rightarrow n^{2}<2^{n}\).

For all \(n \in \mathbf{Z}^{+}\), prove that \(n\) is a perfect square if and only if \(n\) has an odd number of positive divisors.

Give a recursive definition for the set of all a) positive even integers b) nonnegative even integers

a) How many positive integers can we express as a product of nine primes (repetitions allowed and order not relevant) where the primes may be chosen from \(\\{2,3,5,7,11\\}\) ? b) How many of the positive integers in part (a) have at least one occurrence of each of the five primes?

Find the product of all (positive) divisors of (a) 1000 ; (b) 5000; (c) 7000; (d) 9000; (e) \(p^{m} q^{n}\), where \(p, q\) are distinct primes and \(m, n \in \mathbf{Z}^{+} ;\)and (f) \(p^{m} q^{n} r^{k}\), where \(p, q, r\) are distinct primes and \(m, n, k \in \mathbf{Z}^{+}\)

Consider the permutations of \(1,2,3,4\). The permutation 1432, for instance, is said to have one ascent - namely, 14 (since \(1<4)\). This same permutation also has two descents namely, 43 (since \(4>3)\) and 32 (since \(3>2\) ). The permutation 1423 , on the other hand, has two ascents, at 14 and 23 - and the one descent 42 . a) How many permutations of \(1,2,3\) have \(k\) ascents, for \(k=0,1,2 ?\) b) How many permutations of \(1,2,3,4\) have \(k\) ascents, for \(k=0,1,2,3 ?\) d) Suppose a permutation of \(1,2,3, \ldots, m\) has \(k\) ascents, for \(0 \leq k \leq m-1\). How many descents does the permutation have? e) Consider the permutation \(p=12436587\). This permutation of \(1,2,3, \ldots, 8\) has four ascents. In how many of the nine locations (at the start, end, or between two numbers) in \(p\) can we place 9 so that the result is a permutation of \(1,2,3, \ldots, 8,9\) with (i) four ascents; (ii) five ascents? f) Let \(\pi_{m, k}\) denote the number of permutations of \(1,2,3\), \(\ldots, m\) with \(k\) ascents. Note how \(\pi_{4,2}=11=2(4)+\) \(3(1)=(4-2) \pi_{3,1}+(2+1) \pi_{3,2} .\) How is \(\pi_{m, k}\) related to \(\pi_{m-1, k-1}\) and \(\pi_{m-1, k}\) ? c) If a permutation of \(1,2,3,4,5,6,7\) has four ascents, how many descents does it have?

a) Ten students enter a locker room that contains 10 lockers. The first student opens all the lockers. The second student changes the status (from closed to open, or vice versa) of every other locker, starting with the second locker. The third student then changes the status of every third locker, starting at the third locker. In general, for \(1

Write each of the following integers in two's complement representation. Here the results are eight-bit patterns. a) 15 b) \(-15\) c) 100 d) \(-65\) e) 127 f) \(-128\)