==> pickover/pickover.01.s <== 1) 0 1 2 3 4 5 6 7 8 9 2) 6 2 1 0 0 0 1 0 0 0 3) 0 0 0 4 4 4 0 4 4 4 4) 6 6 6 0 0 0 6 0 0 0 5) 0 0 0 4 4 4 0 4 4 4 . . . and so on, repeating rows 3 and 4. I don't know yet whether there are multiple solutions, but I'll keep looking. Mark Hayes Goddard Space Flight Center (GSFC) / Interferometrics, Inc. mwh@gemini.gsfc.nasa.gov GSFC Code 926.9 Greenbelt, MD 20771 ------------------------- In article <1992Sep14.133741.34561@watson.ibm.com>, you write: |> The puzzle I saw there can be stated as follows. In the 10 boxes below, |> write a 10-digit number. The digit in the first box indicates the total |> number of zeros in the entire number. The box marked "1" indicates the |> total number of 1's in the number. The box marked "2" indicates the |> total number of 2's in the number, and so on. For example, the "3" in |> the box labeled "0" would indicate that there must be exactly three 0's |> in the 10-digit number. |> |> ------------------------------- |> | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| |> | 3| | | | | | | | | | |> ------------------------------- |> |> |> Stop And Think |> |> 1. Is there a solution to this problem? Are there many solutions to this |> problem? This is an old puzzle, but I'll solve it as if it was new because I find your extension below to be interesting. Since all possible digits must be "counted" once, the ten digits must add up to 10. Consider the first digit (= the amount of zeroes used): 9: Impossible, since all the other digits would have to be zero. 8: Also impossible, since we must mark a 1 under the 8, and the other digits then must be zeroes. 7: We must mark a 1 under the 7, and we have one more non-zero digit to assign. We've used a 1, so we must put a non-zero digit under the 1. However, if we put a 1 there, it's wrong because we've used two ones, and if we put a two that's also wrong. So 7 zeroes doesn't work. 6: Begin as before, putting a 1 under the 6. Now we must mark under the 1, but putting a 1 is wrong, so put a 2. Now we have one non-zero digit left to assign, and marking a 1 under the two works. 6210001000 works. 5: Now we take a different approach to analyze this. If there are only five zeroes, then there are five non-zeroes, one of which is the 5 we marked under the zero. Obviously a 1 must be marked under the 5 and zeroes under 6-9, so we have 5----10000, where the dashes contain one zero and three other numbers, which must add up to four (since all ten digits must add up to ten) - so we have two ones and a two. But then the digits we have are described by 5310010000, which is not the set of digits we have, so there is no solution. Similar proofs show that there cannot be 4,3,2, or 1 zero. 0: Impossible, since you would have to use a zero to indicate you didn't have a zero. |> 2. A more advanced an interesting problem is to continue to |> generate a sequence in a recursive fashion such that each row becomes |> the sequence for the previous. For example, start with the usual |> 0 through 9 digits in row 1: |> |> Row 1: 0 1 2 3 4 5 6 7 8 9 |> |> Assume Row 2 is your solution to the puzzle. I've just inserted random |> digits below so as not to give away the solution: |> |> |> Row 1: 0 1 2 3 4 5 6 7 8 9 S(1) |> Row 2: 9 3 2 3 3 1 6 7 8 9 S(2) |> Row 3: S(3) |> |> Row 2 is now the starting point, and your next job is to form row 3, row 4, |> etc. using the same rules. In the previous example, a digit in the |> first box would indicate how many 9's there are in the next 10-digit number, |> and so forth. |> |> Contest: I am looking for the longest sequence of numbers users can come |> up with using these rules. Can you find a Row 2 or Row 3? |> Is it even possible to generate a "row 2" or "row 3"? Well, first off, our handy rule about all the digits adding up to ten no longer applies. Let's see if we can find an answer: Row 1: 0 1 2 3 4 5 6 7 8 9 Row 2: 6 2 1 0 0 0 1 0 0 0 Row 3: ? All the same digits must be placed under all the zeroes in row 2, or some of them would be wrong, and this digit cannot be larger than 4 since six non-zeroes are used under the zeroes in row 2. So, consider the cases: 4: If we put 4's under all the zeroes, we must put zeroes everywhere else. 0004440444 works. 3: Now we must place one non-zero digit under either the 6 or the 2, since there are two 1's that must stay alike. Putting any non-zero digit under the 6 is wrong since there aren't any sixes, unless you put a 6 under the 6, which is still wrong. Similarly no digit works under the two. 2: Now we must put a non-zero digit under the 2, since we already used 6 of them. We must also have two zeroes, which can only go under the ones. This gives us --02220222. However, we must put a non-zero under the 6, and we can't put a one, since we must have zeroes under the ones. Any number greater than one is wrong, because we don't have that many 6's. 1: OK, we start with ---111-111, and one of the -'s must be a zero. This zero must go under the 2 or the 6, because the ones must be alike (and we've already used some ones). Suppose we put 6's under the ones, and don't use any more ones. Then we need a 2 under the 6, and we need a one under the 2, which breaks what we did before. So, instead put 7's under the ones. Now we must put a 1 and a 0 in the other two spots, but either arrangement is wrong. We can't put a higher number under the ones because there aren't enough spaces left, so there is no solution with 1 zero. 0: Self-contradiction, as in the original problem. So now we have a unique third row. Can we make a fourth? Row 1: 0 1 2 3 4 5 6 7 8 9 Row 2: 6 2 1 0 0 0 1 0 0 0 Row 3: 0 0 0 4 4 4 0 4 4 4 Now there can only be two different digits used in the next number. Consider the possibilities: No zero is used: We need to mark this by putting zeroes under the zeroes Self-contradiction. Some zeroes are used: They can't go under the zeroes, so put zeroes under the fours. Now six zeroes are used, so put 6's under the zeroes. 6660006000 works. The same logic used to find row four shows that row five must be 0004440444 again, and we get into an infinite cycle alternating between these two. -- ----w-w--------------Joseph De Vincentis--jwd2@owlnet.rice.edu---------------- ( ^ ) Disclaimer: My opinions do not represent those of Owlnet. (O O) Owlnet: George R. Brown School of Engineering Educational Network. v-v (Unauthorized use is prohibited.) (Being uwop-ap!sdn is allowed.) Snail mail: Rice U., 6100 S. Main, Houston TX 77005. ------------------------- In rec.puzzles you write: >Title: Cliff Puzzle 1: Can you beat the numbers game? >From: cliff@watson.ibm.com [...] >1. Is there a solution to this problem? Are there many solutions to this >problem? Yes. No. >2. A more advanced an interesting problem is to continue to >generate a sequence in a recursive fashion such that each row becomes >the sequence for the previous. For example, start with the usual >0 through 9 digits in row 1: [...] >Contest: I am looking for the longest sequence of numbers users can come >up with using these rules. Can you find a Row 2 or Row 3? >Is it even possible to generate a "row 2" or "row 3"? My program produces the following output: 0123456789 6210001000 no solutions found So I believe that the result for row 2 is unique and that there is no result for row 3. [ I am including the program at the end of this message just for your interest ] >If you respond to this puzzle, if possible please include your name, >address, affiliation, e-mail address. If you like, tell me a little bit >about yourself. You might also directly mail me a copy of your response >in addition to any responding you do in the newsgroup. I will assume it >is OK to describe your answer in any article or publication I may write >in the future, with attribution to you, unless you state otherwise. >Thanks, Cliff Pickover The name, address etc should appear in my signature. As for myself, I'm a PhD student due to finish much too shortly who likes solving puzzles. Pauli Paul Dale | grue@cs.uq.oz.au Department of Computer Science | +61 7 365 2445 University of Queensland | Australia, 4072 | Did you know that there are 41 two letter | words containing the letter 'a'? The program I used follows: --------------------------------------8<------------------------------ #include #include #define START(in) for(in=0;in<9;in++) { \ if(sum+in > 10) \ break; \ else \ sum = sum+in; \ counts[digits[in]]++; #define STOP(in) counts[digits[in]]--; \ sum -= in; \ } main() { short counts[10]; short i, sum; short i0,i1,i2,i3,i4,i5,i6,i7,i8,i9; static short digits[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; short solns[10][100]; short solcnt=0; printf("0123456789\n"); again: for(i=0;i<10;i++) counts[i]=0; sum = 0; START(i0) START(i1) START(i2) START(i3) START(i4) START(i5) START(i6) START(i7) START(i8) START(i9) if(counts[0]==digits[i0] && counts[1]==digits[i1] && counts[2]==digits[i2] && counts[3]==digits[i3] && counts[4]==digits[i4] && counts[5]==digits[i5] && counts[6]==digits[i6] && counts[7]==digits[i7] && counts[8]==digits[i8] && counts[9]==digits[i9]) { printf("%d%d%d%d%d%d%d%d%d%d\n", i0,i1,i2,i3,i4,i5, i6,i7,i8,i9); for(i=0;i<10;i++) solns[0][solcnt] = i0; solns[1][solcnt] = i1; solns[2][solcnt] = i2; solns[3][solcnt] = i3; solns[4][solcnt] = i4; solns[5][solcnt] = i5; solns[6][solcnt] = i6; solns[7][solcnt] = i7; solns[8][solcnt] = i8; solns[9][solcnt] = i9; solcnt++; } STOP(i9) STOP(i8) STOP(i7) STOP(i6) STOP(i5) STOP(i4) STOP(i3) STOP(i2) STOP(i1) STOP(i0) if(solcnt == 0) { printf("no solutions found\n"); } else if(solcnt == 1) { for(i=0;i<10;i++) digits[i] = solns[i][0]; solcnt = 0; goto again; } else printf("multiple solutions found\n"); } --------------------------------------8<------------------------------ ------------------------- In article <1992Sep14.133741.34561@watson.ibm.com> you write: >Title: Cliff Puzzle 1: Can you beat the numbers game? >From: cliff@watson.ibm.com > >If you respond to this puzzle, if possible please include your name, >address, affiliation, e-mail address. If you like, tell me a little bit >about yourself. You might also directly mail me a copy of your response >in addition to any responding you do in the newsgroup. I will assume it >is OK to describe your answer in any article or publication I may write >in the future, with attribution to you, unless you state otherwise. >Thanks, Cliff Pickover > >* * * >At a recent trip to the Ontario Science Center in Toronto, Canada I came >across an interesting puzzle. The center is located minutes from >downtown Toronto and it's a vast playground of science with hundreds of >exhibits inviting you to touch, try, test, and titillate your curiosity. >The puzzle I saw there can be stated as follows. In the 10 boxes below, >write a 10-digit number. The digit in the first box indicates the total >number of zeros in the entire number. The box marked "1" indicates the >total number of 1's in the number. The box marked "2" indicates the >total number of 2's in the number, and so on. For example, the "3" in >the box labeled "0" would indicate that there must be exactly three 0's >in the 10-digit number. > >------------------------------- >| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| >| 3| | | | | | | | | | >------------------------------- > > >Stop And Think > >1. Is there a solution to this problem? Are there many solutions to this >problem? A. Since there are ten digits in the number, the sum of the digits in the bottom row must be 10. B. If x appears under y there must be x appearences of y, hence x*y<10 So, the MAXIMUM that can appear under each number is: --------------------- |0|1|2|3|4|5|6|7|8|9| |9|9|4|3|2|1|1|1|1|1| max --------------------- C. In fact, under the numbers 5..9 there can be AT MOST one non-zero (1) answer since otherwise two numbers of the 5..9 veriaty would appear and violate rule A. D. So there must be at least 4 zeros. If there were exactly 4 zeros, then the numbers 1..4 will all have under them non-zeros (as the zeros are used up for the 5..9 group). There is also at least one number that is 5 or greater. Well, there is a 5 (or more), a 4 (under zero), a 1 (under the 5..9 category) and something above zero under the other 1..4 digits for a total above 10. This violates rule A. E. So there must be at least 5 zeros. So a (exactly one) number that is at least 5 has a 1 under it. (since under zero would appear a >=5 number). F. Under 1 there must be at least 1 since the solution has at least one 1 (the one under a 5..9 number). However it could not be exactly 1 as then there would be 2 (or more) 1's in the solution. G. If there were 3 or more ones, then they must be under 2..9 . But then there would be a 5 (or more) under zero + a 3 (or more) under one + a 1 under three (or more) other places for a total above 10. H. So there must be at exactly 2 ones in the solution. And hence, at least 1 under two. We can summerize: --------------------- |0|1|2|3|4|5|6|7|8|9| |5|2|1|0|0|----1----| min |6|2|2|1|1|----1----| max --------------------- where the maximum under each digit is 10 - SUM(minimum of all others) I. Since no 3 or 4 is now possible, those two numbers must have a zero under them. J. So there are six zeros. Hence: --------------------- |0|1|2|3|4|5|6|7|8|9| |6|2|1|0|0|0|1|0|0|0| min |6|2|2|0|0|0|1|0|0|0| max --------------------- K. Notice that "min" is a solution, while "max" is not. Hence, "min is the *ONLY* solution! My name is Dan Shoham. This is the only fact about me I care to make public. You are free to attribute it, but provide me a note when you do so. shoham@ll.mit.edu ------------------------- >From clong@romulus.rutgers.edu (Chris Long) Tue Sep 15 06:08:45 1992 Path: igor.rutgers.edu!romulus.rutgers.edu!clong From: clong@romulus.rutgers.edu (Chris Long) Newsgroups: rec.puzzles Subject: Re: Puzzle 1 (SPOILER) Message-ID: Date: 15 Sep 92 10:08:45 GMT References: <1992Sep14.133741.34561@watson.ibm.com> <1992Sep15.052438.12478@questrel.com> Organization: Rutgers Univ., New Brunswick, N.J. Lines: 62 In article <1992Sep15.052438.12478@questrel.com>, Chris Cole writes: Chris, don't forget to include my name on my solutions in the FAQ, please. My old article should be replaced with the following in the FAQ, anyway: --Cut here-- Solution prepared by Chris Long. Unfortunately, this isn't completely new, since I believe a similar puzzle I posted and answered are in the FAQ. However, it *is* different enough to be interesting. In article <1992Mar3.164702.428@hls.com>, ravi@hls.com writes: > Here's a small number puzzle : > Generate numbers such that the each digit in the number specifies > the number of the occurences of the position of the digit ( postions starting > with 0 from the left ). Example > The number 1210 ... My guess is only: 1210 21200 3211000 42101000 521001000 6210001000 No 1, 2, or 3 digit numbers are possible. Letting x_i be the ith digit, starting with 0, we see that (1) x_0 + ... + x_n = n+1 and (2) 0*x_0 + ... + n*x_n = n+1, where n+1 is the number of digits. I'll first prove that x_0 > n-3 if n>4. Assume not, then this implies that at least four of the x_i with i>0 are non-zero. But then we would have \sum_i i*x_i >= 10 by (2), impossible unless n=9, but it isn't possible in this case (51111100000 isn't valid). Now I'll prove that x_0 < n-1. x_0 clearly can't equal n; assume x_0 = n-1 ==> x_{n-1} = 1 by (2) if n>3. Now only one of the remaining x_i may be non-zero, and we must have that x_0 + ... + x_n = n+1, but since x_0 + x_{n-1} = n ==> the remaining x_i = 1 ==> by (2) that x_2 = 1. But this can't be, since x_{n-1} = 1 ==> x_1>0. Now assuming x_0 = n-2 we conclude that x_{n-2} = 1 by (2) if n>5 ==> x_1 + ... + x_{n-3} + x_{n-1} + x_n = 2 and 1*x_1 + ... + (n-3)*x_{n-3} + (n-1)*x_{n-1} + n*x_n = 3 ==> x_1=1 and x_2=1, contradiction. Case n>5: We have that x_0 = n-3 and if n>=7 ==> x_{n-3}=1 ==> x_1=2 and x_2=1 by (1) and (2). For the case n=6 we see that x_{n-3}=2 leads to an easy contradiction, and we get the same result. The cases n=4,5 are easy enough to handle, and lead to the two solutions above. -- Chris Long, 265 Old York Rd., Bridgewater, NJ 08807-2618 -- Chris Long, 265 Old York Rd., Bridgewater, NJ 08807-2618 ------------------------- The number "2020" was left off my list by mistake ... sorry. -Chris ------------------------- > * * * > At a recent trip to the Ontario Science Center in Toronto, Canada I came > across an interesting puzzle. The center is located minutes from > downtown Toronto and it's a vast playground of science with hundreds of > exhibits inviting you to touch, try, test, and titillate your curiosity. > The puzzle I saw there can be stated as follows. In the 10 boxes below, > write a 10-digit number. The digit in the first box indicates the total > number of zeros in the entire number. The box marked "1" indicates the > total number of 1's in the number. The box marked "2" indicates the > total number of 2's in the number, and so on. For example, the "3" in > the box labeled "0" would indicate that there must be exactly three 0's > in the 10-digit number. > > ------------------------------- > | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| > | 3| | | | | | | | | | > ------------------------------- > > > Stop And Think > > 1. Is there a solution to this problem? Are there many solutions to this > problem? > [Second question and contest problem omitted] Good puzzle! I am wondering though whether the second question (which I have not tried to solve yet) is moe amenable to computer search. It seems to me that there should not be so many cases to consider, so that even exhaustive search should work. So, here is my ten minutes work on the first question. I think there is a unique solution which is: 6210001000. Here is the reasoning. Let the number be (in Tex notation) d_0 d_1 d_2 d_3 d_4 d_5 d_6 d_7 d_8 d_9. By definition d_0 + d_1 + d_2 + d_3 + d_4 + d_5 + d_6 + d_7 + d_8 + d_9 = 10. (1) Moreover, d_0 > 0, since d_0 = 0 contradicts itself. Let d_0 = c for some integer 9 >= c >= 1. If c = 9, then d_9 = 1, contradiction since d_1 should both be 0 and 1 then. If 9 > c >= 1, we rewrite (1) removing all d_i s that are zeros c + d_(i_1) + d_(i_2) + ... + d_(i_(9-c)) = 10 <=> d_(i_1) + d_(i_2) + ... + d_(i_(9-c)) = 10 -c (2) where all the d_(i_j) >= 1, j=1,...,9-c (3) (2) & (3) imply that the d_(i_j)s are 8-c 1s and one 2. Since there exists ONE 2, then there exists at least one 1. So the only digits in the number are 0, 1, 2, and c (if different than 1 and 2). If c is either 1 or 2, we have 3 different digits in the number, which implies d_1 <= 3, impossible since d_1 = 8 - c >= 6. If c> 2, we have four different digits in the number, and in fact d_0 = c, d_1 = 8-c, d_2 = 1, d_c = 1, which leaves us with 6 0s. QED I hope I did not miss any other cases. Do you plan to post answers or comments later? Leonidas -------------------------------------------------------------------------------- Leonidas Palios The Geometry Center 1300 South Second Str palios@geom.umn.edu Minneapolis, Minnesota 55454 ------------------------- ------------------------------- | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| ------------------------------- | 6| 2| 1| 0| 0| 0| 1| 0| 0| 0| | 0| 0| 0| 4| 4| 4| 0| 4| 4| 4| <- | 6| 6| 6| 0| 0| 0| 6| 0| 0| 0| | | 0| 0| 0| 4| 4| 4| 0| 4| 4| 4| <- . . . I must be missing something in my understanding of your rules. I found the second row by imagining that I'd need lots of zeros and putting nine in the 0 column, then skipping back and forth adjusting things. I had to put a tic in the 9 column, then I had to put one in the 1 column, then I realized that had to change that to a two since now there were two ones, and at the same time another required tic in the 2 column balanced the change of one to two in the 1 column, and then of course there weren't nine zeros anymore, but there were still six and so by changing the nine in the 1 column to a six, the one in the 9 column sould just migrate down to the 6 column. But it almost seems like cheating to use fours in the second row when there were none in the second row to necessitate this kind of adjusting. *shrug* If this is right, the series is infinite, obviously. Please let me know if I'm interpreting something wrong. Thanks, and nice puzzle. :) Grant Culbertson grant@minos.nmt.edu dgray@sirius.nmt.edu