>tfw can't wrap my head around pigeonhole principle applied

post examples

>>9154492
Suppose that [math]a_{o}, a_{1}, a_{2}, \dots , a_{n} \in \mathbb{Z}[/math] are integers. Show that the product
[eqn]\prod_{0\leq i < j \leq n} (a_{j}-a_{i})[/eqn]
is divisible by [math]n![/math]

>>9154503
That product always equals 0, ergo it is divisible by everything, in particular by n!

This has been a PSA by the "Write your math right you fucking retard" foundation

>>9154503
I assume it is assumed that the [math]a_i[/math] are pairwise distinct?

>>9154503
You want to show that all the factors of [math]n![/math] appear in the product. If the product is not 0 then all the [math]a_i[/math] are different (otherwise it is trivial). The way the sum is computed implies there are exactly [math]{n \choose 2}[/math] different factors, which is greater than [math]n[/math], and we are finished. This works when [math]a_i \gq 0[/math] but it should be easily shown for the case [math]\mathbb{Z}[/math].

>>9154530
>and we are finished
why?

Also, there are [math]{n+1 \choose 2}[/math] factors in the product.

>>9154562
Yeah I noticed my proof lacks something... At least [math]a_n\geq n[/math] so maybe we can show you have to hit a lot of factors.

>>9154503
This is barely a pigeonhole problem. To solve it simply partition that product cleverly to be able to apply an argument by induction. Do the base case for n=2 instead of n=1 so you can see why the theorem is true (the case n=1 is degenerate and doesn't tell you much). After that you need to use the pigeonhole principle to be able to establish a certain congruence in the induction step. Then play around with that congruence and the proof is done.

I'd say this problem is intermediate at best and is more about induction than pigeonhole. Anyway, thank you. I'm going to steal this for my next class. I was having a hard time finding a second congruences problem that wasn't too hard or too easy.

>>9154530

There are (n choose 2) factors, but that doesn't mean they're unique, even the a_i's are equal. Consider (2, 5) and (3, 6).

>>9154565

Well [math]a_n \geq n[/math] if they're positive integers, since otherwise you have 2 that are the same, thus the product is 0.

>>9154481

You can do it anon! I use it to assure myself of the existence of (probably) at least one matching pair of wearable socks all the time, especially after a fresh batch of laundry has been done! :^D

>mfw the wiki treatment leads off with sock-picking

>tfw math is practical

>>9155338

And this especially because, as a lazy low-level mathematician, I am frequently obliged to plunge into a hamper of clean yet unfolded and wrinkly laundry, in order to construct at least one matching pair of socks.