Math and Logic Puzzles: Redux

[biancospino]

Spoiler:

Thou you were actually on the right path. Proving that you were is the difficult part of course

[implosion]

Spoiler:

So then at each step, pick a neck to chop from that is at the highest level from the root possible, and among such heads, choose one that has the highest number of sibling heads (heads that extend from the same immediate root as it). Chopping a head at level l with s siblings will always reduce the number of s-sibling l-level roots by 1 because the replication can make (s-1)-sibling l-level roots by copying that part of the tree, but can't make anything else at level l or higher because the replication signal goes downward. Eventually all s-sibling l-level roots will be gone, and next are all the (still finitely many) (s-1)-sibling l-level roots, and so on until everything at level l is gone, etc. At each step more future work will appear but nothing that's already been dealt with can spring up again. You can't put an a priori bound on how long it'll take unless you can put an a priori bound on how many times a tree might replicate (which you don't need to do), but every step is guaranteed to make forward progress at its given (s, l) ordered pair, there are only ever finitely many such ordered pairs to deal with (because each replication is finite), and so each such ordered pair will take finite time to deal with.

In fact I

think

this can be turned into an even stronger conjecture, which is that actually

any

order that HyperErcules cuts the heads will eventually kill the hydra, even if he tries not to.The argument would be similar, that making a cut anywhere makes progress on that (s, l) subproblem, meaning that

eventually

you'll solve the (s, l) subproblem and everything below it, which will force you to make a cut at a higher (s, l) subproblem and make progress there. So eventually you'll have to make "actual" progress by cutting at the highest level problem.

[biancospino]

Spoiler:

That is actually not correct since this may happen:
radix->W->X -> Y,Z; each of Y,Z attached to 3 heads
Cutting one of those heads, say above Y, will indeed not allow X to sprout any new (3,4)-heads; however when the signal travels X->W, it will cause W to copy the whole subtree with radix W, which includes Z->(3 heads); and each replication will so produce three new (3,4)-heads

Spoiler:

however, this strategy does indeed work. Your even stronger conjecture is also correct!

[DeathRowKitty]

I'm kinda confused tbh because from the clarification it seemed as though this was a version in which the answer was rather trivially that you can't always kill the hydra rather than the usual hydras in which the answer was what implosion said and the intended solution

uses ordinals

. And that seemed weird because I wasn't sure who the intended audience could possibly be. People who already knew enough to know how and why the hydra would normally get slain but who would get tripped up by a trivial version in which none of that applied?? But then if invisibility was on the right track I assume the answer is the usual expected thing, in which case I think I still don't understand the regeneration rule for this one

pedit: started making this post before the previous one was made so it doesn't take that post into account

[biancospino]

I'm kinda confused tbh because from the clarification it seemed as though this was a version in which the answer was rather trivially that you can't always kill the hydra rather than the usual hydras in which the answer was what implosion said and the intended solution

uses ordinals

. And that seemed weird because I wasn't sure who the intended audience could possibly be. People who already knew enough to know how and why the hydra would normally get slain but who would get tripped up by a trivial version in which none of that applied?? But then if invisibility was on the right track I assume the answer is the usual expected thing, in which case I think I still don't understand the regeneration rule for this one

pedit: started making this post before the previous one was made so it doesn't take that post into account

Frankly it's plausible that we're thinking of the same replication rule and I'm just dogshit at explaining it

[biancospino]

I've made a picture on a piece of paper, maybe it's more clear. Necks marked with a ~ are new necks, the downward arrow marks the signal, the cross marks the cut neck

[DeathRowKitty]

I'm kinda confused tbh because from the clarification it seemed as though this was a version in which the answer was rather trivially that you can't always kill the hydra rather than the usual hydras in which the answer was what implosion said and the intended solution

uses ordinals

. And that seemed weird because I wasn't sure who the intended audience could possibly be. People who already knew enough to know how and why the hydra would normally get slain but who would get tripped up by a trivial version in which none of that applied?? But then if invisibility was on the right track I assume the answer is the usual expected thing, in which case I think I still don't understand the regeneration rule for this one

pedit: started making this post before the previous one was made so it doesn't take that post into account

Frankly it's plausible that we're thinking of the same replication rule and I'm just dogshit at explaining it

Now that I've seen your diagram and looked back at what you said previously, it seems that actually I just can't read perfectly clear explanations. Oops! Thanks for the clarification

[StrangerCoug]

Here come the sudoku puzzles again, and this one should be easy:

8			9	6
	1		4			6
5		6			3			4
						5	3	7
4								8
1	3	5
6			3			9		5
		3			1		4
				2	6			1

[biancospino]

Spoiler:

8	4	2	9	6	7	1	5	3
3	1	7	4	5	8	6	9	2
5	9	6	2	1	3	7	8	4
2	6	8	1	4	9	5	3	7
4	7	9	6	3	5	2	1	8
1	3	5	7	8	2	4	6	9
6	8	1	3	7	4	9	2	5
7	2	3	5	9	1	8	4	6
9	5	4	8	2	6	3	7	1

[StrangerCoug]

Spoiler:

8	4	2	9	6	7	1	5	3
3	1	7	4	5	8	6	9	2
5	9	6	2	1	3	7	8	4
2	6	8	1	4	9	5	3	7
4	7	9	6	3	5	2	1	8
1	3	5	7	8	2	4	6	9
6	8	1	3	7	4	9	2	5
7	2	3	5	9	1	8	4	6
9	5	4	8	2	6	3	7	1

That is correct

[StrangerCoug]

Another one that should be easy:

		1			7		5
7					1	6
3			8		2		9
	3	2				5	1
	5	6				4	2
	4		6		5			3
		8	3					5
	2		1			8

Yes, the middle row, column, and region are all supposed to be empty

[StrangerCoug]

Or, if you prefer a different kind of puzzle, have a cryptoquote to solve:

AQUM ITW PMTOJ JN FM AQXMK, TOK ZVYQNWQJG PVWJ FM CMBJ TAQXM. NOM PVWJ OMXMY, UNY ISTJMXMY YMTWNO, JVYO SQW FTZC NO AQUM. —MAMTONY YNNWMXMAJ

[Aisa]

Spoiler: sudoku

2		1			7		5
7					1	6		2
3	6		8		2		9	1
	3	2				5	1
	1	7	2	5
	5	6		1		4	2
1	4	9	6	8	5	2	7	3
6	7	8	3	2		1		5
5	2	3	1	7		8

I will continue to edit this until either I finish it or I get home

I got home first. Maybe I will finish this tomorrow. Maybe it will be incomplete forever.

[StrangerCoug]

Spoiler: sudoku

2		1			7		5
7					1	6		2
3	6		8		2		9	1
	3	2				5	1
	1	7	2	5
	5	6		1		4	2
1	4	9	6	8	5	2	7	3
6	7	8	3	2		1		5
5	2	3	1	7		8

I will continue to edit this until either I finish it or I get home

I got home first. Maybe I will finish this tomorrow. Maybe it will be incomplete forever.

Spoiler:

What you have so far is correct. Keep going

[Something_Smart]

Or, if you prefer a different kind of puzzle, have a cryptoquote to solve:

AQUM ITW PMTOJ JN FM AQXMK, TOK ZVYQNWQJG PVWJ FM CMBJ TAQXM. NOM PVWJ OMXMY, UNY ISTJMXMY YMTWNO, JVYO SQW FTZC NO AQUM. —MAMTONY YNNWMXMAJ

Spoiler:

Life was meant to be lived, and curiosity must be kept alive. One must never, for whatever reason, turn his back on life. -Eleanor Roosevelt

I don't know much about cryptogram techniques, but with this one I guessed that "JN FM" was "TO BE", then saw that would make the author's name "E_E..." which immediately broke the whole thing open.

[StrangerCoug]

Or, if you prefer a different kind of puzzle, have a cryptoquote to solve:

AQUM ITW PMTOJ JN FM AQXMK, TOK ZVYQNWQJG PVWJ FM CMBJ TAQXM. NOM PVWJ OMXMY, UNY ISTJMXMY YMTWNO, JVYO SQW FTZC NO AQUM. —MAMTONY YNNWMXMAJ

Spoiler:

Life was meant to be lived, and curiosity must be kept alive. One must never, for whatever reason, turn his back on life. -Eleanor Roosevelt

I don't know much about cryptogram techniques, but with this one I guessed that "JN FM" was "TO BE", then saw that would make the author's name "E_E..." which immediately broke the whole thing open.

That is correct

[Charles510]

When Peter and Bill ran a 100-meter race, Peter won by five meters. To give Bill a chance to win, they raced again, but this time Peter started five meters behind the starting line.

Each man ran the race at the same speed as in the first race.

What were the results of the second race?

[biancospino]

Peter won.

Bill's speed is 95/100 of that of Peter; so by the time Peter runs 105 meters, Bill runs
105*95/100<100 meters
(since 105/100<100/95).

For the race to be fair, Peter would need to accept an handicap of
(100/95*100m)-100m ~ 5.26m
(Or let Bill start 5m past the line)

[Who]

A puzzle which everyone here has probably already seen the base version of, but which has many variants which some people may not have seen:
There are 100 mathematicians in a prison. There's a room in the prison with a light switch, which starts switched off. Every day (They all have calendars and know what day it is) the warden chooses a (not necessarily new) mathematician uniformly at random and takes them into the room, and the mathematician sees the state of the light and may switch it, then they are returned to their room. Nobody other than the mathematicians can touch the light switch. If at any point, a mathematician correctly says "Every prisoner has been in this room at least once", they are all set free. If the mathematician is incorrect, they're all killed (So make sure that the probability of making a wrong declaration is exactly 0). In advance they're all allowed to agree on a strategy, give a strategy which will set them free. (Only important thing is that they end up free eventually with probability 1, how long it takes doesn't matter)

