Math Puzzles (from FiveThirtyEight - new puzzle every Friday) (1 Viewer)

[matttyl]

Maybe a little bit extra - the question states that there are "bills", as in more than 1 of them.

Question could have been a bit trickier if if they said exactly how many bills there were (possibly 9 as well). 

 

[Ignoratio Elenchi]

New puzzle and solution to last week's.

Suppose a casino invents a new game that you must pay $250 to play. The game works like this: The casino draws random numbers between 0 and 1, from a uniform distribution. It adds them together until their sum is greater than 1, at which time it stops drawing new numbers. You get a payout of $100 each time a new number is drawn.

For example, suppose the casino draws 0.4 and then 0.7. Since the sum is greater than 1, it will stop after these two draws, and you receive $200. If instead it draws 0.2, 0.3, 0.3, and then 0.6, it will stop after the fourth draw and you will receive $400. Given the $250 entrance fee, should you play the game?

Specifically, what is the expected value of your winnings?

[Editor’s note: You know how sometimes your boss/teacher asks you not to bring your laptop to a meeting/class, and you’re all like, “Jeez, how am I gonna tweet during the meeting/class, then?” Well, I’m going to pull rank and ask that you don’t bring laptops to this Riddler. Next week I will highlight — nay, celebrate! — the elegant, pencil-and-paper solutions over the brutal, cold, silicon ones. We’re all on the honor system with one another, right? RIGHT?]

 

[Fred Lane]

Assuming the numbers are to the first decimal, and that 0 and 1 cannont be drawn (only can draw 0.1, 0.2, 0.3, 0.4, 0.5....0.9), my guess is that the expected win is $200.  Since the cost is $250, I would not play...

 

[Ignoratio Elenchi]

Assuming the numbers are to the first decimal, and that 0 and 1 cannont be drawn (only can draw 0.1, 0.2, 0.3, 0.4, 0.5....0.9), my guess is that the expected win is $200.  Since the cost is $250, I would not play...

Well the puzzle isn't limited to the first decimal.  Any number between 0 and 1 can be chosen - 0.5, 1/3, pi/4, 0.999999...., etc.  

I think I know what the answer is, and I do think that you can arrive at the right answer by starting with a simpler case like yours and then seeing what happens as the gap between possible numbers goes to 0.  

 

[Sinn Fein]

Well you have 100% chance of getting $100

Seems like you have a 50% chance of getting the second $100  - so an expected value of $150 to this point.  It would decrease dramatically from here - so I don't see you getting close to even the $200 EV, let alone $250

 

[heckmanm]

Well you have 100% chance of getting $100

Seems like you have a 50% chance of getting the second $100  - so an expected value of $150 to this point.  It would decrease dramatically from here - so I don't see you getting close to even the $200 EV, let alone $250

I think you have 100% chance of getting $200, since you still get paid on the draw that puts the total over 1.0 (again assuming 0 and 1 are excluded from the set).

 

[heckmanm]

Also, if a casino invented the game, the house will win in the long run, so you should not play unless it's entertaining enough to watch yourself lose money.

 

[matttyl]

I think you have 100% chance of getting $200, since you still get paid on the draw that puts the total over 1.0 (again assuming 0 and 1 are excluded from the set).

That's my assumption as well from the wording "between 0 and 1"

 

[Sinn Fein]

I think you have 100% chance of getting $200, since you still get paid on the draw that puts the total over 1.0 (again assuming 0 and 1 are excluded from the set).

Yeah, I missed that detail.

That changes everything...

 

[Sinn Fein]

So you have 100% at $200 - and 50% at another 100 - then a small amount on top of that - you will be over the $250 EV

 

[heckmanm]

Well the puzzle isn't limited to the first decimal.  Any number between 0 and 1 can be chosen - 0.5, 1/3, pi/4, 0.999999...., etc.  

I think I know what the answer is, and I do think that you can arrive at the right answer by starting with a simpler case like yours and then seeing what happens as the gap between possible numbers goes to 0.  

does it matter if the same number could be re-drawn more than once?

 

[Sinn Fein]

does it matter if the same number could be re-drawn more than once?

Given the infinite number set that can be chosen, I am going to guess no.

 

[heckmanm]

Given the infinite number set that can be chosen, I am going to guess no.

