Puzzle
9 minute read

Ponder This Challenge - November 2004 - Sum of numbers after worm ate some

Ponder This Challenge:

Puzzle for November 2004

This month's puzzle again comes from IQSTAR.
One or both parts can be solved.

Part 1:
The numbers 1 to 9999 (decimal base) were written on a paper. Then the paper was partially eaten by worms. It happened that just those parts of paper with digit "0" were eaten. Consequently the numbers 1200 and 3450 appear as 12 and 345 respectively, whilst the number 6078 appears as two separate numbers 6 and 78. What is the sum of the numbers appearing on the worm-eaten paper?

Part 2:
Suppose the numbers are represented in the base b system. The digits are 0,1,2,3,...,a, where numerically "a" is equal to b-1. The first b^n-1 numbers, 1 through aaa...a, (that is, the last number is an n-digit number with all its digits
equal to "a") were written on a paper. Then it happened that just those parts of paper with the digits "0", "1", ..., "x-1" were worm-eaten (i.e. the remaining numbers consist of digits belong to {"x", "x+1", ..., "a"}, and suppose 0<x<a). For example, in Part 1 we have b=10, a=9, n=4 and x=1. What is the sum of the numbers appearing on the worm-eaten paper in terms of b, n and x?

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

  • ANSWER:

    Part 1:
    37359000

    Part 2:
    Let T_n be the sum of the remaining numbers on the worm-eaten paper; T_0 is defined to be 0.
    d denotes a digit which may be any one of "0","1","2","3",...,"a".
    e denotes a digit which may be any one of "0","1",...,"x-1".
    f denotes a digit which may be any one of "x","x+1",...,"a".
    [ffff] denotes a 4-digit number all of whose digits belong to
    {"x","x+1",...,"a"}, etc.
    c is the mean value of x,...,a, so that c = (b+x-1)/2.
    S_n be the sum of all the n-digit numbers of the form [fff...f].
    It is not difficult to see that S_n = (b-x)^n*c*(b^n-1)/(b-1).
    S_0 is defined to be 0.
    We write y=b-x to simplify the expression.
    Thus S_n = y^n*c*(b^n-1)/(b-1).

    We divide the n-digit numbers into n+1 classes according to the position of the leading e digit.
    Class C_1: [edd...dd]
    Class C_2: [fed...dd]
    Class C_3: [ffe...dd]
    ...
    Class C_(n-1): [fff...ed]
    Class C_n: [fff...fe]
    Class C_(n+1): [fff...ff]
    There are y^(i-1)*x*b^(n-i) different numbers in Class C_i for i in
    {1,...,n}. C_(n+1) has y^n different numbers.

    After worm-eating, all the e digits are gone. The sum of numbers in C_i appearing on the worm-eaten paper is
    x*b^(n-i)*S_(i-1) + y^(i-1)*x*T_(n-i)
    for i in {1,...,n}.
    The sum of numbers in C_(n+1) appearing on the worm-eaten paper is S_n.
    Thus T_n = S_n + sum{i,1,n}{x*b^(n-i)*S_(i-1)} + sum{i,1,n}{y^(i-1)*x*T_(n-i)}

    Let U_n = S_n + sum{i,1,n}{x*b^(n-i)*S_(i-1)} for n>0 and define U_0 = 0.
    We have U_(n+1)-b*U_n = S_(n+1)+x*S_n-b*S_n = S_(n+1)-y*S_n

    S_(n+1)-y*S_n
    = y^(n+1)*c*(b^(n+1)-1)/(b-1) - y^(n+1)*c*(b^n-1)/(b-1)
    = y^(n+1)*c*b^n

    From the basic knowledge about difference equation,
    U_n = c*b^(n-1)*(y^(n+1)-y)/(y-1).

    Similarly
    T_n = U_n + sum{i,1,n}{y^(i-1)*x*T_(n-i)}
    = U_n + sum{i,0,n-1}{y^(n-1-i)*x*T_i}
    T_(n+1)-y*T_n = U_(n+1)+x*T_n-y*U_n
    T_(n+1)-b*T_n = U_(n+1)-y*U_n

    Substitute U_n into this difference equation, we have
    T_n = b^n*(G*y^n + H*n + K)
    where G = c*(b-1)*y^2/(b*(y-1))^2, and the other two coefficients H and K are to be determined by T_0=0 and T_1=S_1=c*y.

    To be explicit, T_n = b^n*(G*y^n + ((c*y/b)-(y-1)G)*n - G)

    If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

  • Part 1 (None)
  • Raicho Tchalkov (11.01.2004 @11:16:18 AM EST)
  • Daniel Wood (11.01.2004 @12:22:01 PM EST)
  • Colin Bell (11.01.2004 @01:19:07 PM EST)
  • Joseph DeVincentis (11.01.2004 @01:44:26 PM EST)
  • Kalyana Chakravarthy (11.01.2004 @02:30:07 PM EST)
  • s (11.01.2004 @02:30:07 PM EST)
  • Mike Rousse (11.01.2004 @05:29:50 PM EST)
  • Trapti Dixit (11.01.2004 @06:47:38 PM EST)
  • Nirmal Balaraman (11.01.2004 @07:50:04 PM EST)
  • Vineet Batra (11.02.2004 @01:00:55 AM EST)
  • Vincent Vermaut (11.02.2004 @02:27:40 AM EST)
  • Gyora (11.02.2004 @04:08:02 AM EST)
  • Benedek (11.02.2004 @04:08:02 AM EST)
  • Satish (11.02.2004 @08:58:16 AM EST)
  • Vedantam (11.02.2004 @08:58:16 AM EST)
  • Dan Dima (11.02.2004 @09:14:13 AM EST)
  • Eugene Vasilchenko (11.02.2004 @10:30:05 AM EST)
  • Markus Nauroth (11.02.2004 @12:01:19 PM EST)
  • Ari (11.02.2004 @02:56:08 PM EST)
  • Radu Grigore (11.02.2004 @03:13:16 PM EST)
  • Gyozo Nagy (11.02.2004 @03:25:35 PM EST)
  • Daniel H. Li (11.02.2004 @04:29:53 PM EST)
  • Naga Thogiti (11.02.2004 @09:25:44 PM EST)
  • Siva Dirisala (11.02.2004 @09:58:27 PM EST)
  • Daniel Voina (11.03.2004 @03:59:13 AM EST)
  • Clive Tong (11.03.2004 @09:51:14 AM EST)
  • Vineet Dwivedi (11.03.2004 @11:48:28 AM EST)
  • Shiva P Kasiviswanathan (11.03.2004 @01:54:25 PM EST)
  • Vinay Mallikarjun Igure (11.03.2004 @03:25:16 PM EST)
  • Jose H. Nieto (11.03.2004 @05:44:13 PM EST)
  • Alexis G. Megas (11.03.2004 @06:18:59 PM EST)
  • Paul Cleary (11.03.2004 @07:58:00 PM EST)
  • Allan Lazarovici (11.03.2004 @08:23:27 PM EST)
  • Phil Lazarovici (11.03.2004 @10:10:24 PM EST)
  • Kim Se Kwon (11.03.2004 @11:52:26 PM EST)
  • Amit Kumar (11.04.2004 @02:32:45 AM EST)
  • Vince Lynch (11.04.2004 @10:25:47 AM EST)
  • Vasudev Nayak (11.04.2004 @12:25:00 PM EST)
  • Vamsidhar Sunkari (11.04.2004 @01:16:00 PM EST)
  • Frank Mullin (11.04.2004 @04:56:54 PM EST)
  • Divyesh Dixit (11.04.2004 @06:07:12 PM EST)
  • John Konglathu (11.04.2004 @06:19:54 PM EST)
  • Vamsi Dhar (11.04.2004 @11:07:13 PM EST)
  • Nikhil Sahasrabudhe (11.05.2004 @11:23:58 AM EST)
  • Atul Kumar Gupta (11.05.2004 @01:16:51 AM EST)
  • Dharmadeep Muppalla (11.05.2004 @01:42:33 AM EST)
  • Troy Lee (11.05.2004 @02:39:14 PM EST)
  • Gerald Harrison (11.05.2004 @07:29:45 AM EST)
  • Gaurav Agrawal (11.06.2004 @05:16:51 PM EST)
  • Bhimasankar Raju Potturi (11.06.2004 @10:45:52 PM EST)
  • Abishek Kumarasubramanian (11.07.2004 @01:35:07 PM EST)
  • Paul Botham (11.07.2004 @02:13:47 PM EST)
  • Princess Melany (11.07.2004 @02:35:50 PM EST)
  • Indrajit Mukherjee (11.07.2004 @03:48:45 PM EST)
  • Patrick J. LoPresti (11.07.2004 @08:10:07 PM EST)
  • Prasanta Babu Jashti (11.08.2004 @05:22:24 AM EST)
  • Biju Mohan (11.08.2004 @06:22:37 AM EST)
  • Joseph R Chadwick (11.08.2004 @12:32:50 PM EST)
  • Yong Liu (11.08.2004 @04:26:19 PM EST)
  • David Auclair (11.08.2004 @04:28:32 PM EST)
  • Enrique Velazquez (11.08.2004 @05:03:59 PM EST)
  • Udhay Kumar (11.09.2004 @12:32:14 AM EST)
  • Patrick Coleman (11.09.2004 @03:29:00 AM EST)
  • Prakash Sachania (11.09.2004 @04:40:30 AM EST)
  • Ajay Reddy Mallepally (11.09.2004 @06:09:57 AM EST)
  • Rick Sprague (11.09.2004 @02:33:35 PM EST)
  • Masta Kuno (11.09.2004 @07:25:02 PM EST)
  • Mark Iuzzolino (11.09.2004 @08:28:41 PM EST)
  • Samantha Casanova (11.10.2004 @03:59:33 PM EST)
  • Usman Tahir (11.11.2004 @11:25:27 AM EST)
  • Praveen Kumar J (11.11.2004 @01:21:00 PM EST)
  • Joaquim Carrapa (11.11.2004 @03:29:34 PM EST)
  • John Ritson (11.11.2004 @04:41:53 PM EST)
  • David Friedman (11.11.2004 @06:41:07 PM EST)
  • Jeff Shute (11.12.2004 @01:35:31 AM EST)
  • Michael Brand (11.12.2004 @02:23:01 AM EST)
  • Daniel Chong Jyh Tar (11.12.2004 @12:53:38 PM EST)
  • Guler Amos (11.14.2004 @03:01:14 AM EST)
  • Alexandru Sofronia (11.14.2004 @12:50:51 PM EST)
  • Richard A Bauer (11.14.2004 @04:03:03 PM EST)
  • Taku Tamagawa (11.14.2004 @06:09:49 PM EST)
  • Kennedy (11.15.2004 @01:46:47 AM EST)
  • Nick Matelli (11.15.2004 @03:04:51 AM EST)
  • Melvin Carvalho & (11.15.2004 @09:53:00 AM EST)
  • Andrew Nubbert (11.15.2004 @09:53:00 AM EST)
  • Chauncey Zheng (11.15.2004 @10:22:42 PM EST)
  • Thomas Rast (11.16.2004 @04:58:08 PM EST)
  • Lakshaman Parihar (11.17.2004 @05:44:23 AM EST)
  • Kalyan Chakravarthy Gudimella (11.17.2004 @08:20:23 AM EST)
  • David Cavanagh (11.17.2004 @09:55:04 AM EST)
  • Claudio Baiocchi (11.17.2004 @10:30:13 AM EST)
  • Scott Miller (11.17.2004 @01:25:00 PM EST)
  • Wills Accad (11.17.2004 @02:56:20 PM EST)
  • Chu-Wee Lim (11.17.2004 @04:29:20 PM EST)
  • Tadej Svetek (11.18.2004 @04:27:07 AM EST)
  • Max Alekseyev (11.18.2004 @07:26:23 AM EST)
  • Forrest McClellan (11.18.2004 @04:12:27 PM EST)
  • George Chen (11.18.2004 @04:37:28 PM EST)
  • Hari Sethuraman (11.18.2004 @06:11:07 PM EST)
  • Tang Ming Fai (11.19.2004 @06:08:02 AM EST)
  • Narayana Babu (11.19.2004 @06:11:18 AM EST)
  • Alan O'Donnell (11.19.2004 @08:48:19 AM EST)
  • Krishna Kumar (11.19.2004 @08:59:31 AM EST)
  • Robin Abraham (11.19.2004 @09:37:56 PM EST)
  • Alex Skorin (11.21.2004 @10:27:22 AM EST)
  • Alex T (11.21.2004 @01:33:36 AM EST)
  • ikhonov (11.21.2004 @01:33:36 AM EST)
  • Lishchenko Yury (11.21.2004 @03:24:00 AM EST)
  • Souvik Bose (11.21.2004 @11:40:59 PM EST)
  • Muharrem Gorkem (11.22.2004 @03:47:56 AM EST)
  • Owen Wright (11.22.2004 @08:03:39 AM EST)
  • Logan Ingalls (11.22.2004 @09:06:27 AM EST)
  • Uday Kale (11.22.2004 @01:00:18 PM EST)
  • Harsha (11.22.2004 @03:03:36 PM EST)
  • Raul Guiu (11.22.2004 @08:53:31 PM EST)
  • Michael Brundage (11.23.2004 @03:35:08 AM EST)
  • Ashutosh Sodhani (11.23.2004 @03:49:01 AM EST)
  • Alok Panigrahy (11.23.2004 @05:36:58 AM EST)
  • Dmitry Chmyr (11.23.2004 @08:32:54 AM EST)
  • Victor Espigares (11.23.2004 @08:20:35 AM EST)
  • Dion K Harmon (11.24.2004 @02:57:32 AM EST)
  • Yuyah (11.24.2004 @04:38:31 AM EST)
  • Ananda Raidu (11.24.2004 @07:12:37 AM EST)
  • Franco Bassi (11.24.2004 @05:55:00 PM EST)
  • Mark Pilloff (11.25.2004 @08:52:27 AM EST)
  • Jinhong (11.25.2004 @09:38:40 AM EST)
  • Kim (11.25.2004 @09:38:40 AM EST)
  • Tony Lin (11.25.2004 @12:43:59 PM EST)
  • Paul Vandenkeybus (11.26.2004 @06:40:43 AM EST)
  • Arun (11.26.2004 @07:13:05 AM EST)
  • John G. Fletcher (11.26.2004 @11:04:18 AM EST)
  • Rico Blaser (11.26.2004 @11:49:13 AM EST)
  • Fakrudeen Ali Ahmed (11.26.2004 @01:46:40 AM EST)
  • Himanshu Dhar (11.26.2004 @02:03:13 PM EST)
  • Hassan Masum (11.26.2004 @02:52:50 PM EST)
  • Mark J Murphy (11.27.2004 @09:55:28 PM EST)
  • Rubén Hernández Aza (11.28.2004 @11:07:57 AM EST)
  • Roger Duthie (11.28.2004 @11:59:37 AM EST)
  • Jeremy McNamara (11.29.2004 @10:38:00 AM EST)
  • Animesh Shrivastava (11.29.2004 @12:44:16 AM EST)
  • R. Nandakumar (11.29.2004 @09:22:41 AM EST)
  • Boris Silantev (11.29.2004 @11:58:24 AM EST)
  • Thomas Russo (11.29.2004 @12:29:21 PM EST)
  • Don Rice (11.29.2004 @06:03:00 PM EST)
  • Nitin Gupta (11.30.2004 @12:55:26 AM EST)
  • Alex McKale (11.30.2004 @02:03:12 AM EST)
  • Gangadhar NPK (11.30.2004 @06:44:05 AM EST)
  • Bert Fischer (11.30.2004 @07:39:17 AM EST)
  • Rethnakaran Pulikkoonattu (11.30.2004 @07:54:51 AM EST)
  • Aditya Utturwar (11.30.2004 @10:41:50 AM EST)
  • Emile Joubert (11.30.2004 @01:29:11 PM EST)
  • Mike Sebastian (11.30.2004 @03:59:10 PM EST)
  • Aaron Prenot (11.30.2004 @03:59:33 PM EST)
  • Reejis Stephen (11.30.2004 @09:44:00 PM EST)
  • Bill Webb (11.30.2004 @11:13:24 PM EST)
  • Vishal Mamania (12.01.2004 @06:59:41 AM EST)
  • Part 2 (None)
  • Colin Bell (11.01.2004 @01:19:07 PM EST)
  • Joseph DeVincentis (11.01.2004 @01:44:26 PM EST)
  • Raicho Tchalkov (11.01.2004 @03:33:54 PM EST)
  • Eugene Vasilchenko (11.02.2004 @10:30:05 AM EST)
  • Ari (11.02.2004 @02:56:08 PM EST)
  • Siva Dirisala (11.02.2004 @09:58:27 PM EST)
  • Vincent Vermaut (11.03.2004 @06:57:37 AM EST)
  • Dan Dima (11.03.2004 @08:08:32 AM EST)
  • Vineet Dwivedi (11.03.2004 @11:48:28 AM EST)
  • Jose H. Nieto (11.03.2004 @05:44:13 PM EST)
  • Kim Se Kwon (11.03.2004 @11:52:26 PM EST)
  • Daniel H. Li (11.04.2004 @03:09:12 AM EST)
  • Frank Mullin (11.04.2004 @04:56:54 PM EST)
  • Divyesh Dixit (11.04.2004 @06:07:12 PM EST)
  • Dharmadeep Muppalla (11.05.2004 @01:42:33 AM EST)
  • Troy Lee (11.05.2004 @02:39:14 PM EST)
  • Radu Grigore (11.05.2004 @03:03:30 PM EST)
  • Nirmal Balaraman (11.05.2004 @05:52:34 PM EST)
  • Bhimasankar Raju Potturi (11.06.2004 @10:45:52 PM EST)
  • Patrick J. LoPresti (11.07.2004 @08:10:07 PM EST)
  • Allan Lazarovici (11.08.2004 @06:44:52 PM EST)
  • Patrick Coleman (11.09.2004 @03:29:00 AM EST)
  • David Friedman (11.11.2004 @06:41:07 PM EST)
  • Jeff Shute (11.12.2004 @01:35:31 AM EST)
  • Michael Brand (11.12.2004 @02:23:01 AM EST)
  • Praveen Kumar J (11.13.2004 @04:02:02 PM EST)
  • Alexandru Sofronia (11.14.2004 @12:50:51 PM EST)
  • Kennedy (11.15.2004 @01:46:47 AM EST)
  • Chauncey Zheng (11.15.2004 @10:22:42 PM EST)
  • Thomas Rast (11.16.2004 @04:58:08 PM EST)
  • Claudio Baiocchi (11.17.2004 @10:30:13 AM EST)
  • Chu-Wee Lim (11.17.2004 @04:29:20 PM EST)
  • Max Alekseyev (11.18.2004 @07:26:23 AM EST)
  • Forrest McClellan (11.18.2004 @04:12:27 PM EST)
  • Alex Tikhonov (11.21.2004 @01:33:36 AM EST)
  • Daniel Chong Jyh Tar (11.21.2004 @04:08:26 AM EST)
  • Muharrem Gorkem (11.22.2004 @03:47:56 AM EST)
  • Franco Bassi (11.22.2004 @05:15:08 PM EST)
  • Alan O'Donnell (11.23.2004 @09:51:00 AM EST)
  • Dion K Harmon (11.24.2004 @02:57:32 AM EST)
  • Ananda Raidu (11.24.2004 @07:12:37 AM EST)
  • George Chen (11.24.2004 @11:46:27 AM EST)
  • Mark Pilloff (11.25.2004 @08:52:27 AM EST)
  • Jinhong (11.25.2004 @09:38:40 AM EST)
  • Kim (11.25.2004 @09:38:40 AM EST)
  • Fakrudeen Ali Ahmed (11.26.2004 @01:46:40 AM EST)
  • John G. Fletcher (11.26.2004 @11:04:18 AM EST)
  • Rubén Hernández Aza (11.28.2004 @11:07:57 AM EST)
  • Roger Duthie (11.28.2004 @11:59:37 AM EST)
  • R. Nandakumar (11.29.2004 @09:22:41 AM EST)
  • Boris Silantev (11.29.2004 @11:58:24 AM EST)
  • Thomas Russo (11.29.2004 @12:29:21 PM EST)
  • Bert Fischer (11.30.2004 @07:39:17 AM EST)
  • Harsha (11.30.2004 @07:16:43 AM EST)
  • Emile Joubert (11.30.2004 @01:29:11 PM EST)

Related posts