Variants (If you haven't solved the base variant don't look at them because they contain clues as to how to do it):

Spoiler: Easy variant

They have no information at all about what day it is the only information is how many times they've been to the room and what the state of the light has been each time), AND the starting state of the light is not known

Spoiler: More challenging variants

(All of these are separate)
The mathematicians now have families they want to get back to and want to minimize the amount of time they spend in prison. Find a solution which gets them out quickly on average/very probably. Also the same problem but N prisoners instead of 100, though I'm not sure how much of a difference that makes to the solution.

As soon as a prisoner correctly declares that everyone has been in the room, that prisoner (and only that prisoner) is set free. Taken out of the pool of prisoners who might visit the room in the future. Find a way to free everyone.

The warden cheats: If a prisoner exits the room with the light on he switches it off with some fixed probability p. The warden never switches an off light on. Also they can't count days like in the easy variant.

They can't count days like in the easy variant AND the mathematicians are all identical robots who must execute identical programs. The robots do have access to random number generators.

Same as the last one but instead of being taken at random the warden decides adversarially at the beginning which order to take them in, but this order must have each one must visit infinitely many times, and also the robots no longer have access to random number generators. I'm pretty sure this is impossible but can't prove it. (All the other variants are definitely possible)

[tris]

Spoiler:

assign a schedule of mathematicians, so they each get a day in each period of 100 days. if the mathematician enters the room on their day, they turn the light on. and the next one turns it off.

