Sequence Differences (Diffsy Qs I)

 Years and years ago, back in my old Math League days, I came up with a trick to finding out the formulas of sequences. The problem type I'm talking about would give me a list of Xs and Ys in a table like this:

Wait, I need HTML for tables? Wow, okay.

X	1	2	3	4	5
Y	4	8	14	22	32

Oh my god, I thought I hated tables when I only knew of how awful they were in the context of word processors. HTML tables are so much worse.

Anyways, the problems would have a table like the one above and ask for the equation that generated those values, usually in the form of y = f(x). There aren't any convenient algorithms for this, so usually the student is expected to graph it, determine if it's a line or parabola, and use the appropriate equations. 

This problem is actually one of the few interesting math problems that a student might see in school. I categorize a lot of math taught in schools as a three step process: 

1. Remember the formula or algorithm that applies to this problem.

2. Apply the formula or algorithm and follow the steps.

3. Write down the result.

This problem gets an additional step; an analysis of the results, as simple as it may be. 

1. Remember the formula or algorithm that applies to this problem (Hm, when the problem looks like this, I have to graph the points on a Cartesian plane)

2. Apply the formula or algorithm and follow the steps. (Actually graph each point)

3. Analyze the results. (Check if the graphed points follow a line or a parabola)

4. Remember the formula or algorithm that applies to this problem (Remember the appropriate formulas for your graph)

