This week the question is: Can You Grow a Hibiscus Hedge? #permutation #sequence

Dean has three colors of the hibiscus: red, orange, and yellow. He wants to plant them in a straight hedge of shrubs (each of which is one color) so that the order appears somewhat random, but not truly random. More specifically, he wants the following to be true:

– No two adjacent shrubs have the same color. – No ordering of three consecutive shrubs appears more than once in the hedge. (But a prior ordering can appear in reverse. For example, ROYOR is an acceptable hedge, but ROYROY is not.)

What is the greatest number of shrubs Dean’s hedge can contain?

And for extra credit:

In addition to red, orange, and yellow hibiscus flowers, Dean now includes a fourth color: pink. Again, he wants to plant a straight hedge of shrubs that appears somewhat random. Here are the rules for ordering the shrubs this time:

– No two adjacent shrubs have the same color. – No ordering of four consecutive shrubs appears more than once in the hedge. (Again, a prior ordering can appear in reverse.) – Among any group of four consecutive shrubs, at least three distinct colors are represented.

What is the greatest number of shrubs Dean’s hedge can contain?

Intermission.

I am sort of obsessed with the candy puzzle from last week. Handled correctly, it’s possible to see, that the important graph has a structure, and that this structure can be used to find the required path. (This picture has a few connections missing, but hopefully it still demonstrates the principle.)

Oh! And I’ve just discovered that years ago a similar puzzle was featured on the riddler. Scroll down to the classic solution.

Last week I had to guess at the solution to the extra credit question. As it happens, I had the right idea: 21 students. But that wasn’t what the question actually asked for. Sigh. Read the question carefully, next time, me! Anyway. I got 21 points out of 26 possible in Q1. Actually not bad.

Highlight to reveal (possibly incorrect) solution:

Related problem. Program.

What are we actually looking for here?

We are interested in the permutations of the 3 colors with 3 elements. However, a permutation cannot have 2 neighbors with the same color. And in the final sequence, a permutation can appear at most once.

My program (brute forcing all possible sequences) tells me, 1) there are 12 of these permutations, 2) it is possible to build a sequence with all of them, and this sequence therefore has length 14.

One possible sequence: ROROYRYOYORYRO.

And for extra credit:

Now there are 4 colors and the permutations have 4 elements. As an extra requirement, each permutation has at least 3 colors. (Having a similar requirement doesn’t change anything in the fiddler case.)

My program tells me, 1) there are 96 of these permutations, 2) it is possible to build a sequence with all of them, and this sequence therefore has length 99.

One possible sequence (split up in smaller chunks for readability):

RORYRORPRO
YROYOROYPR
OPRYRPRYOR
YOYRYOPRPO
ROPORYPRYP
ORPOYRPOPY
ROPYORPYRY
PYRPYOYPOY
OPOYPYOPYP
RPYPOPROR

I’ve just finished reading #RedMars . A lot can be said about this book. These notes will be about just 3 topics, because I spent extra energy on them. 2 of these topics are actually topics discussed by the characters, so many times, in so many forms. It was a bit confusing for me, until I realized all those discussions were actually related. The 3rd topic is an attempt to create a #timeline .

Society, decision making:

• Like Earth? Capitalism? Democracy? Communism?
• Something new?
• Leaderless?
• Controlled from Earth?
• Independent?

Terraforming:

• Yes/no.
• Fast/slow.
• How exactly?

Timeline:

Time	Plot
Summer of 2020	Boone becomes the first man on Mars.
2022?	The selection process for the 1st 100 begins, lasting years before the move to Antarctica.
2024?	Construction of the ship to take the 1st 100 to Mars begins, lasting less than 2 years.
2025?	The 1st 100 and others live in Antarctica for 1 year.
July 20th, 2026	The 9 month voyage from Earth to Mars begins.
	The colonists use a new calendar. Ls goes from 0 to 360, and then starts over. A martian year is 668.6 local days long. This is split into Ls 0-90 (northern spring), 90-180 (northern summer), 180-270 (northern fall) and 270-360 (northern winter).
