[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 710 KB, 2118x839, day_60.png [View same] [iqdb] [saucenao] [google]
10613291 No.10613291 [Reply] [Original]

[math]
\text{Let }B\text{ be a set of more than }2^{n+1}/n\text{ distinct points with coordinates of the}
\\
\text{form }(\pm 1,\pm 1,\ldots,\pm 1)\text{ in }n\text{-dimensional space with }n\geq 3\text{. Show that there are}
\\
\text{three distinct points in }B\text{ which are the vertices of an equilateral triangle.}
[/math]

>> No.10613293

Previous Thread >>10610385

>> No.10613586

there is almost infinite points so therefore the possiblity of there being an equi triangle is exactly 1

>> No.10613680

thinly veiled homework thread of the day

>> No.10613951

>>10613291
Don't put gradients on the backgrounds kudasai.

>> No.10614098

wtf nobody figured this out yet?

>> No.10614105

>>10614098
It's not only combinatorics, but a sock in drawer combinatorics problem.
Miss me with that shit.

>> No.10614120

>combinatorics AND geometry
fucking competition math niggers
cant they just make interesting problems instead of these

>> No.10614136

>>10614120
>implying there's literally any geometry in it

>> No.10614160

The problem says that we are given more than 2^n/n vertices of an n-dimensonal hypercube, and have have to find an equilateral triangle formed by three of them.

For all 2^n vertices consider the number of neighboring vertices that are in B, and take the sum of these numbers. Every vertex in B contributes n to this sum, so we will get n|B|>2*2^n. This means that one of the summands was at least 3.

Three vertices that have a common neighbor form an equilateral triangle.

>> No.10614173

fuck anime

>> No.10614222

>>10614160
This seems correct
well done

>> No.10614322

>>10614160
>Every vertex in B contributes n to this sum
How so? Can it not be that there is some vertex in B that has no neighbors also in B?

>> No.10614593

>>10614322
I misunderstood this at first too.
Let's call that vertex you mentioned v.
Of all the 2^n vertices in the hypercube (not B), n of them have v as a neighbour.
So v contributes n to the total sum.
Same goes for every other vertex in B.

>> No.10614739

>>10614160
I wonder if the bound can be made sharper.
(2^(n+1))/n guarantees the existence of an equilateral triangle whose side length is 2sqrt(2).
Equilateral triangles with side length 2sqrt(2*(n/4)) are most numerous so you might be able to use them to force a better bound.

The number of equilateral triangles with side length 2sqrt(2k) is:
[math]\frac{2^{n-1}}{3} \binom{n}{k\ k\ k\ n-3k}[/math]

>> No.10614746

>>10613291
What math do you even need to solve this shift? I don’t even know where to begin.

>> No.10614754

>>10614746
Apparently just a simple geometry fact about (hyper)cubes, double counting, and the pigeonhole principle.
>>10614160

>> No.10614819

>>10613291
FUCK Reimu

>> No.10615256

>>10614746
Literally the only thing you need to know is the distance formula from linear apgebra.
Well and the pigeon hole principle, but that is intuitive.

>> No.10616709

>>10614819
I'd fuck her alright

>> No.10616802

>>10614746
In an equilateral triangle all sides have the same lengths.
The length of the sides is the distance between the corner points.
The distance between the points is determined by the "edit distance" between the coordinate description between the points.
Therefore if there exist 3 points with pairwise identical edit distance then there exists an equilateral triangle.

Now you just count!