Puzzler's Edge

It's time to solve more puzzles with friends!

Enjoy the puzzles in this thread!! However, please put solutions in spoilers to respect other puzzlers.

Feel free to provide more puzzles to populate the puzzlecosystem!

Here is PUZZLE 1:

You are the king of shapeworld, which boasts a population of 1 million shapes.
Unfortunately, the gods demand that you must sacrifice 1000 shapes to appease their wrath.

Being the king of shapeworld, you have the ability to immediately count your population. Shapeworld has:
300 thousand triangles,
200 thousand squares,
350 thousand pentagons,
100 thousand hexagons,
48 thousand kites,
and 2 thousand trapisboigles, an exotic shape.

However, unknown to you, the only sacrifice that will appease the gods is thus:

500 triangles,
50 squares,
50 pentagons,
100 hexagons,
290 kites,
10 trapisboigles,

What's the probability that the king of shapeworld will appease the gods, if the king of shapeworld sacrifices according to a random lottery?

SpoilerShow

I'm going to make a simplifying assumption that sampling with and without replacement are similar, as there is a ∏_n=999001^n=1000000 / 1000000^1000≈.6067 chance of no repeats, and any repeats will likely not impact the size of the sample, so the binomial distribution is a fair assumption.

For triangles, there is a 300/1000=.3 chance of a success, so the odds of getting 500 successes in 1000 trials is 3.479×10^-40.
For the squares, given 500 triangles, there is a 200/700=.28 chance of a success, so the odds of getting 50 successes in 500 trials is 2.532×10^-24.
For the pentagons, given the others matched, there is a 350/500=.7 chance of a success, so the odds of getting 50 successes in 450 trials is 1.129×10^-150.
For the hexagons, given the others matched, there is a 100/150=.67 chance of a success, so the odds of getting 100 successes in 400 trials is 4.028×10^-65.
For the kites, given the others matched, there is a 48/50=.96 chance of a success, so the odds of getting 290 successes in 300 trials is .105892.
These are all independent, so the odds are all those terms multiplied together, or approximately 4.24×10^-279

---

EDIT:
Well, guess who looked up the multivariate hypergeometric distribution. It's surprisingly easier than what I thought it would be. It's simply P(X_i=x_i)=∏(n_iCx_i)/(nCx). Which I can easily plug into Wolfram Alpha and get 1.80886819768606391029406770736646900211436086948272×10^-269. So I was off by a factor of 10 billion. Whoops. Granted, still ridiculously unlikely, but not as much. So yes, that's much better than what you had before.

SpoilerShow

Seven. My answer is seven.

Great job, everyone!

Now we have another puzzle.

Puzzle 2:

Formalities aside, let's get started.

You know about that whole "adding" thing - you can put 2 and 2 together to make 4.
But when you add tons, you just say how many times you add. Then you can say "x times 2."
When you just have these two, it's easy to say how you can add in weird amounts - for example, adding 1.2 times, by using multiplication.

Then comes along multiplying in all sorts of amounts - exponentiation. Euler even made a way to multiply complex amounts of times but we won't really care about that so much here.

What we don't know is this -
Can you exponentiate in non-integerial amounts?

As a preliminary,
Is there a function A(x) such that for any real x, A(A(x))=exp(x)?

In bigger math words,

SpoilerShow

Can iterated exponentiation be analytically extended to the real numbers?

If not, does there exist a meromorphic function everywhere differentiable except at its poles that is equal to iterated exponentiation in integer domains?