April, 2027	The 1st 100 land on Ls = 7.
2029	The dirigible Arrowhead is sent from Earth, like a lot of other provisions keep coming.
2031?	Children, all about 3 years old. The hidden colony is founded.
2033?	Chalmers becomes US Secretary.
2037?	Russell is named scientific head of the terraforming effort. Boone starts working for him.
2043?	Arabs arrives on Mars 10 years before Nicosia dedication ceremony.
2044?	UNOMA headquarters is established in Burroughs.
2047 / m-year 10	Boone tries to figure out who’s responsible for actions of sabotage. Chalmers has been US Secretary for 3 administrations. There are 10,000 colonists.
2048 / m-year 11	Rejuvenation technique begins use. The great storm begins.
2050?	The great storm ends after 3 years, 2 m-years. Construction on the space elevator begins.
2053?	Nicosia dedication ceremony. The first town of any size to be built free-standing on the martian surface. 5000 people. 25 years of friendship (beginning 2026).
February 6th, 2057 / Ls = 144, m-16	The walk on the bridge, an important bit of the negotiation of the new Mars treaty.
June 2057	The treaty is signed.
July 2057	Chalmers begins a 2 year “vacation”.
2059	Chalmers returns to work, frustrated that the treaty isn’t followed. 1,000,000 people on Mars. Less than 1% of the surface habitable.
	Revolution.

There’s an intriguing timeline elsewhere.

This week the question is: Can You Solve a High Schooler’s Favorite Puzzle?

A teacher is handing out candy to his students, of which there are at least four. He abides by the following rules:

• He hands out candy to groups of three students (i.e., “trios”) at a time. Each member of the trio gets one piece of candy.
• Each unique trio can ask for candy, but that same trio can’t come back for seconds. If students in the trio want more candy, they must return as part of a different trio.
• When a trio gets candy, the next trio can’t contain any students from that previous trio.

It turns out that every possible trio can get a helping of candy. What is the smallest class size for which this is possible?

And for extra credit:

Instead of trios of students, suppose now that groups of 10 students come up to get candy. This time, there are at least 11 students in the class. As before:

• Each member of the group of 10 gets one piece of candy per visit.
• Each unique group of 10 can ask for candy, but the exact same group of 10 can’t come back for seconds. If students in the group want more candy, they must return as part of a different group.
• When a group of 10 gets candy, the next group of 10 can’t contain any students from the previous group of 10.

Suppose the class size is the minimum that allows every possible group of 10 to get a helping of candy. How many pieces of candy does each student receive?

Highlight to reveal (possibly incorrect) solution:

Program.

The first trio could be ABC. The next trio could be DEF. The next trio can’t contain any of D, E or F, and it can’t contain all of A, B and C, so there has to be 1 more student: G. So we need at least 7 students.

(If you want to, you can name the students Annie, Bob etc.)

I wrote a program to test this theory, and found a solution. There has to be at least 7 students, and a solution with 7 students exists. We need 7 students.

Solution: abc def abg cde abf deg acf bde acg bdf ceg abd cef bdg ace bfg acd efg bcd afg bce dfg abe cfg ade bcf adg bef cdg aef bcg adf beg cdf aeg. But this isn’t the only one, as far as I can tell.

And for extra credit:

I am not sure. I’ve been trying to find a pattern in the trio solution, some way to expand this solution to 10 students in each group. No such luck. So I’ve made a guess: 21.

It is time to rant some! The internet doesn’t contain enough ranting!

Episode 183, 372 pages

A fun little game of trying to guess the number of rankings for books on Goodreads, higher or lower. And then laughing. That many people read this book? That many liked it? LOL.

🇩🇰🇩🇰🇩🇰

Den danske sprog er svær – men gør vi selv nok for at gøre det lettere?

Jeg er helt med på, at hvis man ikke bliver forstået, så hjælper det nok at tale tydeligt.

