组合数学 (Spring 2013)/Problem Set 2 and Carmichael number: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
No edit summary
 
imported>Addbot
m (Bot: 21 interwiki links moved, now provided by Wikidata on d:q849530)
 
Line 1: Line 1:
*<font color="red" size=4>每道题目的解答都要有完整的解题过程。中英文不限。</font>
In [[number theory]] a '''Carmichael number''' is a [[composite number|composite]] positive [[integer]] <math>n</math>, which satisfies the [[congruence]] <math>b^{n-1}\equiv 1\pmod{n}</math> for all integers <math>b</math> which are [[coprime|relatively prime]] to <math>n</math>. Being relatively prime means that they do not have common divisors, other than 1. Such numbers are named after [[Robert Daniel Carmichael|Robert Carmichael]].
*<font color="red" size=5>这次作业只有一星期的时间。</font>


== Problem 1==
All [[prime number]]s <math>p</math> satisfy <math>b^{p-1}\equiv 1\pmod{p}</math> for all integers <math>b</math> which are relatively prime to <math>p</math>. This has been proven by the famous mathematician [[Pierre de Fermat]]. In most cases if a number <math>n</math> is composite, it does '''not''' satisfy this congruence equation. So, there exist not so many Carmichael numbers. We can say that Carmichael numbers are composite numbers that behave a little bit like they would be a prime number.  
Prove the following identity:
{{Math-stub}}
*<math>\sum_{k=1}^n k{n\choose k}= n2^{n-1}</math>.
[[Category:Number theory]]
 
(Hint: Use double counting.)
 
== Problem 2 ==
Show that among any group of <math>n</math> people, where <math>n\ge 2</math>, there are at least two people who know exactly the same number of people in the group (assuming that "knowing" is a symmetric relation).
 
== Problem 3 ==
Let <math>S</math> be a subset of <math>\{1,2,\ldots,2n\}</math> such that <math>|S|>n</math>. Show that there exist <math>a,b\in S</math> such that <math>a</math> and <math>b</math> are coprime.
 
== Problem 4 ==
(Due to Karger)
 
Balls of 8 different colors are in 6 bins. There are 20 balls of each color. Prove that there must be a bin containing 2 pairs of balls from the two different colors of balls.
 
== Problem 5 ==
(Erdős-spencer 1974)
 
Let <math>n</math> coins of weights 0 and 1 be given. We are also given a scale with which we may weigh any subset of the coins. Our goal is to determine the weights of coins (i.e. which coins are 0 and which are 1) with the minimal number of weighings.
 
This problem can be formalized as follows: A collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> is called '''determining''' if an arbitrary subset <math>T\subseteq[n]</math> can be uniquely determined by the cardinalities <math>|S_i\cap T|, 1\le i\le m</math>.
 
* Prove that if there is a determining collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math>, then there is a way to determine the weights of <math>n</math> coins with <math>m</math> weighings.
* Use pigeonhole principle to show that if a collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> is determining, then it must hold that <math>m\ge \frac{n}{\log_2(n+1)}</math>.
 
(This gives a lower bound for the number of weighings required to determine the weights of coins.)

Latest revision as of 08:08, 11 March 2013

In number theory a Carmichael number is a composite positive integer [math]\displaystyle{ n }[/math], which satisfies the congruence [math]\displaystyle{ b^{n-1}\equiv 1\pmod{n} }[/math] for all integers [math]\displaystyle{ b }[/math] which are relatively prime to [math]\displaystyle{ n }[/math]. Being relatively prime means that they do not have common divisors, other than 1. Such numbers are named after Robert Carmichael.

All prime numbers [math]\displaystyle{ p }[/math] satisfy [math]\displaystyle{ b^{p-1}\equiv 1\pmod{p} }[/math] for all integers [math]\displaystyle{ b }[/math] which are relatively prime to [math]\displaystyle{ p }[/math]. This has been proven by the famous mathematician Pierre de Fermat. In most cases if a number [math]\displaystyle{ n }[/math] is composite, it does not satisfy this congruence equation. So, there exist not so many Carmichael numbers. We can say that Carmichael numbers are composite numbers that behave a little bit like they would be a prime number. Template:Math-stub

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=组合数学_(Spring_2013)/Problem_Set_2&oldid=7723"