I was thinking of Iggy's suggestion of starting with a simple case (0.1, 0.2, ...0.9).  If I could draw 0.1, 0.1, 0.1 that's much different than if I could only (best case) draw 0.1, 0.2, 0.3, 0.4...

 

[Ignoratio Elenchi]

That's my assumption as well from the wording "between 0 and 1"

I actually think they are included, although I don't think it ultimately matters whether you include them or not.  We're dealing with limits to infinity anyway so "less than 1" and "less than or equal to 1" are basically the same thing.  

The puzzle does state that numbers are drawn until the sum is greater than 1, implying that you'll always need at least two draws.  

 

[Sinn Fein]

i cheated with a speadsheet model, but in 1M+ simulations of 5 numbers drawn - the EV was $271

 

[Ignoratio Elenchi]

does it matter if the same number could be re-drawn more than once?

Assume that the same number can be drawn multiple times.  

 

[matttyl]

Ok, I'm going on the assumption that 0 and 1 are excluded - meaning that the highest first number pulled would be .999999, meaning they'd have to draw again and you'd win a minimum of $200. 

From there, lets assume first that the numbers would have to be "quarters" (.25, .5, .75) - each with a 33.3% chance of being pulled (they said pen and paper, this is close enough)

Possible outcomes:

Spoiler

first pull of .25: (33% odds)

     second pull .25 (11.11% odds)

          third pull .25 (3.7% odds)

               fourth pull .25 (1.23% odds) - equal 1 at this point, fifth pull needed and doesn't matter what it is, win $500, net $250

          third pull of .50 (3.7% odds) - equal 1 at this point, fourth pull needed and doesn't matter, win $400, net $150

          third pull of .75 (3.7% odds) - over 1, win $300, net $50

     second pull .50 (11.11% odds)

          third pull .25 (3.7%) - equal 1 at this point, fourth pull needed and doesn't matter what it is, win $400, net $150

          third pull anything else (7.4%) - over 1 at this point, win $300, net $50

     second pull .75 (11.11%) - equals 1 at this point, third pull needed and doesn't matter what it is, win $300, net $50

first pull of .50 (33% odds)

     second pull of .25 (11.11% odds)

          third pull of .25 (3.7% odds ) - equal 1 at this point, fourth pull needed and doesn't matter what it is, win $400, net $150

          third pull of .50 or .75 (7.41% odds) - over 1, win $300, net $50

     second pull of .50 (11.11 % odds) - equal 1 at this point, third pull needed and doesn't matter, win $300, net $50

     second pull of .75 (11.11% odds) - over 1, win $200, net -$50

first pull of .75 (33% odds)

     second pull of .25 (11.11% odds) - equal 1, third pull needed and doesn't matter, win $300, net $50

     second pull of .50 or .75 (22.22% odds) - over 1, win $200, net -$50

Tallied: (with rounding errors)

1.23% shot of netting $250

11.11% shot of netting $150

51.85% shot of netting $50

33.33% shot of netting -$50

DO IT!!!

 

[Fred Lane]

Well you have 100% chance of getting $100

Seems like you have a 50% chance of getting the second $100  - so an expected value of $150 to this point.  It would decrease dramatically from here - so I don't see you getting close to even the $200 EV, let alone $250

Yes, I missed that detail.  I was assuming that if you went over one, you were not paid for that drawing - big difference.

i will now up the expected value to $222, and still would not take the bet.

 

[Dinsy Ejotuz]

New puzzle and solution to last week's.

First reaction is that since both the min and mean number of draws is 2.0 you'd lose $50 half the time, and win at least $50 1/2 the time.  So it's +EV due to the tail where you hit on 4/5/6 small numbers before they sum > one.

(ETA:  mean of 2.0 is not right -- 50% of results are 2.0 and 50% are at least 3.0, so mean is 2.5+ for the same reason as above.  WAG that EV is +$25 and you should play that game until they kick you out of the casino.) 

 

[Fred Lane]

Okay, I think I have a better thought out solution:

Odds of winning a 1st draw: $100 * 1 = $100 (median 0.5)

Odds of winning a 2nd draw: $100 * 1 = $100 (median 1.0)

Odd of winning a 3rd draw: (1/2) * 100 = $50 (1/2 means 1 out of 2 times will the first two draws be less than 1)

Odds of winning a 4th draw: (1/2) * (1/3) * 100 = $16.50 (1/2 times a third draw will happen, and 1/3 times will this be less than 1)