Men 2 anekdoter er vist ikke nok til at påvise, at dansk er specielt svært.

Det her med spaniere. Er der nogle lyde, de aldrig har lært, og derfor har svært ved at lære som voksne?

This week the question is: Can You Root for the Underdog?

Once again, there are four teams remaining in a bracket: the 1-seed, the 2-seed, the 3-seed, and the 4-seed. In the first round, the 1-seed faces the 4-seed, while the 2-seed faces the 3-seed. The winners of these two matches then face each other in the regional final.

Also, each team possesses a “power index” equal to 5 minus that team’s seed. In other words:

• The 1-seed has a power index of 4.
• The 2-seed has a power index of 3.
• The 3-seed has a power index of 2.
• The 4-seed has a power index of 1.

In any given matchup, the team with the greater power index would emerge victorious. However, March Madness fans love to root for the underdog. As a result, the team with the lower power index gets an effective “boost” B, where B is some positive non-integer. For example, B could be 0.5, 133.7, or 2𝜋, but not 1 or 42. To be clear, B is a single constant throughout the tournament, for all matchups.

As an illustration, consider the matchup between the 2- and 3-seeds. The favored 2-seed has a power index of 3, while the underdog 3-seed has a power index of 2+B. When B is greater than 1, the 3-seed will defeat the 2-seed in an upset.

Depending on the value of B, different teams will win the tournament. Of the four teams, how many can never win, regardless of the value of B?

And for extra credit:

Instead of four teams, now there are 2⁶, or 64, seeded from 1 through 64. The power index of each team is equal to 65 minus that team’s seed.

The teams play in a traditional seeded tournament format. That is, in the first round, the sum of opponents’ seeds is 2⁶+1, or 65. If the stronger team always advances, then the sum of opponents’ seeds in the second round is 2⁵+1, or 33, and so on.

Once again, the underdog in every match gets a power index boost B, where B is some positive non-integer. Depending on the value of B, different teams will win the tournament. Of the 64 teams, how many can never win, regardless of the value of B?

Highlight to reveal (possibly incorrect) solution:

Spreadsheet. Animation.

First off, let’s word the problem differently.

• In the first round the a-seed faces the (5-a)-seed.
• The power index for the a-seed is 5-a.
• Further, in a match the team with the lowest power index gets a boost B, so the power index will actually be 5-a+B.
• If the a-seed and the b-seed meet each other, then the a-seed will win if 5-a > 5-b+B.
• As B isn’t an integer, there will always be a winner.
• In a match where the 1-seed loses to the 4-seed, these all give the same result:
  • 5-1 < 5-4+B
  • 3 = 4-1 < B
  • B = 3.1
  • B = 3.9
  • ⌈B⌉ = 4
• We can therefore just look at 1 representative for each integer, to get through all options: 0+ε, 1+ε, 2+ε etc.

In order to figure out what will happen with 4 teams, we probably have to look at B going from 0+ε to 5+ε. Enter a spreadsheet. Revealing that 1, 3 and 4 can win, but not 2. 1 team can’t win.

And for extra credit:

I do the same thing in the same spreadsheet, just bigger. This reveals the winning teams 1, 2, 10, 6, 22, 18, 14, 46, 50, 54, 58 and 62, 12 teams in all. 64-12 = 52 teams can never win. After correcting some errors in the spreadsheet after getting a hint from a fellow fiddler, it now reveals the winning teams 1, 3-2 (because I found them in that order), 6-4, 12-8, 24-16 and 48-64. Therefore 7, 13-15, 25-47 can’t win. 1 + 3 + 23 = 27 teams.

It is time to rant some! The internet doesn’t contain enough ranting!

Nothing? Oh my.

🇩🇰🇩🇰🇩🇰

Vi tager gerne en tur til i manegen med ’Hunger Games’ (paywall)

5. bind af Hunger Games bliver villigt kaldt en dystopi her. 👍🏻 Men den bliver også kaldt fantasy. 2-3 gange. Suk.

