Math and Logic Puzzles: Redux

[implosion]

The old thread got archived. Here's a new one!

Vaguely, someone will post a math or logic puzzle. Other people try to solve it, and whoever solves it gets to post their own. But in practice, things can be free-formed; if you have an interesting riddle or puzzle, feel free to post it! Just don't flood the thread with a bunch of different things at once.

[implosion]

First is one that I thought of a few days ago. Consider the following way to create a graph based on a finite string:

-For each possible permutation of the characters of the string, create a vertex of the graph labeled with that permutation.
-Create an edge between any two permutations with the property that there exists a contiguous substring of one that can be reversed to form the other.

For instance, if our string is "happy", then the vertices for "happy" and "hppay" would share an edge, because you can reverse the "app" substring; likewise, "happy" would be adjacent to "yppah", "ahppy", etc.

Must any graph formed in this way must be regular (with every vertex having the same degree)? Prove, or provide a counterexample.

[Errantparabola]

ego

[Mitillos]

Start with a specific permutation. If all the characters in the string of length n are distinct, there are (n choose 2) possible inversions to perform, and therefore (n choose 2) neighbours to the corresponding vertex.

On the other hand, if any two characters in the permutation are the same, inverting the substring starting and ending with these characters is the same as inverting the substring between these two characters. Therefore, each pair of copies of characters reduces the number of distinct permutations that can be created by inversion (and therefore the number of neighbouring vertices) by 1.
Note that there are two degenerate cases: If two copies of the same character are consecutive or have a third arbitrary character between them, then the corresponding substring between these two copies is too short to be inverted; once again such an inversion can be ignored when counting the degree of a vertex.

Since every vertex corresponds to a permutation of the same collection of characters, the number of pairs of copies of characters, k, is the same for every vertex. Then, the degree of every vertex is (n choose 2) - k, and the graph is regular.

I'm sleepy, so I hope I didn't mess the reasoning up. I also can't think of any interesting problems right now, so someone else can ask something, instead.

[implosion]

That's pretty much it. The only other slight missing piece is showing that adding duplicate letters doesn't make any other reversals "not count," that is, that any reversal where the endpoints are distinct characters will never do the same thing as a different reversal where the endpoints are distinct characters, even if there are duplicate characters elsewhere in the string. But this isn't too difficult to show.

Here's one that's based on something that me and Mitillos and Ellibereth discussed in sitechat a while ago.

Suppose we have an undirected graph G, and a function f: G->R_≥0. That is, we have a graph and each vertex is labeled with a nonnegative real number. Additionally, f fulfills one other property: for any vertex v in G, f(v) is the average of f(w) over all neighbors w of v. That is, each vertex's label is the average of its neighbors' labels. Call a graph G

balanceable

if there exists such a function f that is nonconstant.

1) Prove that no finite graph is balanceable.
2) Exhibit some balanceable graph and a nonconstant function f with the given property for it. Note that no vertex can have infinite degree, as that would break the definition.
3) (the original problem we looked at, and we never figured it out, but feel more than free to take a crack if you want to): consider the 2-d square lattice graph (put a vertex at every lattice point in the cartesian plane, then connect each vertex to the four adjacent vertices). Is this graph balanceable?

[Ircher]

What exactly is a function in terms of a graph? As in, what inputs is it mapping? I may give this a try, but I would.need to know the previous.

[Harambey180]

Here's a maths puzzle from a maths book I just found:

Here you see three squares. Each square has four numbers in the corners; the first two squares have another number in the middle. The last one doesn't. Using the numbers in the corners so that you get the number in the middle in the same way for all three squares, what should the missing number in the third square be?
(Example: If you add up the top left and bottom right corner in the first square, you also add up those numbers for the second and third square)

7		2
	9
6		3

8		1
	7
4		4

9		6
	?
8		5

[Mitillos]

Answer 1: 25. Product of bottom numbers minus sum of top numbers.
Answer 2: 11. Bottom left number + 3.
Answer 3: 5. 23 - 2 * top left number.
Answer 4: 17. 2 * Top right number + 5.
Answer 5: 5. 15 - 2 * bottom right number.
Answer 6: 9. Sum of top numbers, multiplied by π, divided by bottom right number, and rounded down.

[Harambey180]

