/sci/ - Science & Math » Thread #12339598

154KiB, 1000x1000, gangster-spongebob-by-thehousegiraffe-redbubble-gangster-spongebob-png-1000_1000.jpg

View Same Google iqdb SauceNAO

Anonymous Sat 14 Nov 03:54:52 2020 No.12339598 View Reply Original Report

Quoted By: >>12339755

hey guys so there's this pigeon hole principle problem was wondering if you guys could help. Thanks.

Linda has 5 weeks to prepare for her CSCA67 final. She has compiled 90 practice questions to work on during the course of the 52 days that the course runs. She plans to do at least one question a day. Prove that there exists a span of consecutive days Linda will complete exactly 15 problems.

Anonymous

Anonymous Sat 14 Nov 2020 05:26:02 No.12339755 Report

Quoted By: >>12339811

>>12339598
Let 1 <= N(1) < N(2) < ... < N(52) = 90 denote the total number of problems completed by day d, and let N'(d) = N(d) + 15. Then {N(1),...,N(52)} and {N'(1),...,N'(52)} are 104 numbers <= 105.
If they are not all distinct, then by the pigeonhole principle N(j)=N'(i) for some i,j which yields the desired interval.
Otherwise, let M denote the unique missing number. If we can show that $M\neq 15$ , then N'(1)>15 forces 15 to occur in the {N(d)} series and we are done. So assume for a contradiction that M=15. This forces N(d)=d for d < 15 followed by N(15)=30, and then N(16)=31, ..., N(29)=44, N(30)=60, ..., N(44)=74, N(45)=90 contradicting N(45)<N(52).

Anonymous

Anonymous Sat 14 Nov 2020 05:38:28 No.12339785 Report

Quoted By:

Let 1 <= N(1) < N(2) < ... < N(52) = 90 denote the total number of problems completed by day d, and let N'(d) = N(d) + 15. Then {N(1),...,N(52)} and {N'(1),...,N'(52)} are 104 numbers <= 105.
If they are not all distinct, then by the pigeonhole principle N(j)=N'(i) for some i,j which yields the desired interval.
Otherwise, let M denote the unique missing number, such that at least one of $M \neq 15$ and $M \neq 91$ holds. In the former case, N'(1) > 15 forces N(15)=15 so the desired interval consists of the first 15 days. Dually, in the latter case the last 15 days constitutes the desired interval.

Anonymous

Anonymous Sat 14 Nov 2020 05:51:55 No.12339811 Report

Quoted By:

>>12339755
thanks m8 god bless

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches