 # 377 pickover/pickover.01.p

## Description

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.

# 377 pickover/pickover.01.p

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;
short i, sum;
short i0,i1,i2,i3,i4,i5,i6,i7,i8,i9;
static short digits = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
short solns;
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==digits[i0] && counts==digits[i1] && counts==digits[i2] &&
counts==digits[i3] && counts==digits[i4] &&
counts==digits[i5] && counts==digits[i6] &&
counts==digits[i7] && counts==digits[i8] &&
counts==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[solcnt] = i0;
solns[solcnt] = i1;
solns[solcnt] = i2;
solns[solcnt] = i3;
solns[solcnt] = i4;
solns[solcnt] = i5;
solns[solcnt] = i6;
solns[solcnt] = i7;
solns[solcnt] = i8;
solns[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];
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: