POTW 2!

The second Problem Of The Week has now been posted, along with an official solution to the first problem. Enjoy!

Comments

  1. #1 JimV
    February 2, 2016

    103 is too easy – there has to be a trick. So the answer must be 1 (with zero positive integers less than 1). I dislike tricks! Life is hard enough without them.

  2. #2 Buddha Buck
    February 2, 2016

    I’m fairly certain it’s 101. 1 is always a factor, the answer has to be greater than 100 (otherwise the number of factors less than it can’t be less than 1%), and 101 is a prime, so 1 is the only factor, with 0.91% of the numbers smaller than it as factors.

  3. #3 JimV
    February 2, 2016

    Further justification for 1 (which might be wrong): the set-up jokes had a calculus theme, and in calculus when you have an indeterminate value (zero positive integers less than 1 which are factors of 1 divided by the number of positive integers less than one, also zero) you look at the limit. The limit of 0/n as n goes to zero is zero.

    Note: the <1% criterion was defined as (no. of +integers less than the number which are its factors) divided by (no. of +integers less than the number, e.g. 60% for the number six. So criterion value for 101 is 1%.

  4. #4 Jason Rosenhouse
    February 2, 2016

    Since there are no positive integers smaller than 1, I’d say 100% of the positive integers smaller than 1 are factors of 1.

    There are exactly 100 positive integers smaller than 101, one of which is a factor of 101. That’s exactly 1%. But the problem called for fewer than 1%.

  5. #5 RickR
    VA
    February 2, 2016

    It’s not 101 because for 101 the number of smaller numbers that divide 101 is exactly 1%, and the statement of the problem requires less than 1%. So it’s the next largest prime, or 103.

  6. #6 JimV
    February 2, 2016

    “Since there are no positive integers smaller than 1, Iā€™d say 100% of the positive integers smaller than 1 are factors of 1.”

    It seems more natural to me to say there are no positive numbers less than one which factor 1, so 0% of them are factors of 1. But it’s not my blog, so I concede defeat. Thanks for the response.

  7. #7 Eric Lund
    February 2, 2016

    The problem with 1 as the solution is precisely because there are no positive integers smaller than 1. That gives you the fraction 0/0, which can take on any value you want: it could be 0, or 1, or even infinity. The problem requires the fraction to have a definite value, so of course the solution has to be the smallest prime greater than 101, or 103.

  8. #8 TC
    February 2, 2016

    Since there are no positive integers less than 1, calculating the desired percentage would require division by zero. The desired percentage does not exist, and therefore cannot be less than 1%.

  9. #9 JimV
    February 2, 2016

    And yet sin(x)/x can be evaluated to be 1 (a definite value) at x=0 using calculus, and many similar evaluations are used in physics and engineering calculations. That was my argument in #3, but it was not acceptable, so I was wrong. Not necessarily due to 0/0 per se, but because in this case there was no limit process that everyone would agree on to reach a definite value.

    A philosopher might say that if there is no definite value then the answer could be anything, and if it could be anything it could be zero (similar to the physics argument “nothingness is unstable”), but I am not a philosopher.

  10. #10 Another Matt
    February 3, 2016

    Is the sinc(x) function evaluated to be 1 at x=0, or is it defined to be 1 because the limit exists and the definition is useful?

  11. #11 JimV
    February 3, 2016

    #10 – both. It can be evaluated for example by using the Taylor Series for sin(x) or by calculating values for a series of small x values and extrapolating them to x=0. The latter process (often used in engineering, e.g., when extrapolating fine-element results to an infinite number of elements by plotting results vs. 1/Ne) was what I had in mind in #3 – 0/3=0%, 0/2=0%, 0/1=0%, … As mentioned in #3, I had doubts (“might be wrong”) that this would be accepted, and it wasn’t. To state for the 3rd time, I was wrong. (Dr. Rosenhouse used the limit series 3/3=100%, 2/2=100%, 1/1=100%, …)

  12. #12 TC
    February 3, 2016

    sin(0)/0, like 0/0, is undefined. F(x)=sin(x)/x has a removable discontinuity at 0. In this problem, taking the limit as n->0 seems inappropriate because n is a discrete variable.

  13. #13 JimV
    February 3, 2016

    And yet several of the limit arguments for 0^0 (zero to the zeroth power) = 1 use discrete values, so this procedure is not unprecedented in mathematics. As I said, I think the difficulty is that there is more than one limit process, and no agreement on which is the most natural.

    (Example: The alternating sum of binomial coefficients from the n-th row of Pascal’s triangle is what you obtain by expanding (1-1)^n using the binomial theorem, i.e., 0^n. But the alternating sum of the entries of every row except the top row is 0, since 0^k=0 for all k greater than 1. But the top row of Pascal’s triangle contains a single 1, so its alternating sum is 1, which supports the notion that (1-1)^0=0^0 if it were defined, should be 1.)

  14. #14 JimV
    February 3, 2016

    Follow-up: note that in the case of 0^0 there are two conflicting limit series: a) 0^3 = 0, 0^2=0, 0^1 =0; and b) 3^0=1, 2^0 =1, 1^0=1 – but in this case, mathematicians have agreed that the latter is more natural.

  15. #15 JimV
    February 3, 2016

    However, if you prefer you could consider the function 0/x, where x is any real number. (Dr. Rosenhouse will counter with the function x/x.)

  16. #16 Eric Lund
    February 3, 2016

    In the case of functions like sin(x)/x, you can evaluate the expression by L’Hopital’s rule: differentiate numerator and denominator, then evaluate at the limit where the original expression gives you 0/0. In this case you get cos(0)/1, which equals 1. A similar method lets you evaluate expressions of the form 0 * infinity, since 1/0 = infinity.

    Arguments involving the binomial theorem need not be discrete mathematics, because the binomial theorem can be generalized to real numbers rather than just integers. You do this by replacing the factorials with equivalent expressions in terms of the gamma function, and accept that the series does not terminate for non-integer values (Γ(x) blows up when x is a non-positive integer, which is how you justify choose(n,k) = 0 when k > n or k < 0).

  17. #17 JimV
    February 3, 2016

    Yes, L’Hopital’s rule is the classic way of evaluating sin(x)/x, although not the only way; and yes, the binomial function can be generalized to real numbers (but this was not done in the above argument for 0^0=1 nor need it be done for that argument). Good points of general interest. I should have mentioned L’Hopital in #11 but wasn’t sure of the spelling and too lazy to search for it.

  18. #18 Sean T
    February 9, 2016

    Took a look at POTW 3 and think I have it. The trick is to realize that (x+1)(X^2+1) = x^3 + x^2 + x +1. Multiplying that expression by (x^4+1) gives Sum(I=0 to 7) x^i. Multiplying that sum by (x^8+1) gives the same sum only with i going from 0 to 15. Finally multiplying by (x^16+1) gives that same sum with i ranging from 0 to 31.

    Of course, the numbers given were just (10^x + 1) with x = 1,2,4,8,and16. Their product therefore is sum (i=0 to 31) 10^i. This, in numerical form is simply a string of 32 1’s, so the sum of the digits is 32.

  19. #19 Another Matt
    February 9, 2016

    The answer to POTW 3 is also 100000, assuming that the final product is the largest representable unsigned int.

  20. #20 Eric Lund
    February 9, 2016

    Sean T has it. The intermediate products are 4, 8, and 16 digit numbers with all digits 1, and the final answer is a 32 digit number with all digits 1. So the sum of the digits is 32. That’s true in any base as long as you convert the representation of 32 to that base.

  21. #21 RickR
    February 9, 2016

    Considering multiplying two numbers “by hand” we see that 11 * 11 = 11+ 110 = 121, and 13 * 12 = 26 + 130 = 156. As long as there are no carries, the sum of the digits in the product is the same as the sum of the sum of the digits in the partial products. Also, with no carries, the sum of the digits in the partial products equals the sum of the digits in the first number times the second number. So the sum of the digits in the product of 11 * 11 = the sum of the digits of the finite in the product of 2 * 11, and the sum of the digits in the product of 13 * 12 = the sum of the digits in the product of 4 * 12. We also note that zeroes can be ignored, since multiplying by 0 adds nothing the the sum of the digits in the product.

    The problem is set up so there are no carries, so the case of carries can be left as an exercise for the reader.

    So the first product is 11 * 101, or the same as 2*11, or 2+20, drop the zero, so the sum of the digits is the same as the sum of the digits of 2+2 = 4. The second product is thus 4 * 11 (we can drop the 0’s since no carries result from doing so), or 4+4 = 8. Continuing in like fashion, we get to the final answer of 32.

  22. #22 RickR
    February 9, 2016

    “the sum of the digits of the finite in the product of 2 * 11”? Should be “final sum of the product”. Sometimes autocorrect does weird things.

  23. #23 Another Matt
    February 9, 2016

    Another way to look at this:

    If I have a number where all the digits are 1 ā€” let’s say 111 ā€” in order to add the same number of zeroes at the end I just multiply by 1 followed by the number of digits in my number. In this case 111*1000 = 111,000. Then if I add my original number, getting 111,111, I will have multiplied by 1001. This will be true no matter the base because of the multiplication by 1s of various magnitudes. In the example the number of digits trailing the leading digit in the multipliers doubles, so the resulting sums will double each time.

    BTW Jason, I love how your lead-ins always give a little hint.

  24. #24 JimV
    February 10, 2016

    POTW 3:

    The product is of the form (10+1)(10^2 +1)(10^4 +1)(10^8 +1), or the product of terms [10^(2^M) +1] for M=0 to 3. In general, for M=0 to N, the product has 2^(N+1) decimal digits, each of which is 1, so their sum is also 2^(N+1). This can be proved by induction by multiplying the product for N {10^[2^(N+1) -1] + 10^[2^(N+1) -2] + … + 10 +1} by {10^[2^(N+1)] +1}.

    For N=3 as in the example, there 2^4 = 16 decimal digits whose sum is 16.

  25. #25 JimV
    February 10, 2016

    Erratum (wrong again!) the problem series went to M=4, not M=3, so the correct answer is 32. I deserve no credit for this as I would hot have re-checked without seeing the previous answers/

  26. #26 JimV
    February 17, 2016

    POTW 4: n=95.

    I reasoned as follows: (n-12)/(5n+23) = rp/sp, where n, p, r, ans s are integers, and p>1 (to make the ratio reducible). Therefore,
    n=rp+12 and 5n+23=sp. Substituting the former into the latter gives 5rp+83=sp, so p must divide 83. The minimum allowable value for p is therefore 83. Then 5r+1 = s, so the minimum values for r and s are 1 and 6. Then n=(1)(83)+12 =95, and

    (n-12)/(5n+23) = 83/498 = r/s = 1/6

New comments have been disabled.