## Poll

 I love math! 18 votes (50%) Math is great. 13 votes (36.11%) My religion is mathology. 5 votes (13.88%) Women didn't speak to me until I was 30. 2 votes (5.55%) Total eclipse reminder -- 04/08/2024 11 votes (30.55%) I steal cutlery from restaurants. 3 votes (8.33%) I should just say what's on my mind. 6 votes (16.66%) Who makes up these awful names for pandas? 5 votes (13.88%) I like to touch my face. 11 votes (30.55%) Pork chops and apple sauce. 8 votes (22.22%)

36 members have voted

gordonm888
Joined: Feb 18, 2015
• Posts: 3619
May 2nd, 2022 at 11:46:57 AM permalink
I have been looking at random graph theory, which is a field in discrete mathematics. Notably, combination math is central to this math field. Here is the simplest (but non-trivial) conventional random graph problem I can think of.

Given: Four points (usually called vertexes) are placed randomly in space.

Any line that connects two vertexes is called an "edge." Thus, with four randomly-placed points there are six possible edges. Each edge is defined to have the same probability, p, of occurring/existing.

Write an algebraic expression (or ensemble of algebraic equations) for the probability that edges will exist such that they form one or more loops.
- Note that if two edges cross at a point that is not a vertex that this is not a corner in a closed loop. In other words, if the four vertexes were cities, and the edges are roads connecting cities, then at any point where two roads cross it should be assumed that one road has a bridge over the other road.

Extra credit for a plot (x-y graph) of the probability of at least one loop occurring as a function of p (the probability that an edge occurs between any two points.)
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
ThatDonGuy
Joined: Jun 22, 2011
• Posts: 5361
May 8th, 2022 at 3:05:57 PM permalink
Quote: gordonm888

I have been looking at random graph theory, which is a field in discrete mathematics. Notably, combination math is central to this math field. Here is the simplest (but non-trivial) conventional random graph problem I can think of.

Given: Four points (usually called vertexes) are placed randomly in space.

Any line that connects two vertexes is called an "edge." Thus, with four randomly-placed points there are six possible edges. Each edge is defined to have the same probability, p, of occurring/existing.

Write an algebraic expression (or ensemble of algebraic equations) for the probability that edges will exist such that they form one or more loops.
- Note that if two edges cross at a point that is not a vertex that this is not a corner in a closed loop. In other words, if the four vertexes were cities, and the edges are roads connecting cities, then at any point where two roads cross it should be assumed that one road has a bridge over the other road.

Extra credit for a plot (x-y graph) of the probability of at least one loop occurring as a function of p (the probability that an edge occurs between any two points.)

If fewer than three edges exist, there cannot be any loops.
If three exist, they must connect each other; there are 4 ways to do this.
If four exist, either three of them connect each other, with the fourth path connecting one of those three vertices to the fourth one, or all four do.
There are four possible 3-loops, each with 3 possibilities for the fourth edge, and three possible 4-loops (1234, 1243, 1324 - note 1342, 1423, and 1432 are the same as 1243, 1324, and 1234).
If five or more exist, then at least one 3-loop must exist
P = 4 p^3 (1-p)^3 + 15 p^4 (1-p)^2 + 6 p^5 (1-p) + p^6
= 4 p^3 + 3 p^4 - 12 p^5 + 6 p^6

Gialmere
Joined: Nov 26, 2018
• Posts: 2326
May 14th, 2022 at 7:57:30 AM permalink
A Riddler racket puzzle by Jason Ash...

You are an expert counterfeiter, and you specialize in forging one of the most ubiquitous notes in global circulation, the U.S. \$100 bill. You’ve been able to fool the authorities with your carefully crafted C-notes for some time, but you’ve learned that new security features will make it impossible for you to continue to avoid detection. As a result, you decide to deposit as many fake notes as you dare before the security features are implemented and then retire from your life of crime.