Answer 1: 25. Product of bottom numbers minus sum of top numbers.
Answer 2: 11. Bottom left number + 3.
Answer 3: 5. 23 - 2 * top left number.
Answer 4: 17. 2 * Top right number + 5.
Answer 5: 5. 15 - 2 * bottom right number.
Answer 6: 9. Sum of top numbers, multiplied by π, divided by bottom right number, and rounded down.

Answer 1 is correct and it is the only answer.
I forgot to mention that you have to use all four numbers in the corners and the four numbers only. All your other answers don't use all numbers and some also use illegible numbers.
Great job on finding the answer though! I guess I should have told to only use the four numbers...

[Harambey180]

Here are two more puzzles. They're separate puzzles, but both puzzles work in the same fashion.

For both puzzles: What missing number is supposed to be in the middle of this 'number wheel'? Explain why it is supposed to be the number you got and how you got to that answer.

Puzzle A:

18	10	8
24	?	37
8	22	5

Puzzle B:

13	1	2
2	?	31
17	43	2

[Tazaro]

egosearchbookmark

[Harambey180]

Puzzle A: Answer is 18 -- Each individual column adds up to 50, so middle square's value = 50 - 10 - 22 = 18.
Puzzle B: By comparison with the previous puzzle, it looks like a significantly more difficult one. I guess if no one answers it, then the fairest thing is to let me give the next puzzle

The answer to puzzle A is not the one I am looking for, even though it is correct in the way I showed it.
You should actually see the puzzles as connections that go through the question mark in the middle. So top left with bottom right, left with right, bottom left with top right, and top with bottom. Not with columns or rows.

[Ircher]

I would think you would have to give a bit more information to help us out on those puzzles; I don't see any patterns.

