Math and Logic Puzzles: Redux

[biancospino]

There's like an 80% chance I've messed some computation up along the line, but the general idea should work.

I write C(a,b) for a!/(b!(a-b)!) for each pair of integers with a>=b.

Suppose first that p was fixed. There are C(2n,n) scenarios in which you get n heads, and so the probability of getting exactly n heads is C(2n,n)p^n(1-p)^n.

Now, since p is extraded in [0,1] uniformly at random, the requested probability is the integral from 0 to 1 of C(2n,n)p^n(1-p)^n dp.

Now, let's compute the integral of p^n(1-p)^n dp between 0 and 1.
By parts, one has that, for a,b positive integers,
\int_0^1[p^a(1-p)^b dp]=
=[p^(a+1)/(a+1)(1-p)^b]|_0^1+\int_0^1[p^(a+1)/(a+1)(1-p)^(b-1)b dp]=
=\int_0^1[p^(a+1)(1-p)^(b-1) dp]b/(a+1)

So, by using this expression n times, one gets that
\int_0^1[p^n(1-p)^n dp]=(n/(n+1))*((n-1)/(n+2))*...*(1/2n)*\int_0^1[p^(2n)dp]
=n!/((2n)!/n!)*(1/(2n+1))=n!^2/(2n+1)!

And so in conclusion the requested probability is
C(2n,n)n!^2/(2n+1)!=((2n)!n!^2)/(n!*n!*(2n+1)!)=

1/(2n+1)

.

[biancospino]

Eh, let's do one.
Suppose there's a plane with 400 seats; all seats are booked, and all passengers are actually going to take the plane.

Passengers board the plane in a random order. The first one sits on the wrong seat (that is, a seat different from the one indicated in their ticket); all subsequent passengers sit on the correct seat if it's not occupied by someone else, and on a random unoccupied seat otherwise.

What is the chance that the last passenger to board will sit on the correct seat?

[biancospino]

Eh, let's do one.
Suppose there's a plane with 400 seats; all seats are booked, and all passengers are actually going to take the plane.

Passengers board the plane in a random order. The first one sits on the wrong seat (that is, a seat different from the one indicated in their ticket); all subsequent passengers sit on the correct seat if it's not occupied by someone else, and on a random unoccupied seat otherwise.

What is the chance that the last passenger to board will sit on the correct seat?

Spoiler:

I think it's very close to 1/2.

The first passenger sets off a "chain" of passengers sitting in the wrong seats. For example, if they sit on passenger #3's seat, then #3 might sit in #17's seat, and so on. The chain only stops when one of the passengers closes the loop by randomly sitting in #1's seat, at which point everyone remaining can sit in their assigned seats.

Two possibilities:
1. If someone sits on #1's seat before someone sits on #400's seat, then #400 will sit on the correct seat.
2. If someone sits on #400's seat before someone sits on #1's seat, then #400 will be displaced.

There is a 1/399 chance that #1 happened to sit on passenger #400's seat, displacing #400.

Conditional on this not happening, the probabilities of any displaced passenger in the chain randomly sitting in #1's seat and in #400's seat are the same.

So the probability is (398/399) * (1/2) = 0.4987...

Or (1/2) * ((n-2)/(n-1)) for generic n.

Becomes exactly 1/2 if the first passenger chooses their seat uniformly at random from all seats on the plane, including their assigned seat.

That is correct

[biancospino]

I'm answering the "fair coins" situatiom for now.

Let Q(n) be the chance that, by throwing n coins twice, you get the same number of heads.

Let R(n) be the chance that, by throwing n coins twice, you get more coins the first time. Now, R(n)=(1-Q(n))/2, since provided you get different numbers, which is larger is equally probable.

Let in the end P(n) be the chance that, by throwing n+1 coins, you get more heads than by throwing another n coins. Clearly P(n) is the chance that the first coin is head, times Q(n)+R(n); or that the first coin is tail, times R(n). So,
P(n)=(Q(n)+(1-Q(n))/2)/2+(1-Q(n))/4
=Q(n)/2+1/4-Q(n)/4+1/4-Q(n)/4
=1/2

---

If p!=1/2, one gets
P(n)=(Q(n)+(1-Q(n))/2)p+((1-Q(n))/2)(1-p)
=Q(n)*(2p-1)/2+1/2

But atm idk how to compute Q(n) nicely for general p.

[biancospino]

I've asked wolfram and it appears that the formula is really not that nice lol. Clearly one has that, for fixed n, Q(n;p) must be an even polinomial of degree 2n in (p-1/2) with Q(n;0)=Q(n;1)=1 and Q(n;1/2)=comb(2n,n)/2^(2n) (since Q(n;1/2) is then equal to the chance that there is as many heads in the first pile as

tails

in the second (equal) pile, which happens iff there are n heads total), but other than that it seems real ugly

[biancospino]

Unless you're asking if there are infinitely many such sets with exactly 2023 elements, in which case the answer is no (if we're talking positive integers. Otherwise (n,-n, 0 2021 times) always works).

For suppose that A is such (multi)set, and let M=max(A). Note that, for each a>b>1 and 0<c<b, one has (a+c)-ac>(a+b)-ab; so by using this repeatedly and replacing each element of A that is greater than 1 with 1, except for the (possibly not strictly) second-largest element with 2 and keeping the largest unaltered (N.B.: since M+2022>M always, there must exist an element of A, other than M, greater than one), one gets
M+2+2021>=2M
M<=2023

And so, there clearly are at most 2023^2023 such sets. Note that this upper limit is very clearly very generous (and the actual number is surely way, way lower), but it's finite.

[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?

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

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

[biancospino]

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

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

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

[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

[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

[biancospino]

Spoiler:

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

[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!

[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

[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

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