You know from experience that the bank can only spot your fakes 25 percent of the time, and trying to deposit only counterfeit bills would be a ticket to jail. However, if you combine fake and real notes, there’s a chance the bank will accept your money. You have \$2,500 in bona fide hundreds, plus a virtually unlimited supply of counterfeits. The bank scrutinizes cash deposits carefully: They randomly select 5 percent of the notes they receive, rounded up to the nearest whole number, for close examination. If they identify any note in a deposit as fake, they will confiscate the entire sum, leaving you only enough time to flee.

How many fake notes should you add to the \$2,500 in order to maximize the expected value of your bank account? How much free money are you likely to make from your strategy?
Have you tried 22 tonight? I said 22.
ThatDonGuy
Joined: Jun 22, 2011
• Posts: 5361
May 14th, 2022 at 1:22:11 PM permalink
Quote: Gialmere

A Riddler racket puzzle by Jason Ash...

You are an expert counterfeiter, and you specialize in forging one of the most ubiquitous notes in global circulation, the U.S. \$100 bill. You’ve been able to fool the authorities with your carefully crafted C-notes for some time, but you’ve learned that new security features will make it impossible for you to continue to avoid detection. As a result, you decide to deposit as many fake notes as you dare before the security features are implemented and then retire from your life of crime.

You know from experience that the bank can only spot your fakes 25 percent of the time, and trying to deposit only counterfeit bills would be a ticket to jail. However, if you combine fake and real notes, there’s a chance the bank will accept your money. You have \$2,500 in bona fide hundreds, plus a virtually unlimited supply of counterfeits. The bank scrutinizes cash deposits carefully: They randomly select 5 percent of the notes they receive, rounded up to the nearest whole number, for close examination. If they identify any note in a deposit as fake, they will confiscate the entire sum, leaving you only enough time to flee.

How many fake notes should you add to the \$2,500 in order to maximize the expected value of your bank account? How much free money are you likely to make from your strategy?

I can't think of any way to integrate combinations particularly easily, so this appears to be a Brute Force problem

Let N be the number of fake bills; the object is to maximize the following value:
N x C(25, celing((25 + N)/20)) / C(25 + N, ceiling((25 + N)/20))
since you are drawing ceiling((25 + N)/20) bills from a set of 25 + N, and want to get one of the combinations of ceiling((25 + N)/20) from a set of 25.

The number of counterfeit bills needed is 15; the expected value is \$576.923

GM
Joined: Jun 16, 2021
• Posts: 39
Thanks for this post from:
May 14th, 2022 at 4:39:18 PM permalink
I disagree. You don't seem to take into account that the probability of the bank not detecting any fake notes depends on the number of fake and genuine notes in the sample selected by the bank and I don't think there is a nice formula for it.
Let n be the number of fake notes you are trying deposit. Let a be the number of notes selected by the bank, which is (n+25)/20 rounded up. The probability that exactly b of these notes are fake is binomial(n,b)*binomial(25,a-b)/binomial(n+25,a), then the conditional probability of the bank not noticing any of the fake notes is (3/4)^b. Hence the probability of the bank not noticing the fake notes is the sum of (3/4)^b*binomial(k,b)*binomial(25,a-b)/binomial(n+25,a) from b=0 to b=a, and the expectation of the amount you are able to deposit is 100(n+25) times this probability. I calculated the expectation for all n up to 200 and the maximum is at n=55, \$3756.89, and the expected profit is \$1256.89.
ThatDonGuy
Joined: Jun 22, 2011
• Posts: 5361
May 14th, 2022 at 5:37:40 PM permalink
Quote: GM

I disagree. You don't seem to take into account that the probability of the bank not detecting any fake notes depends on the number of fake and genuine notes in the sample selected by the bank and I don't think there is a nice formula for it.

Actually, I did forget to take something into account - the fact that there is a possibility that fake notes won't be detected.
Ace2
Joined: Oct 2, 2017
• Posts: 1580
May 14th, 2022 at 6:19:00 PM permalink
Quote: GM