Odds of winning a 5th draw: (1/2) * (1/3) * (1/4) * 100 = $4.13 (1/6 times a fourth draw will happen, and 1/4 times will this be less than 1)

Odd of winning a 6th draw: (1/2) * (1/3) * (1/4) * (1/5) * 100 = $.82

Odd of winning a 7th draw: (1/2) * (1/3) * (1/4) * (1/5) * (1/6) * 100 = $.14

Odd of winning a 7th draw: (1/2) * (1/3) * (1/4) * (1/5) * (1/6) * (1/7) *100 = $.02

Sum of above:  $271.61

So, DO take the bet.

 

[GregR]

Even if 1 is included in the range of possible numbers, you are guaranteed to get two numbers for $200.  The game doesn't end until the sum is greater than 1.

Edit: whoops, already said, didn't see there was another page I hadn't read yet

 

[Ignoratio Elenchi]

Even if 1 is included in the range of possible numbers, you are guaranteed to get two numbers for $200.  The game doesn't end until the sum is greater than 1.

Edit: whoops, already said, didn't see there was another page I hadn't read yet

Yeah, I don't think it's too important to get hung up on the edge cases. Solve the problem as if 1 is included, or if it isn't.  Either way when you extrapolate to what happens in the continuous case I think you'll end up with the same answer either way. I even think it probably doesn't matter whether you solve for just reaching a sum of 1, or if you strictly have to exceed 1 - in the discrete case it would mean you go about things a little differently but when you take the limit to infinity they probably work out to the same thing. 

 

[Ignoratio Elenchi]

New puzzle, and solution to last week's.

Three very skilled logicians are sitting around a table — Barack, Pete and Susan. Barack says: “I’m thinking of two natural numbers between 1 and 9, inclusive. I’ve written the product of these two numbers on this paper that I’m giving to you, Pete. I’ve written the sum of the two numbers on this paper that I’m giving to you, Susan. Now Pete, looking at your paper, do you know which numbers I’m thinking of?”

Pete looks at his paper and says: “No, I don’t.”

Barack turns to Susan and asks: “Susan, do you know which numbers I’m thinking of?” Susan looks at her paper and says: “No.”

Barack turns back to Pete and asks: “How about now? Do you know?”

“No, I still don’t,” Pete says.

Barack keeps going back and forth, and when he asks Pete for the fifth time, Pete says: “Yes, now I know!”

First, what are the two numbers? Second, if Pete had said no the fifth time, would Susan have said yes or no at her fifth turn?

 

[fantasycurse42]

I recently found out this dude lives in my neighborhood. Supposedly he goes to this ####ty little Irish Pub here and there around the corner from my house. Hope I run into him one day.

 

[heckmanm]

I recently found out this dude lives in my neighborhood. Supposedly he goes to this ####ty little Irish Pub here and there around the corner from my house. Hope I run into him one day.

If you do, suggest -5^2 as the next weekly puzzle.

 

[heckmanm]

Spoiler

1. The numbers are 2 and 8

2. Susan would still have said "No" on her 5th turn

 

[heckmanm]

Esplanation of my process

Spoiler

Round 1

When Pete doesn’t know on the first guess, we can immediately eliminate any products with only 1 pair of factors (primes and squares of primes), leaving  products 4, 6, 8, 9, 12, 16, 18, 24 as possibilities.

Based on this, the sum must be between 4 and 13 inclusive, but when Susan doesn’t know, we can eliminate sums 4, 12 and 13, as there is only way to get each of those sums and still get one of the possible products.

Round 2

When Pete doesn’t know, it eliminates 4 as a product, since there is only way left to get there.  When Susan still doesn’t know, it then eliminates 5 as a sum

Round 3

When Pete still doesn’t know, it eliminates 6 as a product. When Susan still doesn’t know, it eliminates 7 as a sum

Round 4

When Pete still doesn’t know, it eliminates 12 as a product. When Susan still doesn’t know, it eliminates 8 as a sum

Round 5

On Pete’s 5th turn, there is only one unique product left: 16, which must be the product of 2 and 8, since 4 and 4 were eliminated when Susan didn’t know in round 4.

If Pete had still not known, that would have eliminated 16 as a product, but would still have left 2 ways to get each of sums 6, 9, 10, and 11, so Susan would not know either.

 

[Ignoratio Elenchi]