Not simple addition, subtraction, multiplication, division (try it and you'll see you get different answers for each)
Not modular arithmetic (i.e.: 18 mod X = 5 does not have the same value X as say if one tried 8 mod X = 8 and 24 mod X = 37)
Not non-decimal base system (Some of the sequences increase, others decrease, and in the first one, there is no change and this stuff implies the middle number would be different for each one)
Nothing to do with prime factorization
Doesn't seem to have anything to do with the digit sequence

Also, how can the same input give two different outputs??? (See puzzle B : Apparently, 2 gives both 17 and 31 as possible outputs after going through the middle)

[Harambey180]

I would think you would have to give a bit more information to help us out on those puzzles; I don't see any patterns.

Not simple addition, subtraction, multiplication, division (try it and you'll see you get different answers for each)
Not modular arithmetic (i.e.: 18 mod X = 5 does not have the same value X as say if one tried 8 mod X = 8 and 24 mod X = 37)
Not non-decimal base system (Some of the sequences increase, others decrease, and in the first one, there is no change and this stuff implies the middle number would be different for each one)
Nothing to do with prime factorization
Doesn't seem to have anything to do with the digit sequence

Also, how can the same input give two different outputs??? (See puzzle B : Apparently, 2 gives both 17 and 31 as possible outputs after going through the middle)

Oh no no no, it's not a sequence. It's the lines I was talking about, but you end up with the middle number. Not with one of the other two numbers.
So you use the two numbers in such a way each time that the 'third number' is always the same. That's the missing number.

Don't worry, this puzzle has 3 stars out of 3 for difficulty in the book that I got this from, so it belongs to the hardest ones in there. The previous one, for comparison, was 2 stars out of 3.

[BuJaber]

Puzzle A:

18	10	8
24	?	37
8	22	5

Puzzle B:

13	1	2
2	?	31
17	43	2

Puzzle A: the answer is 6.
Add the numbers on either side then take the product of the 2 digits of the result.
So:
18 + 5 = 23; 2 * 3 = 6.
24 + 37 = 61; 6 * 1 = 6
8 + 8 = 16; 6 * 1 = 6
10 + 22 = 32; 3 * 2 = 6.

Puzzle B: the answer is 12.
The product of the 2 numbers then the product of the digits of the result.
13 * 2 = 26; 2 * 6 = 12
2 * 31 = 62; 6 * 2 = 12
17 * 2 = 34; 3 * 4 = 12
43 * 1 = 43; 4 * 3 = 12

[Harambey180]

Puzzle A:

18	10	8
24	?	37
8	22	5

Puzzle B:

13	1	2
2	?	31
17	43	2

Puzzle A: the answer is 6.
Add the numbers on either side then take the product of the 2 digits of the result.
So:
18 + 5 = 23; 2 * 3 = 6.
24 + 37 = 61; 6 * 1 = 6
8 + 8 = 16; 6 * 1 = 6
10 + 22 = 32; 3 * 2 = 6.

Puzzle B: the answer is 12.
The product of the 2 numbers then the product of the digits of the result.
13 * 2 = 26; 2 * 6 = 12
2 * 31 = 62; 6 * 2 = 12
17 * 2 = 34; 3 * 4 = 12
43 * 1 = 43; 4 * 3 = 12

Do you own the book

[BuJaber]

No

These kinds of puzzles I understand. Once you let us know we can ignore the left column and the right column it became a lot easier.

I remember one time I found a math puzzles app for smartphones. This reminds me of that. Though if I recall it became unbearable because of ads.

I take it my answers are correct then?

[Harambey180]

Yup, they are! Great job

[StrangerCoug]

Here's what should be easy ones, as was traditional for me last time:

You've been hired at the state prison and your job is to oversee the factory that makes the state's license plates. A new license plate series started on Monday, January 1, 2018. In the series, license plates have to be three letters followed by three digits. License plates cannot use the letters I or O, nor can the digits be all zeroes. The license plates are made in sequential order, with the very first plate made on the first day being AAA-001, the plate after that being AAA-002, and so on through AAA-999, with the plate following AAA-999 being AAB-001. Assume your prison makes exactly 25,000 plates per day Monday through Friday with no holiday breaks and that there are no other restrictions to the allowed plate numbers.

1. What was the number of the last plate made on January 5, 2018? What will be the number of the last plate made on December 31, 2018?
   
2. On what day will you make plate number ZZZ-999? Which plate that day will that be?*
   
3. Suppose a law is passed that, after all the available numbers as above are exhausted, the alphabetic and numeric portions change places so that after ZZZ-999 comes 001-AAA. The numeric portion is still the portion that is incremented for the next plate, with the rollover from 999 to 001 incrementing the alphabetic portion, so the sequence goes ..., ZZZ-999, 001-AAA, 002-AAA, ..., 999-AAA, 001-AAB, ... If ZZZ-999 and 001-AAA are made the same day and you still make 25,000 plates total that day, when will you make plate number 999-ZZZ?

* For clarity, I'm looking for an ordinal number to the second part of the question, such as "the 12,345th plate" (which is incorrect, by the way).

[brassherald]

So, January 5, 2018 will be AFC-126, I believe.
December 31, 2018 will be BMD-532, I think.

If I'm right on those two, I'm pretty surprised, because I feel like I'm doing something wrong and will not do the other 2 questions for now.

[Harambey180]

Here's what should be easy ones, as was traditional for me last time:

You've been hired at the state prison and your job is to oversee the factory that makes the state's license plates. A new license plate series started on Monday, January 1, 2018. In the series, license plates have to be three letters followed by three digits. License plates cannot use the letters I or O, nor can the digits be all zeroes. The license plates are made in sequential order, with the very first plate made on the first day being AAA-001, the plate after that being AAA-002, and so on through AAA-999, with the plate following AAA-999 being AAB-001. Assume your prison makes exactly 25,000 plates per day Monday through Friday with no holiday breaks and that there are no other restrictions to the allowed plate numbers.

1. What was the number of the last plate made on January 5, 2018? What will be the number of the last plate made on December 31, 2018?
   
2. On what day will you make plate number ZZZ-999? Which plate that day will that be?*
   
3. Suppose a law is passed that, after all the available numbers as above are exhausted, the alphabetic and numeric portions change places so that after ZZZ-999 comes 001-AAA. The numeric portion is still the portion that is incremented for the next plate, with the rollover from 999 to 001 incrementing the alphabetic portion, so the sequence goes ..., ZZZ-999, 001-AAA, 002-AAA, ..., 999-AAA, 001-AAB, ... If ZZZ-999 and 001-AAA are made the same day and you still make 25,000 plates total that day, when will you make plate number 999-ZZZ?

* For clarity, I'm looking for an ordinal number to the second part of the question, such as "the 12,345th plate" (which is incorrect, by the way).

The end of January 5, 2018, means 25,000 * 5 = 125,000 plates will have been made.
There are 999 plates that start with AAA-???, AAB-???, and so on.
999 * 125 = 124,875 plates, so we are looking for the 126th letter combination, and the 125th number combination of that letter combo, which is 125.
The 126th letter combo is: AA?-??? has 26 combinations. 26 * 4 = 104. We are looking for the 5th A??-??? letter combo, so AE?-???, and we are looking for the 22nd letter to follow that (126 - 104 = 22), which is a W.
That makes the last plate on Friday, January 5th, 2018 to be AEW-125.

December 31, 2018 is the 365th day of the year because 2018 is not a leap year. There are 7 days in a week, and 7 * 52 = 364. So the 53rd week, and December 31 2018 is a Monday.
The plate factory only works 5 days a week. In 2018, there are 52 full weeks, so 52 * 5 = 260 days. Then finally add the Monday on December 31 2018: 261 days.
At the end of December 31, 2018, 25,000 * 261 = 6,525,000 plates will have been made.
There are 999 plates per letter combo. 6,525,000 / 999 = 6531.531..., so we are looking for the 6532nd letter combination.
6531 * 999 = 6,524,469.
6,525,000 - 6,524,469 = 531, so we need the 531st number combination, which is 531.
There are 26 AA? letter combinations, and 26 * 26 = 676 A?? letter combinations.
6532 / 676 = 9.662..., so we are looking for the 10th ?AA letter combination, or the 10th letter as the first letter, which is a J.
-------------------- Right now, we have the plate: J??-531 ---------------------
9 * 676 = 6084 and 6532 - 6084 = 448, so we are looking for the 448th two-letter combo.
448 / 26 = 17.230... so we need the 18th letter as the second letter of our plate, which is an R.
17 * 26 = 442 and 448 - 442 = 6, so the last letter is the 6th letter, which is the F.
That means that the last plate made on Monday December 31, 2018 is the plate JRF-531.

There are 999 number combinations, and 26 * 26 * 26 = 17,576 letter combinations, which means 17,576 * 999 = 17,558,424 combinations.
That means we are looking for the date on which the 17,558,424th plate is made.
25,000 plates are made each day, so 17,558,424 / 25,000 = 702.336, so the plate is made on the 703rd day on which plates are made.
There are five days a week in which plates are made, so 703 / 5 = 140.6, so the plate is made in the 141st work week, and on the third day of that week, so the Wednesday.
7 days a week, so 140 * 7 = 980 days + 3 = 983, so the 983rd day with January 1, 2018 as the first day.
2018 and 2019 are not leap years, so 365 * 2 = 730, and 983 - 730 = 253, so we are looking for the 253rd day in 2020.
2020 though is a leap year. With 31 representing the amount of days in January and so on, 31 + 29 + 31 + 30 + 31 + 30 + 31 + 31 = 244 days January through August. The 9th day of September, so the plate is made on Wednesday, September 9, 2020.
702 * 25,000 = 17,550,000, and 17,558,424 - 17,550,000 = 8,424.
That means that ZZZ-999 is the 8,424th plate made on Wednesday, September 9, 2020.

There are 17,558,424 combinations where the first part is made up of letters. Now we reverse that, so 17,558,424 * 2 = 35,116,848 plates.
35,116,848 / 25,000 plates a day = 1404.67... so the 1405th day is the day the plate is made.
Five days a week in which plates are made, so 1405 / 5 = 281.2, so the plate is made on the first day of the 282nd week.
7 days a week, so 281 * 7 1967 + 1 = 1968, so the 1968th day with January 1, 2018 as the first day.
2018 and 2019 are not leap years, so 365 * 2 = 730. 2020 is a leap year, so 730 + 366 = 1096. And 1405 - 1096 = 309. So the plate is made on the 309th day in 2021.
31 + 28 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31 = 304, and 309 - 304 = 5, so the 5th day of November.
That means that the plate 999-ZZZ will be made on Monday, November 5, 2021.


I really hope I got all of these right because I spent a lot of time on getting these answers.

[brassherald]

You forgot not to include two letters in your alphabet, Harambey.

I and O are unused, so your division should be by 24 rather than 26.

[StrangerCoug]

brassherald is closer to the answer I get for the last plate on January 5, 2018 than Harambey180 is.

[Harambey180]

First one is AFF-125 then.

[Harambey180]

Second one is MJD-531 then.