Levering fra GLS

Sådan noget som 10. gang, at en lever-derhjemme-pakke ikke bliver leveret derhjemme. Metoden er noget i retning af, at chaufføren skal tage et billede af sin tommelfinger foran min ringeklokke, men derefter faktisk ikke ringer på. Og så åbner jeg selvfølgelig ikke døren …

Så kontakter jeg dem for at klage. En eller anden finder fotografiet, og siger så, at alt er efter bogen. Ikke noget at gøre.

Et par gange har jeg sat en optager til, så jeg kunne dokumentere, at lyden af min ringeklokke ikke var der. Det har tilsyneladende ikke hjulpet på noget, at jeg kunne sende sådan en.

De er jo nødt til at stole på deres chauffør. Siger de. Men det sætter mig bare i en vanskelig situation. Er der nogen måde, jeg kan bevise min historie på, som de vil godtage?

Foreløbig bruger jeg så vidt muligt andre firmaer. Nu har jeg så også prøvet at anmelde dem på Trustpilot. Hvor jeg kan se, at masser af andre klager over det samme. Og bliver afvist på samme måde.

This week the question is: Can You Play the Favorite?

March Madness—the NCAA basketball tournament—is here!

The single-elimination tournament consists of 64 teams spread across four regions, each with teams seeded 1 through 16. (In recent years, additional teams beyond the 64 have been added, but you needn’t worry about these teams for this week’s puzzle.)

Suppose in any matchup between teams with seeds M and N, the M-seed wins with probability N/(M+N), while the N-seed wins with probability M/(M+N). For example, if a 3-seed plays a 5-seed, then the 3-seed wins with probability 5/8, while the 5-seed wins with probability 3/8.

In one of the brackets, the top four seeds remain (i.e., the 1-seed, the 2-seed, the 3-seed, and the 4-seed). If case you’re not familiar with how such brackets work, at this point the 1-seed and 4-seed face off, as do the 2-seed and 3-seed. The winners then play each other.

What is the probability that the 1-seed will emerge victorious from this region?

And for extra credit:

As before, the probability that an M-seed defeats an N-seed is N/(M+N). But instead of 16 teams in a region, now suppose there are 2^k teams, where k is a very large whole number.

The teams are seeded 1 through 2^k, and play in a traditional seeded tournament format. That is, in the first round, the sum of opponents’ seeds is 2^k+1. If the stronger team always advances, then the sum of opponents’ seeds in the second round is 2^k−1+1, and so on. Of course, stronger teams may not always advance, but this convention tells you which seeds can play which other seeds in each round.

For any such region with 2^k teams, what is the probability that the 1-seed emerges victorious from the region?

Highlight to reveal (possibly incorrect) solution:

Program .

In order for the 1-seed to win, they have to beat the 4-seed and the winner of the 2-seed/3-seed match. The first win has probability 4/5. The winner of the other match is the 2-seed with 3/5 probability and the 3-seed with 2/5 probability. The 1-seed is victorious in this 2nd match with probability 3/5 * 2/3 + 2/5 * 3/4 = 7/10. Combined with the 1st win, the overall probability for a winner 1-seed is 4/5 * 7/10 = 14/25 = 56%.

My program confirms this.

And for extra credit:

There’s probably a smart way to combine all the above fractions into a sum, that then turns into, I don’t know, sin(2^k). 😁 I will however stick to my program, fiddled (!) a little to let k grow and see what happens. The probability quickly converges to 51.6%.

Recently I’ve been reading my way through one of those bundles. In this case so, so many books by John Scalzi. A lot of reasons for that. The bundle was cheap. And I liked Redshirts, and Fuzzy Nation, and some other stuff here and there. Oh yeah, Old Man’s War. It would be nice to read the rest of the series.

But the language is increasingly rubbing me the wrong way. So many words could be deleted. A lot of sentences could be shortened. And in some cases, a sentence is simply constructed wrong or represents a falsehood. (Disclaimer: My English isn’t perfect either. But I’m not a millionaire author.)

So, just for funzies, let’s look at a random segment of text.

The Last Emperox. Prologue. (Hopefully a link to the Kindle preview.)

ooo

… he only got as far as saying “I,” and really only the very first phoneme of that very short word…

(“I” only has 1 phoneme.)

ooo

… the surfaces of the aircar’s passenger cabin, Ghreni Nohamapetan, acting Duke of End…

(Repetition of phrase, 3 paragraphs earlier.)

ooo

… roughly 89 percent… A distant second to this, at maybe 5 percent…

ooo

… Ghreni’s brain decided…

(A quirk with this writer, where a person and their brain isn’t the same thing.)

ooo

Coming in third, at maybe 4.5 percent…

ooo

Inasmuch as Blaine Turnin’s body…

(Repetition of full name.)

ooo

Coming in third, at maybe 4.5 percent of Ghreni’s cognitive attention, was I think I need a new minister of defense. Inasmuch as Blaine Turnin’s body was now presenting a shape that could only be described as “deeply pretzeled,” this was probably correct and therefore did not warrant any further contemplation.

(Repetition.)

ooo

And indeed, why Ghreni Nohamapetan?

ooo

And indeed, why Ghreni Nohamapetan? What were the circumstances of fate that led him to this moment of his life, spinning wildly out of control, literally and existentially, trying to keep from vomiting on the almost-certain corpse of his now-very-probably-erstwhile minister of defense?

ooo

That was, until a great shift in the Flow would happen-ed at some point in the near future…

ooo

(And I’m only 1/4 through this chapter.)

ooo

… rolling several times before coming to a full and complete stop.

ooo

Blaine Turnin’s body was in the seat opposite him, quiet, composed and restful, looking for all the world like he had not been a human maraca bean for the last half minute. Only Turnin’s head, tilted at an angle that suggested the bones in his neck had been replaced by overcooked pasta, suggested that he might not, in fact, be taking a small and entirely refreshing nap.

ooo

… in a secured room of his palace that lay far underground, in a subterranean wing…

ooo

I have to assume there are traitors in our my midst.

ooo

“Well, and this is just a hypothesis, it might have something to do with the fact that you’re an incompetent who assassinated his way to the dukedom and has lied to his subjects about the imminent collapse of civilization, which, incidentally, you have to date done nothing to prepare for in any meaningful way.”

ooo

“Why do you come to see me, Ghreni?” he asked.
“What do you mean?”
“I mean, why do you come see me?…”

ooo

“Yes, of course, you’re correct, an entirely ineffective rebel leader managed to infiltrate your security detail, plant at least one traitor, learn your secret travel itinerary and send a missile directly into your aircar and no others. Sorry, I was confused about that.”

(Repetition.)

ooo

“I need someone to talk to,” Ghreni said, suddenly.
Jamies looked over toward the (acting) duke. “I beg your pardon?”
“You asked why I keep visiting you,” Ghreni said. “I need someone to talk to.”

ooo

“I still vote for the therapist.”
“You could still help me,” Ghreni said.

ooo

Halfway there. Oh, I think I’ll stop here.

So. What’s going on here?

• A little bit of bad research or something.
• A little bit of not knowing, that 7 syllable names need to be shortened when used a lot.
• A lot of “repetitions are fun, if the language is different”.

For the last bit, ehm, no.

ETA: Rachel Neumeier kindly agreed to take a look at the same text: Writing Analysis: John Scalzi.

This week the question title is: A Pi Day Puzzle

You are planning a picnic on the remote tropical island of 𝜋-land. The island’s shape is a perfect semi-disk with two beaches, as illustrated below: Semicircular Beach (along the northern semicircular edge of the disk) and Diametric Beach (along the southern diameter of the disk).

If you pick a random spot on 𝜋-land for your picnic, what is the probability that it will be closer to Diametric Beach than to Semicircular Beach? (Unlike the illustrative diagram above, assume the beaches have zero width.)