I disagree. You don't seem to take into account that the probability of the bank not detecting any fake notes depends on the number of fake and genuine notes in the sample selected by the bank and I don't think there is a nice formula for it.

Let n be the number of fake notes you are trying deposit. Let a be the number of notes selected by the bank, which is (n+25)/20 rounded up. The probability that exactly b of these notes are fake is binomial(n,b)*binomial(25,a-b)/binomial(n+25,a), then the conditional probability of the bank not noticing any of the fake notes is (3/4)^b. Hence the probability of the bank not noticing the fake notes is the sum of (3/4)^b*binomial(k,b)*binomial(25,a-b)/binomial(n+25,a) from b=0 to b=a, and the expectation of the amount you are able to deposit is 100(n+25) times this probability. I calculated the expectation for all n up to 200 and the maximum is at n=55, \$3756.89, and the expected profit is \$1256.89.

For 55 fakes plus 25 genuine bills = 80 total bills, we know the bank will select 4 bills and that of the 55 fakes, they can only tell that 14 of them (25% rounded up) are actually fakes. They can't tell that the other 41 are actually fake.

So I get the expected value for a deposit of 80 total bills of:

combin(25+41,4) / combin(80,4) * 80 = 36.4557 bills = \$3645.57

Last edited by: Ace2 on May 14, 2022
It’s all about making that GTA
Gialmere
Joined: Nov 26, 2018
• Posts: 2326
May 15th, 2022 at 10:47:31 AM permalink
Quote: GM

Let n be the number of fake notes you are trying deposit. Let a be the number of notes selected by the bank, which is (n+25)/20 rounded up. The probability that exactly b of these notes are fake is binomial(n,b)*binomial(25,a-b)/binomial(n+25,a), then the conditional probability of the bank not noticing any of the fake notes is (3/4)^b. Hence the probability of the bank not noticing the fake notes is the sum of (3/4)^b*binomial(k,b)*binomial(25,a-b)/binomial(n+25,a) from b=0 to b=a, and the expectation of the amount you are able to deposit is 100(n+25) times this probability. I calculated the expectation for all n up to 200 and the maximum is at n=55, \$3756.89, and the expected profit is \$1256.89.

Correct!!

Well done.

You should add 55 fake notes to your 25 real notes for a total deposit of \$8,000. Your expected gain is \$1,256.

The full counterfeit solution (counterfeit bills, that is … the solution itself is very real) comes to us from this puzzle’s submitter, Jason Ash:

Your expected gain is the weighted average of expected profit from successful deposits and expected losses from bank seizures. With 55 fake notes, there is a 47 percent chance — a combination of the chances of the bank selecting our fake notes for examination and of the examination revealing any fake notes — we avoid detection and collect a profit of \$5,500, the value of the fake notes we were able to sneak into circulation. (Remember we started with \$2,500, so only the fake notes count as profit.) There is a 53 percent chance we are caught by the bank and lose the \$2,500 in real dollars we used as decoys. Therefore, our expected profit is (0.47)(5,500) – (0.53)(2,500) = 1,256.

How can we be sure no other strategy produces a higher profit? For example, suppose we combine 30 fake notes with 25 real notes instead. The bank will select three notes for its audit — that is, 5 percent of 55, rounded up to the nearest whole number. Depending on our luck, the bank could choose all three fake notes, all three real notes, or some combination in between.

Let’s assume the bank randomly chooses two fake notes and one real note for its audit. This occurs with roughly 41.5 percent probability, given by the formula (3 choose 2)(30/55)(29/54)(25/53). Each fake note is detected 25 percent of the time, which means at least one fake note from the pool of two is detected 1−0.752

= 43.75 percent of the time. We use similar logic to solve for the likelihood and detection rate of the audits with three fake, one fake and zero fake notes. The overall detection rate is equal to the weighted average across each potential audit.

