Sunny 1,000 Collection

home *** CD-ROM | disk | FTP | other *** search

/ Sunny 1,000 Collection / SUNNY1000.iso / Files / Dos / Boardak / INETPUZ.ZIP / INDUCTIO.TXT < prev next >

Wrap

Text File | 1995-02-05 | 16KB | 396 lines

Archive-name: puzzles/archive/induction Last-modified: 17 Aug 1993 Version: 4 ==> induction/handshake.p <== A married couple organizes a party. They only invite other married couples. At least one person of an invited couple is acquainted to at least the host or the hostess (so between sets {host,hostess} and {male of invited couple, female of invited couple} there exists at least one relation, but two, three or four relations is also possible). Upon arrival at the party, each person shakes hands with all other guests he/she doesn't know yet (it is assumed everybody knows him/herself and his/her partner). When all couples have arrived and all the handshaking has been done, the host mingles between the guests and ask everybody (including his wife): "How many hands did you shake?". To his surprise, all responses are different. With the above information, you must be able to determine how many hands the host and hostess each shook. ==> induction/handshake.s <== Assume there were 2n people (including host and hostess) in the party. 1. When the host asked the question he must have got 2n-1 responses (including from his wife). 2. All of the responses were different. The responses have to be (0, 1, 2, 3, ..., 2n-2) to satisfy the above requirements. As 2n-2 is the maximum possible handshakes any person in this party could have made. /** Below, P{x} - means a person who shook x hands. H - means the host **/ H: <-------->2n-2 0 2n-3 1 2n-4 2 2n-5 3 . . . . . . n n-1 n-2 (There are 2n-1 on the circle.) P{2n-2} must have handshaked with H (because in the circle he can handshake with only 2n-3. He has to exclude himself also.) P{2n-3} must have handshaked with H (because in the circle he can handshake with only 2n-4.) P{2n-4} must have handshaked with H (because in the circle he can handshake with only 2n-5.) P{n} must have handshaked with H (because in the circle he can handshake with only n-1.) from P{n-1} to P{0} nobody handshakes with H, because, for them the handshake numbers are satisfied on the circle itself. This leaves H with (n-1) handshakes. ---------------------------------- P{0} must be the spouse of P{2n-2} (since P{2n-2} handshakes with everbody else.) .. .. .. same logic till P{n-2} leaving the Hostess to be P{n-1}. ---------------------------------------- So, Host - made (n-1) handshakes. Hostess - made (n-1) handshakes. where n is the number of couple including the host couple. ---------------------------------------- ==> induction/hanoi.p <== Is there an algorithm for solving the Hanoi tower puzzle for any number of towers? Is there an equation for determining the minimum number of moves required to solve it, given a variable number of disks and towers? ==> induction/hanoi.s <== The best way of thinking of the Towers of Hanoi problem is inductively. To move n disks from post 1 to post 2, first move (n-1) disks from post 1 to post 3, then move disk n from post 1 to post 2, then move (n-1) disks from post 3 to post 2 (same procedure as moving (n-1) disks from post 1 to post 3). In order to figure out how to move (n-1) disks from post 1 to post 3, first move (n-2) disks . . . . As far as an algorithm which straightens out any legal position is concerned, the algorithm would go something like this: 1. Find the smallest disk. Call the post that it's on post 1. 2. Find the smallest disk which is not on post 1. This disk is, say, size k. (I am calling the smallest disk size 1 here.) Call the post that disk k is on post 2. Disks 1 through (k-1) are then all stacked up correctly on post 1 disk k is on top of post 2. This follow from the fact that the disks are in a legal postition. 3. Move disks 1 through (k-1) from post 1 to post 2, ignoring the other disks. This is just the standard Tower of Hanoi problem for (k-1) disks. 4. If the disks are not yet correctly arranged, repeat from step 1. In fact, this gives the straightening with the fewest number of moves. With 3 towers, for N number of disks, the formula for the minimum number of moves to complete the puzzle correctly is: (2^N) - 1 This bit of ancient folklore was invented by De Parville in 1884. ``In the great temple at Benares, says he, beneath the dome which marks the centre of the world, rests a brass plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty-four discs of pure gold, the largest disc resting on the brass plate, and the others getting smaller and smaller up to the top one. This is the Tower of Bramah. Day and night unceasingly the priests transfer the discs from one diamond needle to another according to the fixed and immutable laws of Bramah, which require that the priest on duty must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. When the sixty-four discs shall have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple, and Brahmins alike will crumble into dust, and with a thunderclap the world will vanish.'' (W W R Ball, MATHEMATICAL RECREATIONS AND ESSAYS, p. 304) This has been discussed by several authors, e.g. Er, Info Sci 42 (1987) 137-141. Graham, Knuth and Patashnik, _Concrete_Mathematics_. There are many papers claiming to solve this, and they are probably all correct but they rely on the unproven "Frame's conjecture". In particular, for the 4 peg case the conjecture states that an optimal solution begins by forming a substack of the k smallest discs, then moving the rest, and then moving those k again; k to be determined. Here is a extensible bc program that does the same work. The output format is not that great. We get 300 numbers as output. The first hundred represent N, the next 100 represent f(N) and the last hundred represent i, which is the number of discs to move to tmp1 using f(N). For convenience, I have here some values for N <= 48. Enjoy. Sharma N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 f(N) 1 3 5 9 13 17 25 33 41 49 65 81 97 113 129 161 193 225 257 i 0 1 1 2 2 3 3 4 5 6 6 7 8 9 10 10 11 12 13 N 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 f(N) 289 321 385 449 513 577 641 705 769 897 1025 1153 1281 1409 1537 1665 i 14 15 15 16 17 18 19 20 21 21 22 23 24 25 26 27 N 36 37 38 39 40 41 42 43 44 45 46 47 48 f(N) 1793 2049 2305 2561 2817 3073 3329 3585 3841 4097 4609 5121 5633 i 28 28 29 30 31 32 33 34 35 36 36 37 38 /* This is the bc program that gives f(N) for 4 peg case */ w = 101; /* This represents the number of disks */ m[0] = 0; m[1] = 1; m[2] = 3; m[3] = 5; m[4] = 9; m[5] = 13; m[6] = 17; /* f(n) is the function that gives the min # of moves for 4 peg case */ define f(n) { return (m[n]); } /* g(n) is the function that fives the min # of moves for 3 peg case */ define g(n) { return (2^n - 1); } /* x(n) is the Optimization Routine */ define x(n) { auto j auto r auto i if(n == 1) return (1); j = f(1) + g(n-1); for(i = 2; i < n; i++) { r = f(i) + g(n-i); if(r < j) { j = r; d = i; } } return (j); } /* main program */ for(q = 4; q < w; q++) { t = x(q-1); m[q] = 2 * t + 1; d[q] = d; }; /*This for loop prints the number of discs from 1 <= n <= w*/ for(q = 1; q < w; q++) { q; } /*This for loop prints f(n) for 1 <= n <= w */ for(q = 1; q < w; q++) { m[q]; } /*This for loop prints i for 1 <= n <= w i represents the number of disks to be moved to tmp location using f(n) N-i-1 will be moved using g(n) */ for(q = 1; q < w; q++) { d[q]; } -- sharma@sharma.warren.mentorg.com There is a solution to the Tower of Hanoi problem which does not require recursion. On odd-numbered moves, move the smallest sized disk clockwise. On even-numbered moves, make the single other move which is possible. ==> induction/n-sphere.p <== With what odds do three random points on an n-sphere form an acute triangle? ==> induction/n-sphere.s <== Select three points a, b, and c, randomly with respect to the surface of an n-sphere. These three points determine a fourth, x, which is the intersection of the sphere with the axis perpendicular to the abc plane. (Choose the pole nearest the plane.) I could have, just as easily, selected x, a distance d from x, and three points d units away from x. The distribution of d is not uniform, but that's ok. For every x and d, the three points abc form an acute triangle with probability p[n-1]. By induction, p[n] = 1/4. ==> induction/paradox.p <== Is there a non-trivial property that holds for the first 10,000 positive integers, then fails? ==> induction/paradox.s <== Consider the sequences defined by: s(1) = a; s(2) = b; s(n) = least integer such that s(n)/s(n-1) > s(n-1)/s(n-2). In other words, s(n) = 1+floor(s(n-1)^2/s(n-2)) for n >= 3. These sequences are similar in some ways to the classically-studied Pisot sequences. For example, if a = 1, b = 2, then we get the odd-indexed Fibonacci numbers. D. Boyd of UBC, an expert in Pisot sequences, pointed out the following. If we let a = 8, b = 55 in the definition above, then the resulting sequence s(n) appears to satisfy the following linear recurrence of order 4: s(n) = 6s(n-1) + 7s(n-2) - 5s(n-3) - 6s(n-4) Indeed, it does satisfy this linear recurrence for the first 11,056 terms. However, it fails at the 11,057th term! And s(11057) is a 9270 digit number. (The reason for this coincidence depends on a remarkable fact about the absolute values of the roots of the polynomial x^4 - 6x^3 - 7x^2 + 5x + 6.) ==> induction/party.p <== You're at a party. Any two (different) people at the party have exactly one friend in common (the friend is also at the party). Prove that there is at least one person at the party who is a friend of everyone else. Assume that the friendship relation is symmetric and not reflexive. ==> induction/party.s <== Here is an easy solution by induction. Let P be the set of people in the party, and n the size of P. If n=2 or 3, the result is trivial. Suppose now that n>3 and that the result is true for n-1. For any two distinct x,y in P, write x & y to mean that `x is a friend of y', and x ~& y to mean that `x is not a friend of y'. Take q in P. The hypothesis on the relation & is still satisfied on P-{q}; by induction, the result is thus true for P-{q}, and there is some p in P-{q} such that p & x for any x in P-{p,q}. We have two cases: a) p & q. Then the result holds for P with p. b) p ~& q. By hypothesis, there is a unique r in P-{p,q} such that p & r & q. For any x in P-{p,q}, if x & q, then p & x & q, and so x=r. Thus r is the unique friend of q. Now for any s in P-{q,r} there exists some x such that s & x & q, and so x=r. This means that r & s for any s in P-{q,r}, and as r & q, the results holds in P with r. The problem can also be solved by applying the spectral theory of graphs (see for instance Bollobas' excellent book, _Extremal Graph Theory_). The problem's condition is vacuous if there is only N=1 person at the "party", impossible if N=2 (If you aren't your own friend, nor I mine, somebody *else* must be our mutual friend), and trivial if N=3 (everybody must be everyone else's friend). Henceforth assume N>3. Let A,B be two friends, and C their mutual friend. Let a be the number of A's friends other than B and C, and likewise b,c. Each of A's friends is also friendly with exactly one other of A's friends, and with none of B and C's other friends (if A1,B1 are friends of A,B resp. and of each other then A1 and B have more than one mutual friend); likewise for B and C. Let M=N-(a+b+c+3) be the number of people not friendly with any of A,B,C. Each of them is friendly with exactly one of A's and one of B's friends; and each pair of a friend of A and a friend of B must have exactly one of them as a mutual friend. Thus M=ab; likewise M=ab=ac=bc. Thus either M and two of a,b,c vanish, or a=b=c=k (say), M=k^2, and N=k^3+3k+3. In the first case, say b=c=0; necessarily a is even, and A is a friend of everybody else at the party, each of whom is friendly with exactly one other person; clearly any such configuration (a graph of k/2+1 triangles with a common vertex) satisfies the problem's conditions). It remains to show that the second case is impossible. Since N=k^2+3k+3 does not depend on A,B,C, neither does k, and it quickly follows that the party's friendship graph is regular with reduced matrix [ 0 k+2 0 ] [ 1 1 k ] [ 0 1 k+1 ] and eigenvalues k+2 and +-sqrt(k+1) and multiplicities 1,m1,m2 for some *integers* m1 and m2 such that (m1-m2)*sqrt(k+1)=-(k+2) (because the graph's matrix has trace zero). Thus sqrt(k+1) divides k+2 and k+1 divides (k+2)^2=(k+1)(k+3)+1 which is only possible if k=0, Q.E.D. ==> induction/roll.p <== An ordinary die is thrown until the running total of the throws first exceeds 12. What is the most likely final total that will be obtained? ==> induction/roll.s <== Claim: If you throw a die until the running total exceeds n>=5, a final outcome of n+1 is more likely than any other. Assume we throw an m for a total n+k>n+1, and assume m-k>=0. Now, it is just as likely to throw an m as an m-k+1, which means that the sum n+1 is just as likely as any other. Now consider the series of throws consisting of n-5 1's followed by a 6 and note that we cannot achieve more than an n+1 by changing the last die roll. Hence, a total of n+1 is more likely than any other. ==> induction/takeover.p <== After graduating from college, you have taken an important managing position in the prestigious financial firm of "Mary and Lee". You are responsible for all the decisions concerning take-over bids. Your immediate concern is whether to take over "Financial Data". There is no doubt that you will be successful if you are the first to bid and that this will be profitable for the firm and you in the long run. However, you know that there exist another n financial firms, similar to "Mary and Lee", that are also considering the possibility. Although you are likely to be the first one to move, you know that just after a take-over there is a lot of adjustment that needs to be done. In fact, for a period of time following any take-over the successful firm becomes a prime candidate for a take-over which will cost the job of whoever is responsible for take-overs. Among all financial firms it is common knowledge that the managers responsible for take-overs are rational and intelligent. What is your best response? ==> induction/takeover.s <== Assume the takeover is wise for n. The takeover is then unwise for n+1, as the other companies now find themselves in the same situation as you for n. If the decision is unwise for n, by similar reasoning it is wise to takeover FD for n+1. Now note that for n=1 the takeover decision is clearly unwise, hence by induction you should takeover FD iff n is even.