Math and Logic Puzzles: Redux

[Aisa]

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.

[Aisa]

I can do one.

I have two piles of coins that have been flipped to show either heads or tails. The coins are fair, so 1/2 chance of each. The first pile has 101 coins, and the second pile has 100 coins. What is the probability the first pile contains (strictly) more heads than the second pile?

Spoiler: Follow-up question

Can you generalise the result to the case where the coins are unfair and turn up heads with probability p?

[Aisa]

Perfect!

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

Whoops - the answer is I wrote the question at 2 am and didn't realise you'd need to compute Q(n) for general p to get this part. I don't know if there's a nice formula for it (:

[Aisa]

Yeahhh not sure what there is to say except

what is the

hypergeometric function

?? Sorry if you wasted any time on that.

Here is another one.

The following are examples of sets of integers such that their sum is the same as their product:
(2, 2)
(1, 2, 3)
(1, 1, 2, 4)

Find such a set with 2023 elements.

Spoiler: Follow-up question

Are there infinitely many such sets?

[Aisa]

Both the answers look good to me ^^.
I was asking if these sets in were finite in general, without the constraint they have to have 2023 elements, but I think bianco's answer is also correct.

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

[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

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

[Aisa]

Yes!

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

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