S2T2

Jim Randell 4:30 pm on 13 January 2023 Permalink Reply
Tags: by: Victor Bryant ( 140 )   

• 

  Jim Randell 5:23 pm on 13 January 2023 Permalink | Reply

  (See also: Enigma 1636).

  If F is the single-digit percentage of forged notes then in a representative sample of X notes, then (F/100)X of them are actually forged.

  And when the pen indicates N forgeries, in fact only one of the notes is forged, then the pen is giving false positives (i.e. it is testing some genuine notes as forgeries). It is not clear if the pen gives false negatives or not. In the following I assume the pen does not give false negatives (i.e. it will always indicate a forged note is forged, but it will also sometime indicate that a genuine note is forged), but see below for a treatment that includes false negatives.

  If we suppose that when testing a quantity of notes, the pen indicates that a fraction f of them are forged.

  Then if we test N notes (of which (F/100)N are forgeries) we get 1 false positive. So:

  f.N = (F/100)N + 1

  And if X is the quantity of notes required to get N positive tests, then:

  f.X = N
  ⇒ f = N/X

  But in this case only 1 of the notes is forged, so:

  (F/100)X = 1
  ⇒ X = 100 / F
  ⇒ f = N/X = (F/100)N

  Combining the equations:

  (F/100)N² = (F/100)N + 1
  F.N² − F.N − 100 = 0

  And we know F is a value in [1..9].

  Run: [ @replit ]

  from enigma import (irange, quadratic, printf)
  
  for F in irange(1, 9):
    for N in quadratic(F, -F, -100, domain="Z"):
      if N > 0:
        printf("F={F} N={N}")
  

  Solution: N = 5.

  This is the case when there are no false negatives. (i.e. the pen always gives a positive test for a forgery, but sometimes will give a positive test for a genuine note).

  In this case: F = 5, N = 5, fp = 4/19 (≈ 21.1%), fn = 0.

  Applying the pen to a representative sample of 100 notes:

  100 notes = 95 genuine, 5 forgeries.
  The pen tests as forgeries, all 5 of the forged notes (correctly), and 20 of the genuine notes (incorrectly), giving 25 positive tests in total.
  The pen tests as genuine, none of the forgeries, and 75 of the genuine notes (correctly), giving 75 negative tests in total.
  The average error rate is 20/100 = 1/5 (as required).
  And of the positive tests 5/25 = 1/5 are actually forgeries (as required).

  For an alternative interpretation of the puzzle, see my comment below.

  ---

  I also wrote a simulation of testing 10 million notes with the pen, and it verifies the values produced give a viable solution to the puzzle. [@replit]

  LikeLike

  • 

    Jim Randell 12:51 pm on 14 January 2023 Permalink | Reply

    With a bit more work we can allow for false negatives as well as false positives:

    fp = fraction of genuine notes that test as forgeries
    fn = fraction of forged notes that test as genuine

    The equations become:

    “of 100 notes, 100/N test incorrectly”
    ⇒ fn.F + fp.(100 − F) = 100/N

    “testing X hundred notes gives N positive tests”
    ⇒ fp.(100 − F).X + (1 − fn).F.X = N

    “only one of the positive tests in X hundred notes is actually a forgery”
    ⇒ (1 − fn).F.X = 1

    It turns out there are many solutions that satisfy these equations.

    Setting fn = 0 gives us the quadratic equation in my original comment.

    But if we set fp = fn (= r) (i.e. the rate of false positives is the same as the rate of false negatives) then we get:

    r.F + r.(100 − F) = 100/N
    ⇒ r = 1/N

    (1 − r).F.X = 1
    ⇒ X = N / (N − 1).F

    r.(100 − F).X + 1 = N
    ⇒ F.N² − 2F.N + (2F − 100) = 0

    And this quadratic equation can be solved in a similar way to the previous one, and also gives a single solution to the puzzle:

    Run: [ @replit ]

    from enigma import (irange, quadratic, printf)
    
    for F in irange(1, 9):
      for N in quadratic(F, -2*F, 2*F - 100, domain="Z"):
        if N > 0:
          printf("F={F} N={N}")
    

    Solution: N = 8.

    This is the case the false positive rate and false negative rate are the same.

    In this case: F = 2, N = 8, fp = 1/8 (= 12.5%), fn = 1/8 (= 12.5%).

    Applying the pen to a representative sample of 100 notes (or 10,000 notes if you don’t like fractional notes):

    100 notes = 98 genuine, 2 forgeries.
    The pen tests as forgeries, 1.75 of the forged notes (correctly), and 12.25 of the genuine notes (incorrectly), giving 14 positive tests in total.
    The pen tests as genuine, 0.25 of the forged notes (incorrectly), and 85.75 of the genuine notes (correctly), giving 86 negative tests in total.
    The average error rate is (12.25 + 0.25)/100 = 1/8 (as required).
    And of the positive tests 1.75/14 = 1/8 are actually forgeries (as required).

    This scenario also tests as viable using the simulation code mentioned above.

    I’m inclined to think this might be the intended interpretation, as we need to restrict F to a single digit integer in order to get a unique solution. But it would have saved some bother if the puzzle text had just stated that the rates of false positives and false negatives were equal.

    ---

    And here is a solution where the false positive and false negative rates are similar (and smaller than in the published answer), but not equal:

    F = 1, N = 11, fp = 890/9801 (≈ 9.1%), fn = 10/99 (≈ 10.1%).

    Applying the pen to a representative sample of 100 notes:

    100 notes = 99 genuine, 1 forgery.
    The pen tests as forgeries, 0.90 of the forged note (correctly), and 8.99 of the genuine notes (incorrectly), giving 9.89 positive tests in total.
    The pen tests as genuine, 0.10 of the forged note (incorrectly), and 89 of the genuine notes (correctly), giving 89.10 negative tests in total.
    The average error rate is (8.99 + 0.10)/100 = 1/11 (as required)
    And of the positive tests 0.90/9.89 = 1/11 are actually forgeries (as required)

    LikeLike

    • 

      Jim Randell 12:33 pm on 22 January 2023 Permalink | Reply

      The published answer was: N = 8.

      Which confirms my suspicions that the false positive and false negative rates are intended to be the same.

      LikeLike

• 

  Tony Smith 8:11 pm on 17 January 2023 Permalink | Reply

  Nothing in the wording suggests that the rates might be different.

  LikeLike

  • 

    Jim Randell 10:40 am on 18 January 2023 Permalink | Reply

    I think you need to assume that the false positive and false negative rates are the same in order to arrive at the intended solution. Something that could have easily been mentioned in the puzzle text.

    LikeLike

• 

  Tony Smith 11:45 am on 18 January 2023 Permalink | Reply

  “on average, for every N uses it only gives an incorrect result once”
  I think that is perfectly clear and unambiguous.

  I also think that is immediately obvious that if the rates were different it would not be possible to deduce an answer without more information about the two rates.

  The puzzle is actually solvable by the application of Bayes’s theorem with all relevant probabilities expressible in terms of N and the error rate.

  LikeLike