It's kind of fascinating how many different ways there were to solve last week's puzzle. There are several different solutions posted in the column today, and I haven't had a chance to really look at all of them but I think the way I solved it might not even be there. 

 

[matttyl]

Esplanation of my process

Spoiler

Round 1

When Pete doesn’t know on the first guess, we can immediately eliminate any products with only 1 pair of factors (primes and squares of primes), leaving  products 4, 6, 8, 9, 12, 16, 18, 24 as possibilities.

Based on this, the sum must be between 4 and 13 inclusive, but when Susan doesn’t know, we can eliminate sums 4, 12 and 13, as there is only way to get each of those sums and still get one of the possible products.

Round 2

When Pete doesn’t know, it eliminates 4 as a product, since there is only way left to get there.  When Susan still doesn’t know, it then eliminates 5 as a sum

Round 3

When Pete still doesn’t know, it eliminates 6 as a product. When Susan still doesn’t know, it eliminates 7 as a sum

Round 4

When Pete still doesn’t know, it eliminates 12 as a product. When Susan still doesn’t know, it eliminates 8 as a sum

Round 5

On Pete’s 5th turn, there is only one unique product left: 16, which must be the product of 2 and 8, since 4 and 4 were eliminated when Susan didn’t know in round 4.

If Pete had still not known, that would have eliminated 16 as a product, but would still have left 2 ways to get each of sums 6, 9, 10, and 11, so Susan would not know either.

Spoiler

Isn't the product of 36 still an option for Pete after round 1? (6x6 and 4x9)

 

[heckmanm]

Spoiler

Isn't the product of 36 still an option for Pete after round 1? (6x6 and 4x9)

Well, crap.  Now I wish i had saved my working doc where I was tracking all the combinations.

 

[Ignoratio Elenchi]

Spoiler

Isn't the product of 36 still an option for Pete after round 1? (6x6 and 4x9)

That's ruled out after Susan says no in round 1. 

 

[matttyl]

That's ruled out after Susan says no in round 1. 

Correct, after Susan - not after Pete.  I didn't mean to say he was wrong.  He nailed it.  Lots of leg work involved in this one.

 

[heckmanm]

That's ruled out after Susan says no in round 1. 

Whew! 

 

[Ignoratio Elenchi]

New puzzle and solution to last week's.

Can You Solve This Napoleonic Puzzle?

...

Now here’s this week’s Riddler, short but deadly, a Napoleonic puzzle.

Complete this series:

10, 11, 12, 13, 14, 15, 16, 17, 21, 23, 30, 33, …

(Yep, that’s it.)

Editing a second time to indicate that I don't see how "Napoleonic" has anything to do with the puzzle, and it isn't necessary for solving. 

 

[Ignoratio Elenchi]

I think I figured it out.  

 

[matttyl]

I'm not familiar with the term "Napoleonic puzzle".  Any change you can define it without giving away the answer to the puzzle itself?

 

[Ignoratio Elenchi]

I'm not familiar with the term "Napoleonic puzzle".  Any change you can define it without giving away the answer to the puzzle itself?

I actually have no idea what "Napoleonic" has to do with the puzzle.  Perhaps there's a connection I'm missing but it doesn't seem relevant at all to me.  Apologies for confusion, I originally assumed it was related but I'll edit my post above to reflect that.

Not sure how much of a hint this is but there are, I think, exactly three more numbers in the sequence.

 

[matttyl]

Could it be "Napoleonic" because the number of possible digits is short?

Spoiler

no 8 or 9

 

[Ignoratio Elenchi]

Could it be "Napoleonic" because the number of possible digits is short?

Spoiler

no 8 or 9

After re-reading the column I'm thinking maybe Napoleonic was just a punny reference to this week's puzzle being "short but deadly."  Not entirely sure what he was going for but I wouldn't focus on it, doesn't really relate to the problem in any way I can see.  

As it turns out, the digits you mentioned don't appear in any of the final three terms in the sequence either, so maybe you're right.

 

[matttyl]

Yeah, I'm going with short and deadly myself.

 

[matttyl]

Yeah, I still got nothing.  Mind sharing your answer in a spoiler?

I think I figured it out.  

 

[Ignoratio Elenchi]

Yeah, I still got nothing.  Mind sharing your answer in a spoiler?

As a hint, here are some similar (complete) sequences that are constructed in the same way as the one in the puzzle:

10, 11, 100, 1111

10, 11, 12, 13, 21, 111, 1111111

