Zonal Informatics Olympiad, 2002, Part A Model Solutions 1. (a) Find the largest disk and flip the top of the stack upto and including this disk. This will take the largest disk to the top of the pile. Then flip the entire stack to get the largest disk to the bottom. At step k+1, inductively the k largest disks are arranged in order at the bottom of the stack. Pick the largest disk above these k disks, flip the stack above this disk to take it to the top and then flip the top n-k disks to bring it to position k+1 from the bottom. (b) Let the disks be numbered 1,2,...,n, where disk 1 is smaller than disk 2 is smaller than ... disk n. In the worst case it takes two flips for each of the disks n, n-1, n-2, ...,3. After disks 3 to n are in the correct position, in the worst case 1 and 2 are inverted so we need one more flip. So, in the worst case, we need 2(n-2)+1 = 2n-3 flips. For 2 disks, the worst case is 2 1 Call this arrangement s2 For 3 disks, the worst case is to get to s2 after 3 comes to the bottom. We would like to take 2 flips to get 3 to the bottom, so, working backwards, 2 3 1 1 <- 1 <- 3 = s3 3 2 2 For 4 disks, we want s1 above 4 after flipping twice to get 4 to the bottom, so s4 is the last sequence of the following 1 4 3 3 <- 2 <- 2 = s4 2 3 4 4 1 1 For k+1 disks, we want sk above disk k+1 after flipping twice to get k to the bottom, so s(k+1) is obtained as follows: (Notation: reading a sequence from top to bottom, head is the top element, tail is the rest, last is the bottom element, init is all but the bottom, flip is a function that inverts a list): sk (k+1) flip (init(flip sk)) = tail sk : <- : <- (k+1) (k+1) (k+1) flip sk last (flip sk) head sk 2. Formally: Conditional probability (Bayes): Pr(A given B) = Pr(A and B) / Pr (B) (a) B is "test is positive", A is "has TB" Pr (A and B) is (80/100)*(10/100) = 8/100 Pr (B) is Pr(yes TB, test positive) + Pr(no TB, test positive) = (10/100)*(80/100) + (90/100)*(20/100) = 26/100 So Pr(A given B) is 8/26 = 4/13 (a) B is "test is negative", A is "has TB" Using similar computation as in (a) Pr (A and B) is 2/100 Pr (B) is 74/100 Pr(A given B) 2/74 = 1/37 Informally: In 100 people, 10 have TB, 90 do not. For the 10 who do, 8 test positive, 2 do not. For the 90 who don't, 18 test positive, 72 do not. (a) 8 of 26 people who test positive have TB (b) 2 of 74 people who test negative have TB 3. Think of one pan as the 'positive' pan and the other as the 'negative' pan. If we put w1 in the positive pan and w2 in the negative pan, the net weight is w1 - w2. Thus, if we use weights w1, w2, ..., wn, we can write out the net weight as a "ternary" n-digit number using digits +1/0/-1. From this, it follows that the optimal set of weights corresponds to powers of 3. (a) 1, 3, 9, 27, 81, 243, 729, 2187, 720 (the last weight is 4000-3280, where 3280 is the sum of the previous 8 weights). (b) In general, we would use 1, 3, 9, ..., log_3(n), n-(1+3+..+log_3(n)) 4. (a) Look at A after rearranging the columns. Consider any pair of adjacent columns k-1 and k. We show that for each row j, A(j,k-1) is smaller than A(j,k). The first entry A(1,k) is bigger than A(1,k-1). This is because A(1,k) dominates at least one entry in column k-1 (the one that was originally to the left of it) and so dominates A(1,k-1), the minimum element in column k-1. Now consider A(2,k). We can argue that A(2,k) dominates at least two entries in column k-1 and hence dominates A(2,k-1), the second smallest entry in column k-1. Suppose A(2,k) dominates only one entry in column k-1 (it dominates at least one, the one originally to its left). Then, the element originally to the left of A(2,k) is the element currently at A(1,k-1). This means that A(1,k) originally had another element A(j,k-1) to its left, not A(1,k-1). But then, A(2,k) > A(1,k) > A(j,k-1) > A(1,k-1), which contradicts the assumption that A(2,k) dominates only one entry in column k-1. In a similar manner, we can show that for each j, A(j,k) dominates at least j entries in column k-1 and so dominates A(j,k-1). Since for each row j and each column k, A(j,k) is bigger than A(j,k-1), it follows that all the rows are still in ascending order. (b)(i) Check k against the top right corner element A(1,n) Case 1: If k is smaller than A(1,n) then k cannot appear in the last column (since A(1,n) is the smallest entry in that column) so we have to search for A in rows 1 to n, columns 1 to n-1. Case 2: If k is bigger than A(1,n) then k cannot appear in the first row (since A(1,n) is the largest entry in that row) so we have to search for A in rows 2 to n, columns 1 to n. In the next step, we check k against the top right corner of the remaining matrix of interest (the top right corner is A(1,n-1) if Case 1 holds and A(2,n) if Case 2 holds) and repeat the earlier analysis. With each step we reduce the matrix of interest by pruning either one row or one column. Since we started with n rows and n columns, within 2n steps (actually 2(n-1) steps) we would have pruned the matrix down to a single row and column, i.e. a single element. (ii) Since the search proceeds from the top right to the bottom left, the search goes on longest if the element is at the bottom left corner, A(n,1). 5. (a) There are two natural methods: The first is to pick up a pair of balls, weigh them, retain the heavier. Then, pick up each of the other balls in turn, weigh them against the current "champion" and retain the heavier one as the new "champion". The ball that remains at the end is the heaviest. The second method is to organize a knockout tournament. Pair up all the balls and retain the heavier one from each pair. Then, pair up the winners of the first round and do the same. Repeat until a single winner is found. Both methods require n-1 weighings. (b) The tournament solution to (a) helps us find the second heaviest ball more efficiently than by naively repeating the procedure for (a). In the overall tournament, the second heaviest ball would have beaten every ball other than the heaviest one. So, we only have to find the heaviest among the log n balls that "lost" to the heaviest ball to find the second heaviest. 6. In each round, the number of black balls can either decrease by 1 (if we pick up black-black or black-white) or increase by 1 (if we pick up white-white) so not much information can be gleaned from analysing the black ball count. However, notice that white balls are eliminated in pairs. Thus, the parity (even/odd) of the white balls in the bag is an invariant. Eventually, we have a single ball (odd). Thus, the last ball is white if only if the bag originally had an odd number of white balls. ======================================================================