For the 30 fake, 25 real strategy, the probability of success is 64.3 percent — again, we need to either avoid their selecting our fake notes for examination or, if they do select them, avoiding identification of them as such — and the probability of detection is 35.7 percent. Therefore, the expected profit is (0.643)(3,000) – (0.357)(2,500) = 1,038. That’s a decent payday, but we can do better. The chart below shows the profit for strategies with up to 200 fake notes, and it illustrates that the maximum is achieved when we use 55 of them.

We can see two patterns above. First, as we move to the right, we enter the “greedy danger zone,” in which the bank becomes more likely to discover our fraud and seize the starting capital, resulting in larger and larger expected losses. Second, we see “sawtooth” behavior caused by the bank’s practice of auditing 5 percent of deposited notes. The effect is significant: 55 is the ideal answer because if we deposit 80 total notes, the bank will audit four. If we use 56 fake notes for a total of 81, then the bank audits five notes instead, which cuts the expected gain in half!

A life of crime only pays if you’re good with numbers. But with great power comes great responsibility, Riddler Nation.

--------------------------------------------------------

Be on the lookout for hot singles in your area.
Have you tried 22 tonight? I said 22.
gordonm888
Joined: Feb 18, 2015
• Posts: 3619
May 15th, 2022 at 2:50:47 PM permalink
Quote: ThatDonGuy

Quote: gordonm888

I have been looking at random graph theory, which is a field in discrete mathematics. Notably, combination math is central to this math field. Here is the simplest (but non-trivial) conventional random graph problem I can think of.

Given: Four points (usually called vertexes) are placed randomly in space.

Any line that connects two vertexes is called an "edge." Thus, with four randomly-placed points there are six possible edges. Each edge is defined to have the same probability, p, of occurring/existing.

Write an algebraic expression (or ensemble of algebraic equations) for the probability that edges will exist such that they form one or more loops.
- Note that if two edges cross at a point that is not a vertex that this is not a corner in a closed loop. In other words, if the four vertexes were cities, and the edges are roads connecting cities, then at any point where two roads cross it should be assumed that one road has a bridge over the other road.

Extra credit for a plot (x-y graph) of the probability of at least one loop occurring as a function of p (the probability that an edge occurs between any two points.)

If fewer than three edges exist, there cannot be any loops.
If three exist, they must connect each other; there are 4 ways to do this.
If four exist, either three of them connect each other, with the fourth path connecting one of those three vertices to the fourth one, or all four do.
There are four possible 3-loops, each with 3 possibilities for the fourth edge, and three possible 4-loops (1234, 1243, 1324 - note 1342, 1423, and 1432 are the same as 1243, 1324, and 1234).
If five or more exist, then at least one 3-loop must exist
P = 4 p^3 (1-p)^3 + 15 p^4 (1-p)^2 + 6 p^5 (1-p) + p^6
= 4 p^3 + 3 p^4 - 12 p^5 + 6 p^6

Correct. Very good. I wondered whether this problem statement had broken the thread because of the long silence that followed it's posting.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
Gialmere
Joined: Nov 26, 2018
• Posts: 2326
May 16th, 2022 at 7:30:59 AM permalink
Here's a few easy Monday puzzles...

You are on your way to visit your Grandma, who lives at the end of the valley. It's her birthday, and you want to give her the cakes you've made.

Between your house and her house, you have to cross 7 bridges, and as it goes in the land of make believe, there is a troll under every bridge! Each troll, quite rightly, insists that you pay a troll toll. Before you can cross their bridge, you have to give them half of the cakes you are carrying, but as they are kind trolls, they each give you back a single cake.

How many cakes do you have to leave home with to make sure that you arrive at Grandma's with exactly 2 cakes?

Al and Ben are standing back to back next to a railroad track. When the front of a train passes them, Al starts to walk in the opposite direction of the train, while Ben starts to walk in the same direction as the train. Each stops walking when the back of the train passes him.

If the two of them walk at the same speed, and Al walks exactly 30 feet, and Ben walks exactly 45 feet, how long is the train?
Have you tried 22 tonight? I said 22.