10, 11, 12, 13, 14, 15, 21, 23, 32, 1011, 11111111111

 

[Dinsy Ejotuz]

Been looking at it for awhile, but got nothing.  Keep wanting to do something in a base other than 10, but got nowhere with it.

 

[matttyl]

Got it. finally.

 

[matttyl]

As it turns out, the digits you mentioned don't appear in any of the final three terms in the sequence either, so maybe you're right.

3, or 2?

 

[Ignoratio Elenchi]

3, or 2?

3, although I guess you could argue that the third and last one is sort of trivial and pointless. 

Spoiler

The last three terms would be 120, 1111, and 111111111111111.

 

[Ignoratio Elenchi]

Something a little different, but might help pass the time until Friday's next puzzle... this weekend was the qualification round for Google Code Jam, a programming competition.  I took a stab at it on Saturday, and while the challenge is a programming one, each of the four problems have mathy components to them that basically need to be solved to efficiently answer the questions.  For the purposes of this thread I'll try to strip out just the "math puzzle" aspects but you'll probably want to read the full problems for context and additional details:  

A. Counting Sheep:  Start with a number N and note its digits.  Then look at 2N, 3N, ... until you've seen all ten digits from 0-9 at least once.  For some numbers, like 0, you'll just keep seeing 0 and the process will never end.  Are there other numbers like this?  How many successive multiples of N would you have to look at to be sure you've seen every digit from 0-9 (or decide that you'll never see them all)?

B. Revenge of the Pancakes:  You have a stack of pancakes, each of which has a happy face on one side and is blank on the other side.  You can tell which pancakes in the stack are face up and which are upside down.  On any turn, you can grab any number of pancakes off the top of the stack, flip the entire group upside down (not each one individually), and place it back on top of the stack.  What is the minimum number of turns you'd need to get all of the pancakes face up?

C. Coin Jam: A jamcoin is a string of N ≥ 2 digits with the following properties:

• Every digit is either 0 or 1.
  
• The first digit is 1 and the last digit is 1.
  
• If you interpret the string in any base between 2 and 10, inclusive, the resulting number is not prime.
  