eventually

someone will have been after every other mathematician on their day. its going to take fucking forever tho

[tris]

probably much more efficient ways of doing that

[Who]

Spoiler:

assign a schedule of mathematicians, so they each get a day in each period of 100 days. if the mathematician enters the room on their day, they turn the light on. and the next one turns it off.

eventually

someone will have been after every other mathematician on their day. its going to take fucking forever tho

That works. I think it's the slowest strategy I know of, but speed was only required in one variant so it is 100% valid in the base variant. Testing it once it took about 3 million days, which is about 8,000 years. Testing it 100 times and taking an average is rather slow, but still seems to take on average around 3 million, but it seems to have a pretty high variability and I'd need more tests to be certain. I'm too lazy to calculate/estimate the expected value of number of days it will take by hand. There's a relatively simple modification you can make to make it take around 80,000-100,000 days, or about

30 years

(Edit: Missed a 0, it's actually 300 years), but even with the speedup it takes more than 1,000,000 days reasonably frequently. Even with the speedup it's still the slowest strategy I know of. (Not counting anything which is intentionally slow)

Since that was the first strategy you came up with the "easy" variant might not be so easy, I labelled it as "easy" expecting most people to come up with a different strategy first.

[tris]

hehe

[WeabooBob455]

probably much more efficient ways of doing that

Yes, there are. But this one is efficient, even if it's slow.

[tris]

Spoiler: easy variant

one person turns on the light every time they enter a dark room. everyone else turns off the light if it's on two times and then leaves it alone. once the one who turns on has seen the light go off 199 times, they know everyone has been in the room.