(Iterated exponentiation defined here is base first: For example,
If we call this function "Tetration," then let us define "a tetrated to b" as:
a^(a^(a^(a^(...such that there are b amount of a in this power tower...))))

Admittingly, after a point, the power ceases to matter - the base, whether real or complex, generates a surface which determines the movement of the exponent in some domain. Through investigating this structure as a conformal map I hope to have some advancement.

No..? I'm going to go with no.

Definitely. My uncle works at math and says it's true

Definitely. My uncle works at math and says it's true

dang

Given an arbitrary rational number in decimal form, how can you quickly determine the denominator of that number? (quickly as in something that does not on really large numbers or factorization, and preferably something that does not use iteration or recursion.)

Bonus points (and the problem I'm actually trying to solve): How can you make a graphing calculator (desmos.com in particular) calculate the LCD of two fractions when the LCM function is only defined on the integers?


_{yes i know this is a simple problem but i'm bad at number theory. this counts as number theory, right?}

Oh, with regards to A(A(x))=a^x (which I'm calling the square hyperroot), I put in the simplest case of y=x^x to Wolfram Alpha, told it to solve for x, and got this mess. So even in the simplest possible situation, I'm not sure fractional tetration makes any sense at all. Especially since, as far as I understand it, the Lambert W-function seems to have multiple outputs for part of its domain.

(although it does somehow give the right answer for e^e=x^x. hmm.)

I would probably suggest using something that isn't desmos

Ok let's try something.

You (probably) don't want to graph every single rational number, desmos will not be happy with you if you try to do that.

However, if you're willing to settle for some loss of quality, you can consider all fractions of form 1/N, 2/N, 3/N, etc. with the following:

N/gcd(mod(floor(N*x),N),N) = D

This extracts the denominator. The fraction itself can be extracted from floor(N*x)/N = F. Thus you can extract the numerator N = F*D.

You probably want to set N to some highly factorable number like 30 or 60 or 120 or 210 or something. (You'll quickly see that setting N to too large of a number will not make desmos happy, which is why over the reals (or a floating point approximation as desmos uses) this isn't very feasible)

If you're doing stuff to the fractions, you'll probably have do manual rational arithmetic to get your desired results. Like A/B+C/D = (AD+BC)/BD and the like. But since you have the numerators and denominators of both in simplest form this should not be too bad.

I'm going to use python for this project eventually, I just like using desmos for quick and dirty visualizations. Then I inevitably get sidetracked by something like this, where the simplest part of the problem is difficult or impossible to express in this medium, and ends up as a problem of its own.

When you use Python (or any other respectable programming language), there are two iterative ways that you can use to approximate any real to a decently close fraction with low-ish denominators, terminating the process once you have sufficiently good approximations. (Once again if you're going to graph things on the real line and you want fractions, this is a necessary tradeoff.)

1) Continued fractions

Given N, keep taking the fractional part, then taking the reciprocal, etc. constructing a continued fraction expansion. You can choose to stop after some number of terms and then reconstruct your desired fraction. This converges pretty rapidly, I think. On the other hand, you're going to have to divide floats and thus you may encounter rounding errors.

2) Farey sequences

It's also iterative, in the following algorithm:

I'll assume your real number is between 0 and 1. Consider 0/1 and 1/1. Next, we "binary search" - however, instead of taking the midpoint of the two bound fractions, we instead take the mediant. That is to say, given a/b and c/d, your divider is (a+c)/(b+d).

That this process will eventually stumble upon every single exact rational is an exercise left to the reader. You can also terminate when the bounds are say within some epsilon apart.

Plus side: you only have to worry about float comparisons, so errors will not propagate in this algorithm.

Minus side: well... let's see

An example. So suppose we want to approximate pi-3=0.1415926535...

0/1 1/1
divider 1/2>x, so take left half
0/1 1/2
divider 1/3>x, so take left half
0/1 1/3
divider 1/4>x, so take left half
0/1 1/4
divider 1/5>x, so take left half
0/1 1/5
divider 1/6>x, so take left half
0/1 1/6
divider 1/7>x, so take left half
0/1 1/7
divider 1/8<x, so take right half
1/8 1/7
divider 2/15<x, so take right half
2/15 1/7
divider 3/22<x, so take right half
3/22 1/7
divider 4/29<x, so take right half
4/29 1/7
divider 5/36<x
5/36 1/7
6/43 1/7
7/50 1/7
8/57 1/7
9/64 1/7
10/71 1/7
11/78 1/7
12/85 1/7
13/92 1/7
14/99 1/7
15/106 1/7
15/106 16/113
...

So incidentally this touches both the approximations 22/7 and 355/113. That's not a coincidence.

On the other hand yeah this converges pretty slowly. You're basically doing Euclidean algorithm by individually subtracting each term, in some sense. Continued fractions shortcuts this.

Yeah, I knew how to do that. That's probably how I'm going to do it when I get the rest of the ideas fleshed out enough to write it in code.

edit: here we go:
https://www.desmos.com/calculator/yq2swud4q7

Here's an interesting one I stumbled across while doing computer graphics:

How many Eulerian paths are needed to cover all the edges of a cube? (They need not be Eulerian cycles.)

Or, for those unfamiliar with graph theory, if you are walking along the edges of a cube, but you cannot revisit any edges and must restart at a different vertex whenever you have nowhere to go, what is the minimum number of times you have to restart?

Prove your answer.

Bonus points: Generalize your answer to a formula for all hypercubes of an odd dimension. (All even-dimensional ones only require one path)