You want to generate 500 different jamcoins that are each 32 digits long.  Come up with an efficient way to do this.  (In other words, one way would be to just look at every possible combination of 32 1s and 0s, convert it into every base from 2 to 10, and check if it's prime.  But these are big numbers so that would take a prohibitively long time.)

D. Fractiles: Long ago, the Fractal civilization created artwork consisting of linear rows of tiles. They had two types of tile that they could use: gold (G) and lead (L).

Each piece of Fractal artwork is based on two parameters: an original sequence of K tiles, and a complexity C. For a given original sequence, the artwork with complexity 1 is just that original sequence, and the artwork with complexity X+1 consists of the artwork with complexity X, transformed as follows:

• replace each L tile in the complexity X artwork with another copy of the original sequence
  
• replace each G tile in the complexity X artwork with K G tiles
  

You have just discovered a piece of Fractal artwork, but the tiles are too dirty for you to tell what they are made of. Because you are an expert archaeologist familiar with the local Fractal culture, you know the values of K and C for the artwork, but you do not know the original sequence.  

What is the minimum number of tiles you'd need to clean to determine whether or not the artwork contains a G tile?  Which tiles would you clean?

 

[ZWK]

Here's an answer for C. Coin Jam:

Spoiler

Pick any 500 numbers between 0 and 16383. Write them in binary, as 14-digit numbers (including leading 0's). Then, for each of them, make a 28-digit binary number by duplicating each digit twice in a row. For example, 00000000110101 becomes 00,00,00,00,00,00,00,00,11,11,00,11,00,11 (I have added a comma after each pair of digits for ease of reading). Then add an extra "11" to the beginning and end - with this example number you'd get 11000000000000000011110011001111. These are your jamcoins.

In base 10, they are all divisible by 11. In base nine, they are all divisible by ten. In base eight, they are all divisible by nine. ... And in base two, they are all divisible by three. In base b, they are all divisible by b+1 (in other words, the first sentence of this paragraph is true regardless of which base you interpret it as being written in).

The rightmost 2 digits equal b+1 (since they are always both 1). The next 2 rightmost digits equal (b+1)*b^2 if both are 1 or 0 if both are 0. The next 2 rightmost digits equal (b+1)*b^4 if both are 1 or 0 if both are 0. Then (b+1)*b^6 for the next pair of digits, etc. So we're just adding up a bunch of things which are all divisible by (b+1).

I initially started thinking that you could do this with divisibility rules. You can make each number be divisible by three in base ten by making sure that the number of 1's is a multiple of 3 (since you can check if a number is divisible by 3 by seeing if the digits sum to a multiple of 3). You can make each number be even in base three by making sure that the number contains an even number of 1's. And those two rules actually make your number non-prime in bases 4, 5, 7, and 9 as well. When I tried to come up with how to get the number to be divisible by three in base two, I realized that the answer would actually cover all of the bases. This version gives you up to 16384 jamcoins, and a slight variant can get you more.

 

[Ignoratio Elenchi]

Here's an answer for C. Coin Jam:

Spoiler

Pick any 500 numbers between 0 and 16383. Write them in binary, as 14-digit numbers (including leading 0's). Then, for each of them, make a 28-digit binary number by duplicating each digit twice in a row. For example, 00000000110101 becomes 00,00,00,00,00,00,00,00,11,11,00,11,00,11 (I have added a comma after each pair of digits for ease of reading). Then add an extra "11" to the beginning and end - with this example number you'd get 11000000000000000011110011001111. These are your jamcoins.

In base 10, they are all divisible by 11. In base nine, they are all divisible by ten. In base eight, they are all divisible by nine. ... And in base two, they are all divisible by three. In base b, they are all divisible by b+1 (in other words, the first sentence of this paragraph is true regardless of which base you interpret it as being written in).

The rightmost 2 digits equal b+1 (since they are always both 1). The next 2 rightmost digits equal (b+1)*b^2 if both are 1 or 0 if both are 0. The next 2 rightmost digits equal (b+1)*b^4 if both are 1 or 0 if both are 0. Then (b+1)*b^6 for the next pair of digits, etc. So we're just adding up a bunch of things which are all divisible by (b+1).

I initially started thinking that you could do this with divisibility rules. You can make each number be divisible by three in base ten by making sure that the number of 1's is a multiple of 3 (since you can check if a number is divisible by 3 by seeing if the digits sum to a multiple of 3). You can make each number be even in base three by making sure that the number contains an even number of 1's. And those two rules actually make your number non-prime in bases 4, 5, 7, and 9 as well. When I tried to come up with how to get the number to be divisible by three in base two, I realized that the answer would actually cover all of the bases. This version gives you up to 16384 jamcoins, and a slight variant can get you more.

That's awesome, very clever.  I gave up pretty quickly and just brute-forced a solution instead, but meant to revisit it this week since I knew there had to be a much nicer solution. 

 

[ZWK]

Here's a partial answer for A. Counting Sheep:

Spoiler

You will see every digit for any integer besides 0. You are guaranteed to see every digit if you look at all the multiples up to 81N.

You might not ever have to go all the way to 81N. You do at least sometimes have to go to 45N. So the bound is somewhere from 45 to 81.

If your number N is 2, then you don't get a 9 until 45N=90. So 45 is a lower bound on how far you need to go to guarantee that you've seen all the digits.

Next, let me argue that the bound is at most 90N. If you go up to 90N, then you are guaranteed to hit every digit (besides 0) as the first digit of the number. If you have a 3-digit number, for example, then you are guaranteed to get a "4" by hitting some number in the 4000s, because a 3 digit number is not large enough to let you jump straight from 3999 to 5000. By 90N you will be over 9000 (or equal to it) so you will have picked up every digit from 1-9 as the leading digit of a 4-digit number. And you have 0 as the last digit of 10N. It works basically the same if your original number is not 3 digits (e.g., if N is a 4-digit number then you can't jump from 39999 to 50000). So 90N is an upper bound on how far you need to go.

And I can get the bound down to 81N rather than 90N. Write your number in scientific notation as c * 10^k. If c < 10/9, then you are guaranteed to hit every number (1-9) as the leading digit by the time you've reached 9N, so you only need to go to 10N. If c is at least 10/9, then 81N is at least 90 * 10^k so you have hit every number as a leading digit by 81N.

If we allow numbers to be infinite fractions, then N = 1/9 = 0.11111111... requires you to go all the way to 81N before you get a 9. If number have to be integers, then I have a hunch that you never have to go past 45N. But for a programming problem, I'd play it safe and go up to 81N.