Math and Logic Puzzles: Redux
- biancospino
-
biancospino he/shecompulsive complex Inventor
- biancospino
he/she- compulsive complex Inventor
- compulsive complex Inventor
- Posts: 2259
- Joined: October 18, 2022
- Pronoun: he/she
- Location: UTC+1
Alright, another one.
Alice and Bob are playing a game. There are N piles of coins (with N>=3), the first with 1 coin, the second with 2 coins, the third with 3 coins etcetera. Alice starts by removing any (positive) number of coins from a single pile; then Bob does the same. They keep taking turns until someone takes the last coins, and that player wins.
For which values of N does Alice have a winning strategy?Now modding- Aisa
-
Aisa she/her, they/themMafia Scum
- Aisa
she/her, they/them- Mafia Scum
- Mafia Scum
- Posts: 2838
- Joined: December 19, 2013
- Pronoun: she/her, they/them
- Location: Europe
- biancospino
-
biancospino he/shecompulsive complex Inventor
- biancospino
he/she- compulsive complex Inventor
- compulsive complex Inventor
- Posts: 2259
- Joined: October 18, 2022
- Pronoun: he/she
- Location: UTC+1
Spoiler: hint
Spoiler: hint 2Now modding- biancospino
-
biancospino he/shecompulsive complex Inventor
- biancospino
he/she- compulsive complex Inventor
- compulsive complex Inventor
- Posts: 2259
- Joined: October 18, 2022
- Pronoun: he/she
- Location: UTC+1
Parity is indeed relevant, but looking at parity it's not enoughAlso idk sometimes the piles have an odd number of coins in total, sometimes an even number and maybe that's, like, relevant somehow?Now modding- biancospino
-
biancospino he/shecompulsive complex Inventor
- biancospino
he/she- compulsive complex Inventor
- compulsive complex Inventor
- Posts: 2259
- Joined: October 18, 2022
- Pronoun: he/she
- Location: UTC+1
Very heavy hint:
Spoiler:Now modding- Aisa
-
Aisa she/her, they/themMafia Scum
- Aisa
she/her, they/them- Mafia Scum
- Mafia Scum
- Posts: 2838
- Joined: December 19, 2013
- Pronoun: she/her, they/them
- Location: Europe
I haven't forgotten about this, just haven't sat down to crack it yet. But also anyone else feel free to give it a try!- Aisa
-
Aisa she/her, they/themMafia Scum
- Aisa
she/her, they/them- Mafia Scum
- Mafia Scum
- Posts: 2838
- Joined: December 19, 2013
- Pronoun: she/her, they/them
- Location: Europe
How this went:
I looked at your first hint and was like "ok! This seems pretty helpful".
Couldn't solve the problem.
Then I looked at your second hint and was like "hmm thisliterallytells me the construction I need to solve this, there's no way I don't solve this now".
Still couldn't solve it.
Then I looked at your very heavy hint and thought "ok I went too far, this literally says what the solution is, should have stuck it out with two hints. Ah well, whatever, I should be able to construct a proof now".
But Istillcouldn't find the optimal strategy!!
Then I asked my friends Google and Wikipedia who finally helped me with the optimal strategy
Spoiler: The wikipedia article
Ok so the solution is that
Spoiler:
but the hints and wikipedia definitely did all the heavy lifting- Aisa
-
Aisa she/her, they/themMafia Scum
- Aisa
she/her, they/them- Mafia Scum
- Mafia Scum
- Posts: 2838
- Joined: December 19, 2013
- Pronoun: she/her, they/them
- Location: Europe
I'm out of fun maths problems I can name off the top of my head but I can probably dig something out if there's interest
Also to say that Isolvedbianco's problem would be, uh, very very generous so I feel like it's still open to attempts that don't consult Wikipedia- biancospino
-
biancospino he/shecompulsive complex Inventor
- biancospino
he/she- compulsive complex Inventor
- compulsive complex Inventor
- Posts: 2259
- Joined: October 18, 2022
- Pronoun: he/she
- Location: UTC+1
This is correct.
Sorry for spoiling it for you (thou proving the Very Heavy Hint was much of the difficulty anyway, so you really spoiled yourself a bit there...)Now modding- biancospino
-
biancospino he/shecompulsive complex Inventor
- biancospino
he/she- compulsive complex Inventor
- compulsive complex Inventor
- Posts: 2259
- Joined: October 18, 2022
- Pronoun: he/she
- Location: UTC+1
Yes pleaseIn post 257, Aisa wrote: I'm out of fun maths problems I can name off the top of my head but I can probably dig something out if there's interestNow modding- biancospino
-
biancospino he/shecompulsive complex Inventor
- biancospino
he/she- compulsive complex Inventor
- compulsive complex Inventor
- Posts: 2259
- Joined: October 18, 2022
- Pronoun: he/she
- Location: UTC+1
Btw, it could be proved much more easily than what the wiki does.
Spoiler:Now modding- Aisa
-
Aisa she/her, they/themMafia Scum
- Aisa
she/her, they/them- Mafia Scum
- Mafia Scum
- Posts: 2838
- Joined: December 19, 2013
- Pronoun: she/her, they/them
- Location: Europe
Yeah it's not really your fault, lolIn post 258, biancospino wrote: This is correct.
Sorry for spoiling it for you (thou proving the Very Heavy Hint was much of the difficulty anyway, so you really spoiled yourself a bit there...)- Aisa
-
Aisa she/her, they/themMafia Scum
- Aisa
she/her, they/them- Mafia Scum
- Mafia Scum
- Posts: 2838
- Joined: December 19, 2013
- Pronoun: she/her, they/them
- Location: Europe
Spoiler: Explanation of what an "increasing subsequence" is
I think this may be a slightly harder problem that the other two I shared. But apparently there are "multiple proofs", maybe there's a really nice way of framing it that makes it simple!Last edited by Aisa on Fri Apr 14, 2023 6:57 am, edited 1 time in total.- biancospino
-
biancospino he/shecompulsive complex Inventor
- biancospino
he/she- compulsive complex Inventor
- compulsive complex Inventor
- Posts: 2259
- Joined: October 18, 2022
- Pronoun: he/she
- Location: UTC+1
I assume that "increasing" means "weakly increasing"?Now modding- Aisa
-
Aisa she/her, they/themMafia Scum
- Aisa
she/her, they/them- Mafia Scum
- Mafia Scum
- Posts: 2838
- Joined: December 19, 2013
- Pronoun: she/her, they/them
- Location: Europe
-
-
DeathRowKitty
- Aisa
-
Aisa she/her, they/themMafia Scum
- Aisa
she/her, they/them- Mafia Scum
- Mafia Scum
- Posts: 2838
- Joined: December 19, 2013
- Pronoun: she/her, they/them
- Location: Europe
Very neat.
- biancospino
-
biancospino he/shecompulsive complex Inventor
- biancospino
he/she- compulsive complex Inventor
- compulsive complex Inventor
- Posts: 2259
- Joined: October 18, 2022
- Pronoun: he/she
- Location: UTC+1
Let a,b,c be the radii of the spheres; we want to minimize a+b+c. Now, one sees that A'B' satisfy
length(A'B')2=(a+b)2-(a-b)2=4ab
so 4ab must be a square, and so ab must also be; analogously, bc and ac are squares. If a is not a square, then there is a prime p so that the highest power of p dividing a is odd; so p must divide both b and c otherwise ab, ac could not be square. But then a,b,c is not minimal, since a/p,b/p,c/p would also work. Then a is a square, and analogously so are b an c; let a=x2, b=y2, c=z2. Since ab,bc,ca is a pitagorean triple, one gets (possibly rearranging the order of a,b,c) that
x2y2+y2z2=x2z2 ==> (y/x)2+(y/z)2=1
The solutions to this are in the form y=lcm(p,q), x=r/p*lcm(p,q), z=r/q*lcm(p,q) for (p<q<r) pytagorean triple, and we can restrict ourselves to primitive ones for minimality. Taking (p,q,r)=(3,4,5) we find
y2+x2+z2=122+152+202=769
so we clearly see that the minimum must be found amongst the triples (p<q<r) with r<28 (since 282>769); but is immediate to verify, just by cheking all such triples (that are only (3, 4, 5), (5, 12, 13), (8, 15, 17) and (7, 24, 25)), that (3,4,5) does indeed realize the minimum.Last edited by biancospino on Wed Apr 26, 2023 2:23 pm, edited 1 time in total.Now modding-
-
DeathRowKitty
- biancospino
-
biancospino he/shecompulsive complex Inventor
- biancospino
he/she- compulsive complex Inventor
- compulsive complex Inventor
- Posts: 2259
- Joined: October 18, 2022
- Pronoun: he/she
- Location: UTC+1
A hyperhydra is a curious beast; it has a great number of necks. Each of those necks may end either in a head, or in a nodule, from which exit one or more necks (i.e. the hyperhydra's necks form an acyclic graph, of which the leaves are the heads. Since it is a finite beast, this tree has a finite number of vertexes).
Whenever a head is cut, a replication message descends down through the synapsis in the necks, always down and never bifurcating; whenever the message passes through a neck, other than the one immediately below the cut head, that neck, and everything attached above it, replicates a great number of times (at least one copy is produced, but the hyperhydra has extreme regenerative powers, so that sometimes it may produce hundreds or thousands of copies!); then all the nodules that are leaves of the new graph become heads.
The skin of the necks is generally too hard to cut, however the skin of the necks attached to a head is soft enough.
Does HyperErcules, tasked with killing a hyperhydra, always have a strategy to do so, regardless of the exact form of the particular hyperhydra? If so, describe one such strategy.
Since the description in words may be a bit confusing, here's a small example with pictures. Suppose you have an hyperhydra with an ending like this:
* **\ | / \|/ * \ / \ / \/ \...
and you cut thered head (*). Then, when the signal goes down to the first neck, you get something like this:
* * * * [there may be \ / \ / many more \/ \/ copies of this!] \ | \ | \ | \ | \ | * \ | / \ | / \|/ \ \...
Then the duplication signal propagates further down the radix in ...Now modding-
-
DeathRowKitty sheFrogshe
- Frog
- Frog
- Posts: 6296
- Joined: June 7, 2009
- Pronoun: she
Can you clarify exactly what replicates? I think different interpretations give different answers here- biancospino
-
biancospino he/shecompulsive complex Inventor
- biancospino
he/she- compulsive complex Inventor
- compulsive complex Inventor
- Posts: 2259
- Joined: October 18, 2022
- Pronoun: he/she
- Location: UTC+1
Whenever the signal passes through a neck (other than the one you've cut), consider the whole subtree whose root is the upper vertex of the neck (the neck you've cut no longer exists). Then, attach to the lower vertex any number of additional necks, and to the other vertex of each such neck attach a copy of that subtreeNow modding- Invisibility
-
Invisibility he or sheJack of All Trades
- Invisibility
he or she- Jack of All Trades
- Jack of All Trades
- Posts: 5911
- Joined: April 17, 2018
- Pronoun: he or she
I think I am just misunderstanding how this works but can HyperErcules not just keep hacking away at the outermost heads until he eliminates all them, then move down and continue chopping away? The hydra is finite, and each head will only grow further down from the head you just chopped off, meaning that, eventually, he'll get down to a point where the signal has nowhere to go.Invisibility is actually AWESOME!- biancospino
-
biancospino he/shecompulsive complex Inventor
- biancospino
he/she- compulsive complex Inventor
- compulsive complex Inventor
- Posts: 2259
- Joined: October 18, 2022
- Pronoun: he/she
- Location: UTC+1
The problem is this may happen: suppose you have X attacked to Y attached to A, B, C, and C is a head. You cut C, then X sprouts N>=1 new necks attacked each to a copy of thewholesubtree Y->A,B ; in particular now you have 2*(N+1) heads at the level were C was, instead of the 3 you had before chopping CNow modding- Invisibility
-
Invisibility he or sheJack of All Trades
- Invisibility
he or she- Jack of All Trades
- Jack of All Trades
- Posts: 5911
- Joined: April 17, 2018
- Pronoun: he or she
- Invisibility
Copyright © MafiaScum. All rights reserved.
- biancospino
- Invisibility
- biancospino
- biancospino
- biancospino
- Aisa
- Aisa
- biancospino
- Aisa
- Aisa
- biancospino
- biancospino
- biancospino
- Aisa
- Aisa
- Aisa
- biancospino
- biancospino
- biancospino
- Aisa
- biancospino