This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

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?

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"?

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 <stdio.h> #include <stdlib.h> #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: <Sep.15.06.08.45.1992.9569@romulus.rutgers.edu>

Date: 15 Sep 92 10:08:45 GMT

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

Continue to: