Math and Logic Puzzles: Redux

[biancospino]

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?

[Aisa]

Hint?
So far I think I have:

Spoiler:

N=3 is always a win for the second player (Bob).
N=4 is always a win for the first player (Alice), as she can reduce the game to N=3 while making Bob start first.

Also idk sometimes the piles have an odd number of coins in total, sometimes an even number and maybe that's, like, relevant somehow?

[biancospino]

Spoiler: hint

It may help to try to solve a slightly more general problem first: starting from a position with a pile of n_1 coins, a pile of n_2 coins... a pile of n_m coins, does the starting player win? To solve that, try to do some stuff in base two.

Spoiler: hint 2

It may help to consider the map from omega to 2^omega given by the expansion in base two and the group operation on (F_2)^omega given by the elementwise sum

[biancospino]

Also idk sometimes the piles have an odd number of coins in total, sometimes an even number and maybe that's, like, relevant somehow?

Parity is indeed relevant, but looking at parity it's not enough

[biancospino]

Very heavy hint:

Spoiler:

To determine who has a winning strategy from a given position, first compute the bitwise XOR (that is, the "sum in base two with no carryout") of the numbers of coins in each pile. The first player always wins if and only if this XOR is not zero.

[Aisa]

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]

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 this

literally

tells 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 I

still

couldn'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

https://en.wikipedia.org/wiki/Nim

Ok so the solution is that

Spoiler:

first player wins unless N modulo 4 is 3.

Proof:
Use the proof on Wikipedia to prove the Very Heavy Hint. Using the Very Heavy Hint, we just need to show that bitwise XOR of (binary representation of 1, 2, ..., N) is 0 if and only if N modulo 4 is 3.
A formal proof can be obtained e.g. by writing N = 4M + r and using induction on M; this is essentially because bitwise XOR of (...00, ...01, ...10, ...11) is zero.

but the hints and wikipedia definitely did all the heavy lifting

[Aisa]

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 I

solved

bianco's problem would be, uh, very very generous so I feel like it's still open to attempts that don't consult Wikipedia

[biancospino]

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...)

[biancospino]

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

Yes please

[biancospino]

Btw, it could be proved much more easily than what the wiki does.

Spoiler:

It suffices to show that (1) moving from a position with a XOR of 0 always produces a position with a nonzero XOR; and (2) from a position with a nonzero XOR, one can always move to a position with a zero XOR.

(1) is obvious (in fact, the new XOR will have ones in all positions in base 2 were the touched pile will differ from the previous value).

For (2), just note that there must be a pile whose base 2 representation has a one in the same position as the most significative one in the XOR. Just note that, by taking the XOR of that pile and of the (old) XOR, you find a smaller number, and so may move there; this does the trick.

[Aisa]

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...)

Yeah it's not really your fault, lol

[Aisa]

Prove that in any sequence of n^2 + 1 real numbers there is an increasing subsequence of length n+1 or a decreasing subsequence of length n+1.

Spoiler: Explanation of what an "increasing subsequence" is

This is a sequence:
3, 11, 7, 5, 1, 10, 2, 18, 17, 20

When you pick out some numbers from the sequence, keeping them in the order they were in in the original sequence, it's called a sub-sequence. All these are subsequences of the above sequence:
3, 11, 7
11, 7, 5, 20
3, 7, 10, 18, 20

The last of these also happens to be increasing, i.e. each number in the subsequence is greater than or equal to the previous number.

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!

[biancospino]

I assume that "increasing" means "weakly increasing"?

[Aisa]

Yes!

[DeathRowKitty]

Prove that in any sequence of n^2 + 1 real numbers there is an increasing subsequence of length n+1 or a decreasing subsequence of length n+1.

Spoiler:

Let A = {a_i}, i=0,1,...,n²+1 be the sequence. Let f(a_k) denote the length of the longest increasing subsequence of A ending with a_k. If there is some k such that f(a_k) = n+1, we've found an increasing subsequence of length n+1. If no such k exists, then, by pigeonhole, there must be some c such that f(a_i)=c for at least n+1 distinct values of i and those n+1 such a_i form a decreasing subsequence of length n+1.

Easier and a different type of problem:

Suppose you have 3 spherical marbles with centers A, B, C resting on a flat table, each touching the other two marbles. Let A', B', C' be the points at which these marbles touch the surface. If each marble has an integer radius and A'B'C' is a right triangle with integer sides, find the minimum possible semiperimeter of ABC.

[Aisa]

Prove that in any sequence of n^2 + 1 real numbers there is an increasing subsequence of length n+1 or a decreasing subsequence of length n+1.

Spoiler:

Let A = {a_i}, i=0,1,...,n²+1 be the sequence. Let f(a_k) denote the length of the longest increasing subsequence of A ending with a_k. If there is some k such that f(a_k) = n+1, we've found an increasing subsequence of length n+1. If no such k exists, then, by pigeonhole, there must be some c such that f(a_i)=c for at least n+1 distinct values of i and those n+1 such a_i form a decreasing subsequence of length n+1.

Very neat.

[biancospino]

Easier and a different type of problem:

Suppose you have 3 spherical marbles with centers A, B, C resting on a flat table, each touching the other two marbles. Let A', B', C' be the points at which these marbles touch the surface. If each marble has an integer radius and A'B'C' is a right triangle with integer sides, find the minimum possible semiperimeter of ABC.

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')²=(a+b)²-(a-b)²=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=x², b=y², c=z². Since ab,bc,ca is a pitagorean triple, one gets (possibly rearranging the order of a,b,c) that
x²y²+y²z²=x²z² ==> (y/x)²+(y/z)²=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
y²+x²+z²=12²+15²+20²=

769

so we clearly see that the minimum must be found amongst the triples (p<q<r) with r<28 (since 28²>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.

[DeathRowKitty]

yeps!

[biancospino]

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 the

red 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 ...

[DeathRowKitty]

Can you clarify exactly what replicates? I think different interpretations give different answers here

[biancospino]

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 subtree

[Invisibility]

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.

[biancospino]

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 the

whole

subtree 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 C

[Invisibility]

oooh right right