ECS 20: Discrete Mathematics for Computer Science PS1.Problems UC Davis — Prof. Sept 22, 2021
Problem Set 1 – Due Tuesday, September 28, at 5 pm
Recall from our syllabus all of the following. Homeworks are turned in on Gradescope. You must upload a pdf file produced from LATEX. You may work with zero or one partners. If you work with a partner you must turn in a single assignment for the two of you, entering both names in Gradescope, not just on the softcopy. If you get ideas from anyone other than your named partner, your professor, or a TA, you must acknowledge them. Any use of old problem-set solutions is strictly forbidden.
1 (a) A ball and a bat costs $1.10 (total). The bat costs $1 more than the ball. How much does the ball cost? (b) If your first impulse for (a) was wrong, explain why you think that might have been so. NB: You might ask a few people around you to see if they get it right.
2. Before COVID-19, I used to spend much time jetting about the globe. One day as I was walked to my gate at the airport I noticed that, for the third time this hour, I needed to stop to tie a shoe lace. There was a moving walkway just ahead. Normally I walk on moving walkways, but I could always pause there long enough to tie my shoe, instead of doing it now. I wondered: if I wait to tie my shoe until I get to the moving walkway, will I reach my gate faster, slower, or will it make no difference? Help me figure it out, convincingly explaining your answer. Note: Like all problems I ask, if you need to make any reasonable assumptions to solve a problem, go ahead and do so, explicitly stating your assumption.)
3. Margaret bicycles from Davis to Winters at 20 mph. She arrives at Steady Eddy’s only to discover that it is closed. Dejected, she rides back at 15 mph. What is her average speed over the entire trip?
4. A sadistic guard lines up his 10 prisoners, whom he affectionately refers to as prisoners P0 , P1 , . . . , P9 . (The guard, having majored in CS, prefers to index his prisoners starting at 0.) So situated, prisoner Pi can see the head of each prisoner Pj if and only if j > i. The guard shouts: “I am going to put a hat on your stupid little heads. Either a white hat or a black hat. Then I am going to ask you, starting at prisoner P0 and moving my way up to P9, if your own hat is white or is black. If you answer incorrectly, I will immediately shoot you. If you answer correctly, you will live another day.”
Carefully describe an optimal strategy for the prisoners to minimize their losses. Under your strategy, what is the maximum number of prisoners who will die?
Hint: Think parity (odd/even), or XOR.
5. Suppose you must write down every positive integer from 1 to 99999. That is, you write 1,2,…,9,10,11,…,99,100,101,…,99998,99999.
but with all the numbers filled in—no ellipses. In carrying out this tedious exercise, how many times will you write the digit “1”? Try to find an easy way to get to the answer.