Counting 2: the pigeonhole principle

Error

There was an error loading the page.

Contributors

Feedback

From users who are members of Discrete Mathematics :

Daniel Mansfield

said

Needs to be tested

7 years, 7 months ago

History

○

Daniel Mansfield 7 years, 7 months ago

Gave some feedback: Needs to be tested

○

Daniel Mansfield 7 years, 7 months ago

Published this.

○

Daniel Mansfield 7 years, 7 months ago

Created this.

There is only one version of this question that you have access to.

There are 3 other versions that do you not have access to.

Question statement

The pigeonhole principle states that:

If $p$ items are placed into $n$ containers, then there exists a container which has at least $\left\lceil \dfrac{p}{n} \right\rceil$ items.

Recall that the ceiling function $\lceil x\rceil$ is the smallest integer greater than or equal to $x$ . For example $\lceil \var{e0} \rceil = \var{a0}$ .

Give any introductory information the student needs.

			Name	Type	Generated Value

n1	integer	7
p1	integer	12
n2	integer	10
p2	integer	34
a2	integer	4
a1	integer	2
e0	rational	1141/1000
a0	integer	2
n3	integer	6
a3	integer	6
a4	integer	5

Automatically regenerate variables?

Name

Data type

Value

xxxxxxxxxx
 
random(4..9)

JME function reference

Description

Describe what this variable represents, and list any assumptions made about its value.

Can an exam override the value of this variable?

Generated value: `integer`

→ Used by:

This variable doesn't seem to be used anywhere.

Advice

a. $\left\lceil \dfrac{\var{p1}}{\var{n1}}\right\rceil = \var{a1}$ .

Of course, all $\var{p1}$ pigeons could choose to sleep in the same nest. The pigeonhole principle only provides a lower bound on how many pigeons must be in the same nest.

b. $\left\lceil \dfrac{\var{p2}}{\var{n2}}\right\rceil = \var{a2}$ .

c. Writing $p$ for the number of pigeons, by the pigeonhole principle we have $\left\lceil \dfrac{p}{\var{n2}}\right\rceil \geq \var{a4}$ .

Then $\dfrac{p}{\var{n2}} > \var{a4-1}$ , and so $p > {\var{n2}}\times{\var{a4-1}}$ .

Since $p>\var{n2*(a4-1)}$ , the smallest integer value of $p$ is $\var{n2*(a4-1)+1}$ .

d. Writing $n$ for the number of nests, if $\left\lceil \dfrac{\var{p2}}{n}\right\rceil \geq \var{a3}$ ,

then $\dfrac{\var{p2}}{n} > \var{a3-1}$ and so $\dfrac{\var{p2}}{\var{a3-1}} > n$ .

Since $\dfrac{\var{p2}}{\var{a3-1}} = \var{p2/(a3-1)} > n$ , the largest integer value of $n$ is $\var{n3}$ .

Give a worked solution to the whole question.

Use this tab to check that this question works as expected.

There was an error which means the tests can't run:

Part	Test	Passed?
Number entry
Number entry		Hasn't run yet
Number entry
Number entry		Hasn't run yet
Mathematical expression
Mathematical expression		Hasn't run yet
Mathematical expression
Mathematical expression		Hasn't run yet

This question is used in the following exam:

Week 8: Further counting by Daniel Mansfield in Discrete Mathematics.

Loading...

Error

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Daniel Mansfield 7 years, 7 months ago

Daniel Mansfield 7 years, 7 months ago

Daniel Mansfield 7 years, 7 months ago

Error in variable testing condition

Error

Warning

Generated value: `integer`

Parts

Number entry

Advanced settings

Loading...

Error

Counting 2: the pigeonhole principle

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Daniel Mansfield 7 years, 7 months ago

Daniel Mansfield 7 years, 7 months ago

Daniel Mansfield 7 years, 7 months ago

Error in variable testing condition

Error

Warning

Generated value: integer

Parts

Number entry

Advanced settings

Generated value: `integer`