5. Apply the formula or algorithm and follow the steps. (Use the appropriate formulas / plug 'n chug)

6. Write down the result (The formulas spit out this number for the slope and this number for the y-intercept, so I can put them in place of the m and the b and write down the equation)

Yeah, that additional analysis step is very simple, but it's one of two examples that come to mind in the math I learned as a kid that weren't completely algorithmic. (The other is triangle congruence, which was always a favorite of mine!) 

This analysis step is something I loved back then, because I could get around it with some thinking. Why bother graphing out all those points when you can just intuitively figure out whether the points will make a line or a parabola? (Well, because the teacher's going to take points away for not showing your work, that's why.)

So, how do you figure out whether it's a line or a parabola without graphing it? I came up with a method that I'm now going to retroactively call "Sequence Differences". I called them "subsequences" back then, but it turns out that that term is protected. I subtracted adjacent y values from each other to make a new sequence that had one fewer term. Let's see if I can get a table to illustrate that:

X	1	2	3	4	5
Y1	4	8	14	22	32
Y2	4	6	8	10

Eh, close enough. As you can see, the Y₂ sequence comes from 8 - 4, 14 - 8, 22 - 14, and 32 - 22. Upon seeing this, I thought "these numbers are all different, and lines have a constant slope, so it must be a parabola!" and went on to the next part of the problem. But isn't it interesting that the numbers are increasing in an arithmetic sequence? If I were to do another round of sequence differences here, 

X	1	2	3	4	5
Y1	4	8	14	22	32
Y2	4	6	8	10
Y3	2	2	2

we can see that the sequence is constant. Somehow, every time I performed a sequence difference, I decremented the degree of the source equation. The first equation was y = x² + x +2; the second can be solved to be y = 2x + 2, and the last is just y = 2. Looks... a bit familiar, doesn't it? The constant isn't the same, but it looks almost like we're taking the derivative to find the equations that describe our new sequences. There's a mystery there!

But, that's probably plenty for one day; it's definitely enough HTML tables for one day. All that remains is a name, and I think I've got a good one. Differential Equations are often abbreviated to Diff Eq, pronounced "Diffy Q", and this problem is about Differences (of) Sequences, so let's go with the almost cringeworthy Diffsy Q. Next time, a deep dive into the mechanics of Diffsy Qs!

Nerdle + Absurdle: A Theoretical Combination of Two Games

Wordle is a simple-to-understand game that chooses a secret five-letter English word, and then asks you to guess it. If your guess has letters in common with the secret word, you get a yellow square if it's in the wrong position, and a green square if it's in the right position. It's the classic Bagels Pico Fermi / Mastermind / Bulls and Cows (which is the first implementation of this concept I was able to find) feedback system when trying to guess a secret sequence. And when any game gets the widespread popularity that Wordle got, there will absolutely be game variants with varying degrees of quality. I want to focus in on two - Nerdle and Absurdle. 

Absurdle is an adversarial version of Wordle - Absurdle will dynamically change the chosen word to make it as hard as possible for you to get it. In return, you get an infinite number of guesses. This makes it interesting, but not replayable - the same moves in the same order will win every time. 

Nerdle is a version of Wordle that uses simple equations instead of words - a valid, eight-character equation is chosen, and your goal is to guess what it is. Your "letters" are the digits 0 through 9, the four standard operations (+, -, *, and ÷), and the equals sign. There are a few additional rules, but the important one for our purposes is that the equation is set up in an "expression = number" format, so equations like "15 = 60 - 45" and "10 - 8 = 7 - 5" aren't valid. It's called Nerdle because math is for nerds, I guess. 

So here's the question. If there was an adversarial version of Nerdle that tried to dynamically change the secret equation to give you the least information possible, how would we solve it? What would be the best technique to find a solution?

So, one approach to this would be to start exploring the space of all possible valid equations. This is definitely a task for a Python script - a basic script could simply iterate through all ~7,000,000,000 possible permutations of these 15 characters in a 8 character sequence and evaluate whether they are mathematically valid. A more complicated script could eliminate lots of those cases by only allowing one equals sign, not allowing adjacent operations, not allowing numbers to start with 0, etc. But I'm more interested in what we can do without brute forcing it.

Let's assume that the adversarial algorithm tries to give us the least information possible. If we type in a guess, it will change its secret equation so that it can give us less information, and it'll keep doing it as long as possible. That gives us a general starting point - maybe it's true that any equation we choose for our first guess is going to have nothing in common with the answer, except for the mandatory equals sign. 

So, here's what that would look like. If we start with my standard Nerdle opener, "12+35=47", the best case for the algorithm is to return something without 1, 2, 3, 4, 5, 7, or +, and with the equals sign in a different place. Does such an equation exist? Well, with a little thought, we can see that the trivial equation "9999*0=0" satisfies those conditions, so the algorithm will be able to achieve its best case scenario of giving us the least information possible.

But it has actually given us a lot of critical information. It's told us that 1, 2, 3, 4, 5, 7, and + appear nowhere in its equation, and that the equals sign must be in some place other than the 6th slot. The only tools we're left with are 6, 8, 9, 0, -, *, and ÷.

Another angle we can explore here is that there's only a few places the equals sign can be. The equation must be of the form "Expression = number", so we're limited by how big the number on the right can be. It could be a one-digit number (such as in the case of "10-2-3=5"), a two-digit number (such as "10+20=30", or a three-digit number ("80*4=320"). But can it be a four-digit number? It would have to take the form of "#*#=####" - we only have three characters to make a four-digit number. And without exponents, factorials, or up arrows, our best bet is multiplication, but we can already see that that won't work. When multiplying integers, the product can only have as many digits as the two factors combined. So there's exactly three places that the equals sign can be. And using our earlier method, that means we can force it into being in a particular place with two calculated guesses. It also means that there's no way we'll be able to win without at least three guesses.

So now we've got some proven techniques and ideas:

• We can eliminate digits and operations with guesses.
• We can use two guesses to nail down the location of the equals sign. 
• We have a starting lower bound for this problem of 3 guesses.

Adding to that, I've got some intuition about this problem - nothing I can prove without a computer, but intuition is all we have when we're first approaching a problem like this. 

• We should try to choose a solution that we like, and then try to force it onto the algorithm by eliminating everything else, as opposed to a top-down approach. 
• We should try to use multiplication and division instead of addition or subtraction - it forces the product or dividend to have factors, which limits the kinds of numbers it can be. There are a lot of numbers that add up or subtract to get 562, but only a very small number that multiply or divide to get 562 (within our domain, of course).
• We should try to optimize for a solution with the fewest digits and operations, to minimize complexity and eliminate many possibilities immediately.
• We should try to optimize for a solution without the possibility of commutativity - "10+10=20" is better than "10+11=21", even though they have the same digits and operations; the latter can also be written as "11+10=21", and the algorithm will gleefully mark us incorrect no matter which one we choose first.

That seems like a good stopping point for our groundwork for this problem. Next time, we'll get into making some initial guesses and then refining our strategy, and maybe retroactively trying to understand how and why these qualities are intuitively desirable. All that remains is a name for the problem, and it really writes itself: Absnerdle! Need a name for a problem and don't know what to pick? A lazy portmanteau always does the trick!

Birthday Puzzle 2021!

Hey folks, and welcome back to Spandan's Birthday Puzzle, 2021 edition. I've taken things in a very different direction this year. Normally I try to make something very complicated, something emergent, but at the same time fundamental... with varying degrees of success. What usually happens is that only a very small number (usually 0-2) of people end up solving them, and even that's only with a decent number of hints and additional clues. I'm usually more fixated on a puzzle ideal than I am on making it enjoyable; that has its own form of value to me, but often leaves people frustrated. 

So, here's a new direction I'm trying. I tried to invent a new Nikoli-style puzzle: a puzzle with clear, simple rules, with a well-defined progression path to the answer. I aimed for a puzzle like Hashi, Nonograms, or Sudoku, a puzzle that someone learns the rules to and plays in their spare time, deriving enjoyment from learning little tricks and shortcuts as they play. Let me be very clear - There is no "puzzle behind the puzzle" or anything else going on in this puzzle but the 12 puzzles and extras that are presented clearly at face value. In the past, I've delighted in hiding things in the introduction text, in changing details and making intentional typos as part of a deeper puzzle, and I'm sure I'll delight in them again, but this puzzle is exactly what it appears to be on the surface. That's a promise, and I wouldn't lie about that. 

Now, the puzzle. It's called Twinominoes, and it involves adding lines to a figure to split it into pieces that follow some rules. Short of writing an app for it, my best choice is to resort to Excel / Google Sheets as the tool that the most people have access to (even though Sheets is terrible at handling custom border drawing). So, here's the link to the puzzle itself.

https://drive.google.com/file/d/1_wL3NMGQdyXwnys85hYnBiIX2I2mvzHB/view?usp=sharing

I strongly recommend downloading a copy; the Google Sheets preview doesn't always do borders properly, but I made sure the puzzles were all functional in Sheets, so it should work if absolutely necessary. Graph paper and pencil is definitely the best option, but it does require more effort. Whatever medium you use, and however many or few puzzles you solve, I'd love to see your solutions and hear your feedback about if this new kind of puzzle is fun or interesting. Thanks for reading!

Harmony of the Spheres 2: The Tinkering Begins

 

As soon as I saw that beautiful cornucopia of a graph that we talked about in the first Harmony of the Spheres problem, I wanted to tinker. What would the graph look like if it was only two simultaneous notes, or four? What if we split the octave into eleven or thirteen semitones?

There’s two major variables at play here: the number of different tones and the number of simultaneous voices. Let’s call them t and v; t for tones, and v for voices. Each combination of t and v should give us a different graph. Like before, each node is a possible set of notes; a sound the group could be making. Each edge is one voice moving up or down one note; if one combination of notes is being sung, and one person decides to move up one note, they’ve moved the sound from one node to the other, along an edge.

Ideally, we’d want to have a system in which we know what the graph looks like if we’re given t and v. So let’s try to find one. Let’s start way down low, at the basics, and build out this set of graphs. If t is one, it doesn’t matter what v is, because all of the voices have to sing the same pitch (the only pitch that exists). And the order of the voices doesn’t matter, so those graphs have exactly one node. Which is the most boring graph possible.

If v is one, then that voice can sing any of the tones in t. But, under our rules, the pitch doesn’t matter, either – what matters is the relationships between the tones. Therefore, these graphs will also only have one node.

Now, the first non-trivial case: 2 x 2. Two tones, two voices. Let’s start with both voices on the same tone. That’s our first node, and then… something interesting happens. Moving one voice up or down to find another node, no matter how we do it, seems to bring us to the same new node – the node in which the two voices are different.

A hard example could be helpful here. Imagine two people, Alice and Bob, taking a break from writing ciphers, and two notes, C and D. The way this musical scale works is that there’s only two notes in the octave, C and D. If you sing one note higher than D, it’s a C. One note down from C, it’s a D.

So we started with both Alice and Bob singing C. That’s our first node. Then, Bob decides to sing one higher while Alice stays on C, and by our rules, that’s an edge to another node. Now Alice is on C, and Bob is on D. New node. But now, no matter who changes their note, and in what direction, we’re going to end up back at the first node!

If Bob goes down, they’re both at C again. If Bob goes up, he goes up to C. If Alice goes up or down, she goes to D, the same note that Bob is on, and remember, we only care about the relationships between the notes, so D+D is the same as C+C! And if we try to go to a different node from the first node, we quickly find that C+D is the same as D+C!

I'll keep track of the ones we've done in a table, like so.

 

Not very interesting so far – we’ve just shown that if there’s two tones and two voices, they can sing either different notes or the same note, and that’s it. But as we add more voices and tones, things will get very complicated, fast!