And for extra credit:

Suppose the island of 𝜋-land, as described above, has a radius of 1 mile. That is, Diametric Beach has a length of 2 miles.

Again, you are picking a random point on the island for a picnic. On average, what will be the expected shortest distance to shore?

Highlight to reveal (possibly incorrect) solution:

Figure. Desmos.

From a point p₁ within the semi-disk, the distance to the semicircle is actually the distance to the point p₂ on the semicircle, that lies on the line going through the center of the semicircle and p₁, as that line is perpendicular to the tangent going through p₂. (Figure.) The distance to the diameter is measured by simply going straight down.

Assuming that the radius of the semicircle is 1, the distance from center to p₂ is 1. The distance from center to p₁ = (x₁, y₁) is (x₁² + y₁²)^0.5. The distance between p₁ and p₂ is 1 – (x₁² + y₁²)^0.5.

The distance from p₁ to the diameter is simply y₁.

And what we’re looking for is the part of the semi-disk, where y₁ < 1 – (x₁² + y₁²)^0.5.

The area of the whole semicircle is π * 1² / 2 = π / 2.

The area of the purple area of the Desmos figure is… Hang on.

y = 1 – (x² + y²)^0.5 <=>

1 – y = (x² + y²)^0.5 <=>

(1 – y)² = x² + y² <=>

1 – 2y + y² = x² + y² <=>

1 – 2y = x² <=>

1 – x² = 2y <=>

(1 – x²) / 2 = y

So the area of the purple area is

∫ (1 – x²) / 2 dx, from -1 to 1 =

1/2 ∫ 1 – x² dx, from -1 to 1 =

1/2 [x – x³/3] from -1 to 1 =

1/2 ((1 – 1/3) – (-1 + 1/3)) =

1/2 (2/3 + 2/3) =

2/3

So the probability of aiming for the red area and hitting the purple area is 2/3 / π/2 = 4/3π ~ 0.4244.

And for extra credit:

Program.

Imagine the semi-disk is the base of a shape, described by z = f(x, y). At the beaches, f(x, y) = 0. Elsewhere, f is the distance to the nearest shore. We want to integrate over this shape.

Or maybe we just want to monte carlo it. 😉

My program reaches the conclusion, that the average distance is something like 0.192 miles.

This week the question is: Can You Tip the Dominoes?

You are placing many, many dominoes in a straight line, one at a time. However, each time you place a domino, there is a 1 percent chance that you accidentally tip it over, causing a chain reaction that tips over all dominoes you’ve placed. After a chain reaction, you start over again.

If you do this many, many times, what can you expect the median (note: not the average) number of dominoes placed when a chain reaction occurs (including the domino that causes the chain reaction)? More precisely, if this median number is M, then you would expect to have placed fewer than M dominoes at most half the time, and more than M dominoes at most half the time.

And for extra credit:

You’re placing dominoes again, but this time the probability of knocking each domino over and causing a chain reaction isn’t 1/100, but rather 10^–k, where k is a whole number. When k = 1, the probability of knocking over a domino is 10 percent; when k = 2, this probability is 1 percent; when k = 3, this probability is 0.1 percent, and so on.

Suppose the expected median number of dominoes placed that initiates a chain reaction is M. As k gets very, very large, what value does M/10^k approach?

Highlight to reveal (possibly incorrect) solution:

Program 1, 2.

Calculating using probabilities: Assuming I simply start all these lines at the same time. After placing 1 domino in each line, 1/100 of them will tip over. After placing the 2nd domino in each remaining line, 1/100 of these will tip over. And so on, until more than half have tipped over. I write a short program to keep track of the numbers. The answer is 69.

Simulation: I write a short program to simulate a lot of lines. Same answer.

And for extra credit:

Program.

I change to first program a little, so I can go through probability 1/10, 1/100, 1/1000 etc. Apparently M/10^k goes towards 0.69314718, which looks like ln(2).