Tall med forskjellige sifre
On januar 11, 2021 by adminVurder settet med naturlige tall fra 0 til 999 inkludert. Anta at vi velger noen delsett av dette settet slik at et par tall fra det ikke deler mer enn ett siffer i de samme posisjonene. For å avklare er
- Par som 123 og 456 åpenbart tillatt siden de ikke deler noen sifre til felles.
- 123 og 321 er tillatt sammen siden, mens de har de samme eksakte sifrene, bare de 2 er faktisk i samme posisjon.
- 812 og 212 ville ikke være tillatt siden de begge deler «12» på slutten, som er to sifre.
- 206 og 246 er heller ikke tillatt. De delte sifrene trenger ikke å være sammenhengende.
- Ledende nuller betyr noe, så 5 og 205 er et forbudt par som vi vil. (Tenk på 5 som «005».)
Husk at dette trenger å holde for hvert par tall i delsettet. Hva er det største settet (som i de fleste elementene ) som oppfyller denne betingelsen? Hva med settet med den største sum av elementer?
(Puzzle inspirert av en samtale med en venn angående feil inntasting av ID-nummer. Unnskyld hvis dette allerede er spurt her.)
Svar
For hva det er verdt, Jeg har en fin visualisering av hvorfor svaret er 100:
Se for deg en enklere sak, der du har alle tallene 0-99 og du ikke kan ha to tall som deler et tall på samme sted; vi kan tegne en talltabell slik:
Merk at hvert tall i en rad deler sitt første siffer, og hvert tall i en kolonne deler det andre siffer. Derfor må du velge tall slik at ingen deler en rad eller kolonne. Det er ganske klart at det maksimale antallet tall du vil kunne velge er 10. Her er en løsning:
Vurder nå saken som er stilt i spørsmålet. Få 10 av disse 0..99 tabellene, bortsett fra at den andre tabellen har 100..199, den tredje 200..299 og så videre. Lag dem deretter hverandre for å danne en 10x10x10 rutenett fra 0..999 (jeg har skrevet inn noen av tallene for å gi deg ideen):
Merk at hvert tall i en hvilken som helst «stripe» på ti kuber (rad eller kolonne) deler to sifre til felles. Derfor må du velge tall slik at ingen tall deler en «stripe».
Etter å ha tenkt litt over er det klart at du bare vil være i stand til for å velge 100 slike tall.
Svar
For å legge til i PrisonMonkeys «svar, hvert sett med 100 elementer vil ha samme sum, som er 49950. For hvert sted i tallet kan hvert siffer bare vises i det stedet e på det meste 10 ganger, fordi det ikke kan vises med samme verdi for et annet sted to ganger. Dette betyr at hvert siffer må vises på hvert sted nøyaktig 10 ganger, for at det totalt skal være 100 tall i settet. Derfor kan vi oppsummere hvert sted separat for å få 45000 + 4500 + 450 = 49950.
Svar
Jeg har en løsning med 100 elementer i settet. Generer hvert tall som følger:
For element $ 0 \ leq n \ leq 99 $, legg til
ABC
til settet derAB
er $ n $ (med ledende null hvis $ n < 10 $) ogC
erA+B mod 10
. Så for $ n = 3 $ erAB
03
ogC
er0+3 mod 10=3
, som betyrABC
er033
.
Det er ingen tallpar i dette settet som bryter med betingelsen (så vidt jeg vet, altså). Og det er ikke noe tresifret nummer ABC
med en annen AB
del, siden jeg dekket alle de 100 mulighetene. Noe som betyr at dette er det største mulige settet som tilfredsstiller betingelsen.
Jeg har ingen løsning på det andre spørsmålet ennå.
AB
57
(A=5
ogB=7
), ogC
er5+7 mod 10=2
, såABC
er572
.